Editorial for Bubble Cup V8 H Bots

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.

The problem can be transformed to a more formal one: how many vertices will a trie (data structure) contain, if we add all possible strings of length $2N$ ~2N~ with $N$ ~N~ zeroes and $N$ ~N~ ones to this trie.

First, it is obvious that the upper half of this tree will be a full binary tree. Let's take a look at $N = 3$ ~N = 3~:

level $0$ ~0~: $1$ ~1~ vertex
level $1$ ~1~: $2$ ~2~ vertices
level $2$ ~2~: $4$ ~4~ vertices
level $3$ ~3~: $8$ ~8~ vertices.

Starting from level $N+1$ ~N+1~, not every vertex will have two children. Vertices that will have two children are those that have less than $N$ ~N~ zeroes and less than $N$ ~N~ ones on the path to the root.

So, here is how we calculate how many vertices there will be on level $i+1$ ~i+1~:

Let's define $S_i$ ~S_i~ as the number of vertices on level $i$ ~i~ which have less than two children
If $V_i$ ~V_i~ is the number of vertices on level $i$ ~i~, then $V_{i+1} = 2V_i-S_i$ ~V_{i+1} = 2V_i-S_i~
$S_i$ ~S_i~ can be calculated easily using binomial coefficients: $S_i = 2 \binom i N$ ~S_i = 2 \binom i N~

Everything else in the task are implementation techniques. We need to calculate some modular multiplicative inverses, which can be done in logarithmic time using exponentiation by squaring. We can calculate binomial coefficients efficiently, by using the values calculated for the previous level.

Time complexity: $\mathcal O(N \log(10^9+7))$ ~\mathcal O(N \log(10^9+7))~

Comments

0

miav commented on June 27, 2024, 6:57 a.m.

Can you share the proof?

9

ahoraSoyPeor commented on Feb. 21, 2022, 4:46 p.m. ← edited →

Challenge: Prove that the answer is exactly $\binom{2n+2}{n+1}-1$ ~\binom{2n+2}{n+1}-1~.