doraemon_icpc's blog

By doraemon_icpc, history, 7 years ago, In English

Need Editorail for the problem INSQ17X from INSOMNIA. There are lot of problems innvolvinf Tree and GCD. Any insights would help https://www.codechef.com/INQU2017/problems/INSQ17X

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

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I did not solve it but I had got an idea but with a problem. :(

You can do a dfs traversal in the tree while maintaining a deque. You add the value of the node in the deque as you traverse it. Maintain a map containing the frequency of all the prime factors of the values in the deque. Suppose the value of node u has a prime factor that has already been used by another value in the deque. Start popping the values from the front until there is no more contradiction. Since all the elements will be in the deque twice(You need not add a value back once its popped). Suppose the length of the deque is N after popping the elements, then there N nodes where the path could have started to end at u, add N to your answer and continue the dfs. When the dfs on u is finished, if the last element is the value of u(Not a duplicate value, see if the value is the value that was pushed in by u) then pop u from the back.

The problem is that, after u finishes a dfs in one of its child's subtree, to go to the next subtree the whole deque needs to be made again. I hope someone can help me figure out what to do in this case. :( :( :(

For anyone who helps me out: Thank you in advance. :)

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

First let's define an array maxUp[i].
Suppose you are at node x whose level is L and value is v[x]. Now you want to know the node y(an ancestor of x) present at least depth such that all nodes from y to parent[x] are coprime to v[x].
So maxUp[x] = level[y]. But one important thing to notice is that, maxUp of a node has to be >= maxUp of its parent(always). Because we want a chain where all values are coprime.
So answer contributed by node x will be (L-maxUp[x]+1).
Sum these values for all nodes.
Now to implement it run a dfs and maintain an array of vectors val. Here val[i] = vector of levels of nodes whose values were divisible by i. And now compute maxUp[x] with the help of val and factors of v[x].
You can see my implementation here
Happy coding :)