Editorial for COCI '13 Contest 5 #2 Obilazak

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.

Firstly, we will enumerate the nodes in the tree in the following way: the root is number $1$ ~1~, its left child is number $2$ ~2~ and its right child is number $3$ ~3~. Generally, the left child of a node $t$ ~t~ is numbered with $2t$ ~2t~ and the right child is numbered with $2t+1$ ~2t+1~.

Mirko walks around visiting the buildings following this recursive algorithm:

visit(x)
if x < 2^K-1, visit(2 * x)
write down x on paper
if x < 2^K-1, visit(2 * x + 1)

We can construct a "reverse" recursive function which will reconstruct a tree for a given route of visits. We will use an array tree[] where the $i^\text{th}$ ~i^\text{th}~ item is going to be a label of the $i^\text{th}$ ~i^\text{th}~ node and a counter p which is initially set to $1$ ~1~.

return(x)
    if x < 2^K-1, return(2 * x)
    tree[x] = route[p]
    p = p + 1
    if x < 2^K-1, return(2 * x + 1)

In the end, we output items of the array tree[].

The task could have been solved without recursion, with noticing regularities in the route of visits of the tree. Consult the source code for this type of solution.

Comments

There are no comments at the moment.