R2__D2's blog

By R2__D2, history, 6 years ago, In English

problem in brief:
problem link

you are given a Tree of nodes n(<=2e5). Each nodes has value x(<=2e5).

Let's denote the function g(x,y) as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex x to vertex y (including these two vertices).

For every integer from 1 to 2e5 you have to count the number of pairs (x,y)(1≤x≤y≤n) such that g(x,y) is equal to this number.

My idea:
As the number can be at most 2e5 so, the total number of divisors can be maximum 160.I just stored possible unique gcd for each node u where paths end at some nodes in subtree u. total numbers can be maximum 160 as well for each nodes. while traveling each node I calculated possible answers where paths start at some node in subtree u and ends at some nodes in subtree u. Finally when return back to parent node I cleared the memory of every childs to save memory.

Unfortunately, I got memory limit exceeded at test 100. but I have no idea why as I store values at only one node at a particular time.

my submission

Any suggestions will be appreciated.


Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By R2__D2, history, 7 years ago, In English

Given N nodes and M edges. I have to color(only 2 colors) the nodes in such a way that at least one of the connected nodes of each nodes belong to different color. What will be the maximum number of nodes of same colored ? I am not sure about the range of N,M. I was working on bipartite graph. Suddenly I noticed it but failed to manage any idea to solve it.

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it