Abacus'17-OLPC Geek Tree Solution

Hello, the contest Abacus’17 has just finished. Can somebody tell how to solve the problem, Geek Tree.

link - CodeChef: Practical coding for everyone

1 Like

Can someone tell the solution for this problem too : CodeChef: Practical coding for everyone

@tihorsharma

In this problem,try drawing a matrix to come up with a solution.
You will observe a pattern.

If u still can’t figure it out, tell me and I’ll tell u the full solution.

This u can do easily bu using a dfs and BIT or segment tree.Basically as u go into a branch during dfs u update the node value in BIT.Then u do a search for all values in the range [s-k,s+k] in the ancestors where “s” is the current node value because all those values will be counted as pairs with s.
Here is when u will use BIT to find this value:

ans+=query(s+k)-query(s-k-1);

U find this in O(log n).Then update this current node’s value in BIT before going to its children.
By doing this u can find the answer for all vertices and hence for the whole subtree.

See my code for reference : CodeChef: Practical coding for everyone

Happy coding :wink:

2 Likes

try solving this

3 Likes

Okay I will try Thanks :slight_smile:

Thanks although I don’t know BIT or segment trees yet. So, I’ll probably try this problem later.

Can you please elaborate your answer? What will you get in ans after performing this query? And why there is a need of update in this offline query?