(Analysis by Steven Hao)
We first present a naive algorithm that recursively iterates through all nodes.
Below is Python code implementing this naive algorithm, which we will soon optimize.
import sys def ask(cur): print cur sys.stdout.flush() return [int(_) for _ in raw_input().split()] def count(cur): # count size of subtree at cur if cur == 0: return 0 a, b = ask(cur) rgt = count(b) lft = count(a) return 1 + lft + rgt ans = count(1) print 'Answer %d' % ans
Of course, with , this code is too slow!
We will make an optimization that makes use of the fact , where and are the size of the left and right subtree of (as used in the above code).
We do not need to compute from scratch; we merely need to compute it given that it is either or .
In other words, we evaluate .
When computing , we use the same approach as before: compute the size of the left subtree of and the right subtree of (which we shall again name and ), then evaluate to find the size of the subtree at .
In general, if , then and . This is very useful, as we know is either or .
If is even, then .
If is odd, then .
Knowing lets us recursively find , and vice versa -- . Overall, this means we only need to recurse once to count the size of a tree given that its size is one of two options.
Below is code implementing this optimization.
def countGiven(cur, x): # given ret = x or ret = x + 1, find ret if cur == 0: return 0 a, b = ask(cur) # lft + rgt = x - 1 or lft + rgt = x if x % 2 == 1: rgt = (x - 1) / 2 lft = countGiven(a, rgt) return 1 + lft + rgt else: lft = x / 2 rgt = countGiven(b, lft - 1) return 1 + lft + rgt def count(cur): # count size of subtree at cur if cur == 0: return 0 a, b = ask(cur) rgt = count(b) lft = countGiven(a, rgt) return 1 + lft + rgt
We can analyze the number of queries this code makes -- we want it to be less than the allowed .
In the maximum case, . Then the height
The procedure is called once for each level. At a height , spawns a which makes queries, so overall, there are queries.
[Note from problem author: Trees of this sort are sometimes called "Braun trees" in the computing literature; they have a number of nice uses particularly in "functional" programming languages, since they are easy to manipulate in a recursive context. For example, to insert a new element in time while maintaining the balancing condition, we can just insert it recursively into our left subtree and then swap the left and right children of the root.]