Connection Status:
Competition Arena > RndSubTree

RndSubTree

SRM 731 · 2018-03-16 · by subscriber

SRM 731 · 2018-03-16 · by subscriber · Advanced Math, Dynamic Programming, Math
Class Name: RndSubTree
Return Type: int
Method Name: count
Arg Types: (int)
Problem Statement

Problem Statement

Hero has an infinite complete binary tree rooted at the vertex r. That is, the tree contains r, its two children, four grandchildren, and so on. Initially, all vertices in this tree are white. Hero is going to color k vertices of its tree red. He will choose each of those vertices at random. More precisely, he will repeat the following procedure k times:
  1. Place a token onto the root vertex r.
  2. While the token is on a red vertex, choose one of its two children at random with equal probability and move the token onto the chosen child.
  3. When the token is on a white vertex for the first time, color that vertex red and remove the token.
If there are k red vertices in the tree, there are exactly k*(k-1)/2 simple paths such that both endpoints of the path are red. Hero is interested in the total length of all these paths. Calculate the expected value of that total length. Let M = 10^9 + 7. It can be shown that the exact value of the answer can be written as a reduced fraction P/Q such that Q and M are relatively prime. Let Q^(-1) be the multiplicative inverse of Q, modulo M. Compute and return the value (P*Q^(-1)) modulo M.

Constraints

  • k will be between 1 and 2000, inclusive.
Examples
0)
1
Returns: 0

With only one red vertex there are no paths, so their total length is always zero.

1)
2
Returns: 1

The two red vertices will always be the root vertex r and one of its children. The only path with both endpoints red will always have length 1.

2)
3
Returns: 4

Regardless of the random choices, the three red vertices will always form a path. (The root vertex r may be an endpoint of this path, or it can be in its middle.) The three random paths will have lengths 1, 1, and 2, for a total of 4.

3)
4
Returns: 875000016

With probability 7/8 the sum of path lengths is 10 and with probability 1/8 the sum of path lengths is 9. Thus, the expected value of the sum of path lengths is (7/8)*10 + (1/8)*9 = 79/8. The multiplicative inverse of 8 modulo M = 10^9 + 7 is 125,000,001, because (125000001*8) mod M = 1. Thus, the value you should return is (79 * 125000001) mod M = 875000016.

4)
5
Returns: 531250023

Submissions are judged against all 32 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RndSubTree with a public method int count(int k) · 32 test cases · 2 s / 256 MB per case

Submitting as anonymous