Home » 国际竞赛 » Details

USACO 2015 US Open, Gold Problem 1. Googol

Category: 国际竞赛, 计算机国际竞赛 Date: 2017年12月8日下午3:46

原题下载

USACO2015OPEN-G1

答案

(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? $N \leq 10^{100}$ , this code is too slow!

We will make an optimization that makes use of the fact? $l f t - r g t \in {0, 1}$ , where? $l f t$ ?and? $r g t$ ?are the size of the left and right subtree of? $c u r$ ?(as used in the above code).

We do not need to compute? $l f t$ ?from scratch; we merely need to compute it given that it is either? $r g t$ ?or? $r g t + 1$ .

In other words, we evaluate? $l f t = c o u n t G i v e n (a, r g t)$ .

When computing? $c o u n t G i v e n (c u r, x)$ , we use the same approach as before: compute the size of the left subtree of? $c u r$ ?and the right subtree of? $c u r$ ?(which we shall again name? $l f t$ ?and? $r g t$ ), then evaluate? $1 + l f t + r g t$ ?to find the size of the subtree at? $c u r$ .

In general, if? $l f t + r g t = z$ , then? $l f t = ⌈ \frac{z}{2} ⌉$ and? $r g t = ⌊ \frac{z}{2} ⌋$ . This is very useful, as we know? $z + 1$ ?is either? $x$ ?or? $x + 1$ .

If? $x$ ?is even, then? $l f t \in {⌈ \frac{x - 1}{2} ⌉, ⌈ \frac{x}{2} ⌉} ⟹ l f t = \frac{x}{2}$ .

If? $x$ ?is odd, then? $r g t \in {⌊ \frac{x - 1}{2} ⌋, ⌊ \frac{x}{2} ⌋} ⟹ r g t = \frac{x - 1}{2}$ .

Knowing? $l f t$ ?lets us recursively find? $r g t = c o u n t G i v e n (b, l f t - 1)$ , and vice versa --? $l f t = c o u n t G i v e n (a, r g t)$ . 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? $70, 000$ .

In the maximum case,? $N = 10^{100}$ . Then the height? $H \approx \lg_{2} N = 100 \lg_{2} 10 < 100 \cdot \frac{10}{3} \approx 333$

The procedure? $c o u n t$ ?is called once for each level. At a height? $h$ ,? $c o u n t$ ?spawns a? $c o u n t G i v e n$ ?which makes? $h$ ?queries, so overall, there are? $1 + 2 + \dots + 333 \approx 10^{6} / 18 < 70000$ ?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? $O (\log n)$ ?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.]