Editorial : Deterministic Heap (Easy Version)

For anyone else wondering about where the binomial coefficients come from, here’s an alternate explanation.

Let’s try to find the number of unique max heaps using the $k$ operations without worrying about the deterministic conditions. We start with a max heap (since all elements are zero), and doing an operation maintains the max heap invariant. So, we only have to blindly apply the operation on nodes.

Let $T = 2^{n} - 1$

The first thought that comes to mind is to perform the first operation on a random node, and then recurse for the same tree, with $k - 1$ ops left, i.e, something like

$f(k) = T\cdot f(k - 1)$

However, this leads to overcounting. Consider

Configuration 1 : Node $x$ is chosen in round 1, and it’s child $c$ is chosen in round 2.
Configuration 2 : Node $c$ is chosen in round 1, and it’s parent $x$ is chosen in round 2.

Notice that if $k = 2$, these configurations are essentially the same. Hence, we can deduce that round number at which a particular node participated is not important, what’s important is how many rounds did it participate in.

So, let’s call the number of participation rounds for each node as $x_1, x_2 \dots x_T$, then, since there can only be $k$ different rounds, we should have

$x_1 + x_2 + \dots x_T = k$

So the number of unique max heaps is the non-negative integral solution for this equation, which is pretty well known via Stars and Bars to be $k + T - 1 \choose k$

First, let’s find out the number of unique max heaps using the $k$ operations (Let’s disregard deterministic properties).

$dp[n][k]$ represents the number of unique max heaps on $n$ levels perfect binary tree with $k$ operations. Then, let’s think about how many operations will we use at the root, $root \in [0, k]$, and the remaining number of operations is $remain = k - root$.

Then, from the remaining number of operations, we need to distribute some operations to the left and right subtree. How many operations can left receive? $left \in [0, remain]$, Therefore, $right = remain - left$. After distributing the operations, the left and right subtree have become independent. Hence, the transitions are:

$$ dp[n][k] = \sum_{remain \in [0, k]} \sum_{left \in [0, remain]}(dp[n - 1][left]*dp[n - 1][right]) $$

Note that $dp[n][k]$ is $T + k - 1 \choose k$, as described in my earlier comment, but I just showed you a DP instead of a combinatorics approach.

Now, how do we count unique deterministic max heaps? The first thought that comes to mind is to track the final value of each node, something like $dp[n][k][val]$. However, if you think about it, this value parameter can be inferred from other parameters. The root will always have $val = k$.

Then, you might think about blocking the transitions when $left = right$. However, that is also incorrect, because left and right child are allowed to be equal if the node is not on the path defined in the problem. This means that we need to track another DP parameter, which would be a boolean.

$dp[n][k][on\_path]$ is no. of unique max heaps on $n$ levels with $k$ operations such that $on\_path$ denotes whether root is on the path.

But since 3D DP will be hard to visualize and optimize, let’s remove the boolean parameter, and maintain two 2D DP. Define $indp[n][k]$ to be the number of unique deterministic max heaps when the root is in the defined path. Similarly, define $outdp[n][k]$ to the number of such configurations when root is not on the path.

To perform the transitions,

$$ outdp[n][k] = \sum(outdp[n - 1][left]*outdp[n - 1][right]) $$

If $left > right$ $$ indp[n][k] = \sum(indp[n - 1][left]*outdp[n - 1][right]) $$

But if $left < right$

$$ indp[n][k] = \sum(outdp[n - 1][left]*indp[n - 1][right]) $$

There are $O(N \cdot K)$ states and transitions are $O(K^2)$. Hence, the time complexity is $O(N \cdot K^3)$.

How to optimize it? Before we do that, let’s consider the problem of finding the sum of pairwise product in an array

$$ \sum_{i < j} a[i] \cdot a[j] $$

You immediately know a 1D DP approach. But can you optimize this 2D DP. Why or why not?

for gap in [1, n]:
	for i in [1, n]:
		j = i + gap
		if j <= n:
			ans += a[i]*a[j]

Optimization is not possible, because when a gap is fixed, there is no pattern, or any number that remains constant. However, we didn’t really need to fix the gap, we could’ve fixed $a[i]$ and inferred all the possible gaps, and come up with $a[i]*suffix\_sum$.

We will use the same trick here. Instead of fixing $root$ and then iterating through $left$, let’s directly iterate through $left$ and notice its contribution. You’ll realize that $indp$ only takes contribution from a subarray sum of the previous row of $outdp$. Hence, you can optimize using prefix sums.

for left in [0, k]:
	remain = k - left:
	for right in [0, remain]:
		outdp[n][k] += outdp[n - 1][left]*outdp[n - 1][right]
	for right in [0, min(left - 1, remain)]:
		indp[n][k] += indp[n - 1][left]*outdp[n - 1][right]
	for right in [left + 1, remain]:
		indp[n][k] += outdp[n - 1][left]*indp[n - 1][right]

The time complexity is now $O(N \cdot K^2)$.

Code

It’s the same as the transitions in my DP, except it does the heavy lifting through combinatorics (which isn’t really required, it can be offloaded to DP).

Notice that my $outdp[n][k] = {n + T - 1 \choose k}$. (We can see from combinatorics above, but we also chose to calculate it using DP. Let’s call it as $f(n, k)$ from now on.

If you don’t want to compute it explicitly, just remove the $outdp$ matrix altogether. Then, you’ll notice that the $dp[n][k]$ in editorial’s solution is same as my $indp[n][k]$. Then, take my old transitions,

for left in [0, k]:
	remain = k - left:
	for right in [0, min(left - 1, remain)]:
		indp[n][k] += indp[n - 1][left]*outdp[n - 1][right]
	for right in [left + 1, remain]:
		indp[n][k] += outdp[n - 1][left]*indp[n - 1][right]

and let’s remove all keywords that reference $outdp$ and use the combinatorics equivalent.

for left in [0, k]:
	remain = k - left:
	for right in [0, min(left - 1, remain)]:
		dp[n][k] += indp[n - 1][left]*f(n - 1, right)
	for right in [left + 1, remain]:
		dp[n][k] += f(n - 1, left)*dp[n - 1][right]

The editorial’s transitions are written in a fancy way using $x \in [0, j)$ $l \in [j + x, k]$ But my transitions with left and right are doing the same thing, except I use Receiving DP while editorial uses Distributing DP.

If you want to visualize how trees are computed using editorial’s, you can just visualize how trees are computed using left and right variables above, and apply the same thing there. The crucial idea here is that since you are calculating indp, one of the child would go to outdp, and one would remain for indp, hence that’s why you see the product of binomial coefficients with DP. If you understand the above DP, you should be able to understand editorial’s DP as well. Let me know if anything specific that you’re confused about.