SEGTREECON - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: hjroh0315
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

You’re given N and K.
Find a binary string S of length 2^N such that the following condition is satisfied:

  • Create a perfect binary tree with 2^N leaves.
  • Write the values of S on the leaves, left to right.
  • For each internal vertex, define its value to be the minimum of the values of its left and right children.
  • In the final tree, the sum of values should be exactly K.

EXPLANATION:

Let’s make a couple of observations about the values of the tree vertices.

  1. Every value will be either 0 or 1.
    This is because the leaves have values 0 or 1, and so taking the min of them can’t give any other value.
    In particular, this observation tells us that “sum of values equal to K” is equivalent to “exactly K vertices have value 1”.
  2. The value of a vertex is nothing but the minimum value across all leaves present in its subtree.
    This is easy to show inductively: it’s trivially true for leaves, and for internal vertices you’re taking the minimum of its left and right children - which encompasses all leaves.
  3. The first two points combine to tell us that a vertex can have value 1 if and only if every vertex in its subtree has value 1.
    An alternate way of looking at this is that if some leaf has value 0, all its ancestors must have value 0.

We can now use these observations to come up with a solution.

Rather than construct the string S, let’s just try to construct a valid tree that has K vertices with value 1 and everything else with value 0.
If we can manage this, simply extracting the values of the leaves will give us the string S.

So, let’s look at the tree as a whole.
It has 2^N leaves, and hence 2^{N+1} - 1 vertices in total.

First, consider the root of the tree. This can have value either 0 or 1, we’ll look at the cases separately.

If the root has value 1, then as noted above every vertex under it must also have value 1.
This would give us 2^{N+1} - 1 vertices with value 1.
If K = 2^{N+1} - 1 this is a valid solution, and we’re done.
If K \neq 2^{N+1} - 1 we can’t do this, and so the root must have value 0.

The root having a value of 0 means that some leaf has a value of 0.
However, a leaf having a value of 0 means that each of its ancestors will also have a value of 0.
Since this is a perfect binary tree, any leaf will have N+1 ancestors (including itself).
This means at least N+1 vertices cannot have a value of 1.
In particular, if K \gt 2^{N+1} - 1 - (N+1), no solution can exist.
That leaves us with K \leq 2^{N+1} - 1 - (N+1) to solve now.

However, once the root is given a value of 0, observe that the left and right subtrees are completely independent of each other.
Further, each of these subtrees is itself a perfect binary tree, just with 2^{N-1} leaves instead.
So, we can attempt to recursively solve the problem for each of them.

The only decision now is how many 1 vertices each side should receive.
This distribution can be done greedily:

  • Note that each side has 2^N - 1 vertices.
  • If K \geq 2^N - 1, give 2^N - 1 to the left and K - (2^N - 1) to the right (essentially, the left side becomes all ones).
  • If K \lt 2^N - 1, we could try giving all K to the left and 0 to the right.
    However, recall the impossible case above: if K \gt 2^N - 1 - N then no solution can exist on the left side.
    To account for this, we can give \min(K, 2^N - 1 - N) to the left side and everything else to the right side.

It’s not hard to see that this will always work:

  • If the left side receives 2^N - 1, the right side will receive
    K - (2^N - 1) \leq 2^{N+1} - 1 - (N+1) - (2^N - 1) = 2^N - 1 - N vertices, so it will not be “bad”.
  • If the left side receives \lt 2^N - 1 - N, the right side will receive 0 and be fine.
  • If the left side receives 2^N - 1 - N, the right side will receive at most N-1 vertices, and we have N-1 \leq 2^N - 1 - N for any N \geq 0 so we’re still fine.

In other words, as long as K doesn’t fail the value check initially, we’re able to ensure that the recursive calls don’t fail the check either.
So, if the check doesn’t fail at the very first call, we know for sure that it’ll never fail and we always obtain a solution via the recursion.

In summary, we have a rather simple recursive solution that looks like this.

  1. Define f(N, K) to be the answer for 2^N leaves and sum K.
  2. If K = 2^{N+1} - 1, return 2^N ones.
  3. Otherwise, if K \gt 2^{N+1} - 1 - (N+1), no solution exists.
  4. Then, to solve K \leq 2^{N+1} - 1 - (N+1):
    • If N = 0, then K = 0 so return a single 0.
    • If K \geq 2^N - 1, the answer is f(N-1, 2^N - 1) + f(N-1, K - 2^N + 1).
    • Otherwise, let L = \min(K, 2^N - 1 - N) and the answer is f(N-1, L) + f(K - L).
    • Here, + denotes string concatenation.

This way, the problem is solved in \mathcal{O}(2^N) time.

TIME COMPLEXITY:

\mathcal{O}(2^N) per testcase.

CODE:

Editorialist's code (PyPy3) 
def solve(n, k):
    if n == 1:
        if k > 1: return '-'
        return str(k)
    
    if k == 2**n - 1: # all ones
        return '1' * (2 ** (n-1))
    
    # at least one 0 leaf -> at least n 0 vertices
    if k > 2**n - 1 - n:
        return '-'
    
    left = 2**(n-1) - 1
    if k >= left:
        return solve(n-1, left) + solve(n-1, k - left)
    else:
        left = min(k, left - (n-1))
        return solve(n-1, left) + solve(n-1, k - left)

for _ in range(int(input())):
    n, k = map(int, input().split())
    ans = solve(n+1, k)
    if ans.count('-') == 0: print('Yes', ans)
    else: print('No')