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.