Editorial for COCI '06 Contest 4 #5 Jogurt

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

There's more than one way to solve this problem, we present one of them.

Let's try to extend a tree of depth $n$ ~n~ for which the property is satisfied to a tree of depth $n+1$ ~n+1~ for which the property is satisfied. Have the root node of the new tree contain the number $1$ ~1~ and put two copies of the old tree as its left and right subtrees, only multiplied by $2$ ~2~. Now the subtrees contain only even numbers and each appears twice between the two subtrees. The property is still satisfied in the subtrees; multiplying the elements by two caused the differences to be multiplied by two, but the depths of those nodes increased by one so this is good.

Add $1$ ~1~ to all leaf nodes in the left subtree and to all non-leaf nodes in the right subtree. Now each element appears only once in the entire tree. The property is still satisfied in the subtrees because adding a constant to all nodes on the same level in a subtree does not change the differences. The property holds for the root node because we added $2^n$ ~2^n~ to the left subtree and $\sum_{i=0}^{n-1} 2^i = 2^n-1$ ~\sum_{i=0}^{n-1} 2^i = 2^n-1~ to the right subtree so the difference is $1$ ~1~.

Comments

There are no comments at the moment.