TREEROOT - Editorial

Problem Link

Practice

Contest

Difficulty

SIMPLE-EASY

Pre-requisites

Simple Math

Problem

You are given partial information of a binary tree: for each node, its id, and the sum of the ids of its children. This sum is 0 if the node is a leaf, and if the node has just one child, then it is equal to the child’s id. Given this, you are asked to output ids of all possible roots of such a tree, given that such a tree does exist.

Explanation

The possible root node is unique (if it exists). Since we are given that a tree exists, finding the root node’s id is as simple as follows.

Denote by “id(node v)” the id of the node v, and “sid(node v)” the sum of the id’s of v’s children. Consider x = sum(id(v) - sid(v)) over all nodes v. If a binary tree exists, then its root node has to have id x. This is because, for each node v other than the root, its id is counted once in the sum (as id(v)) and it cancels out once in the sum (as -sid(v’s parent)). Since the root node doesn’t have a parent, its id is left uncanceled in the sum.

The constraints N <= 30 were left to trick some people into trying out brute force solutions. The test-data however does not allow for such solutions to pass.

One possible brute force solution requires you to store all possible subtrees rooted at a particular vertex, and then for each vertex t, and possible children-pairs u,v test if t with u and v can form a possible subtree (by merging two subtrees rooted at u and v). The main issue to be handled here, is to ensure that the considered subtrees at u and v to be merged are disjoint.

This can be done by storing vector dp[node u] which stores bitmasks of all possible subtrees rooted at u. Finally check if there exists a vertex on which a subtree rooted includes all vertices.

Unfortunately the tests included cases where there were as many as 10^4 possible bitmasks for subtrees rooted at a node, and hence such an attempt to merge subtrees would have tried 10^4 * 10^4 possibilities to merge. Such an approach would time out.

Author’s Solution

Can be found here

Tester’s Solution

Can be found here

53 Likes

Please provide a rough idea for proving “The possible root node is unique (if it exists).”

6 Likes

hell of a question!!

1 Like

“The most incomprehensible thing about the question is that it is comprehensible.”

Brilliant question and even more brilliant solution!
Excellent

1 Like

NIce solution, thanks

Brilliant question really and awesome explanation Thanks

root += id - sum_ids

i must appreciate the way this problem is disguised. when i actually saw the solution after literally 2 hours of struggling with the recursive procedures, i was totally stunned and within 10s i understood the whole setup :stuck_out_tongue: sadly i started in the wrong direction :confused: good work by the problem setter! :slight_smile:

12 Likes

i have done this brutefoce thing – but it is giving runtime error (segment fault) , please see where i can go wrong.

please give me some test case for its is failing.

sum of two ids cannot be more than 2000 and there are only 30 nodes.


[1]. 

  [1]: http://www.codechef.com/viewsolution/1647806

This question should now be titled,“Master of Disguise”…
Solution,totaly took me by a surprise,such an easy insight in the end.
Good work !

5 Likes

I have one question :
“x = sum(id(v) - sid(v))”
will hold for any tree (not necessarily binary) , so is there any point that it was mentioned in the problem that the given tree is binary.

This is only to disguise the problem even more :stuck_out_tongue:
I think that for trees other than binary
we wouldn’t have so many dp/backtracking solutions during the contest :smiley:

1 Like

I think it follows from the solution. If you are able to prove the solution, in a way you are proving that the root is unique, since root-node-id is just a function of inputs.

Nice question !:smiley:

The solution shocked me completely. Good problem kudos to the setter.