Contest Duration: - (local time) (300 minutes) Back to Home

## B - 01 Inversion Expected Editorial by Benq

DP Solution

For each index $$i\in [1,N]$$, we will count the expected number of operations involving that index of $$S$$. The final answer will be half the sum of the expected number of operations over all indices.

Solving for a single index $$i$$:

The expected number of operations involving index $$i$$ depends only on

• the number of ones to the left of $$i$$
• the value of $$S_i$$
• the number of zeros to the right of $$i$$

Why can we ignore zeros to the left of $$i$$? Any operations involving them will permute the characters to the left of $$i$$, but will not change the number of ones left of $$i$$. Similar reasoning holds for ignoring ones to the right of $$i$$.

Assume $$S_i=1$$; if not, we can flip and reverse $$S$$ and change $$i\to N+1-i$$. Let $$dp[o][z]$$ be the expected number of operations involving index $$i$$ when $$S_i=1$$, the total number of ones to the left of or at $$i$$ is $$o$$ ($$o\ge 1$$), and the total number of zeros to the right of $$i$$ is $$z$$ ($$z\ge 0$$). Then we have

$dp[o][z]=\frac{o-1}{o}\cdot dp[o-1][z-1]+\frac{1}{o}\cdot (1 + dp[z][o-1]).$

The first summand comes from operations not involving index $$i$$, and the second comes from operations involving index $$i$$, after which we flip and reverse $$S$$.

The total number of DP states for a single $$i$$ is $$O(N)$$, since $$o-z$$ can take on only two distinct values. Solving over all $$i$$ takes $$O(N^2)$$ time.

Optimizing to $$O(N)$$:

Letting $$H_i$$ be the $$i$$th harmonic number, it may be proven by induction that:

$dp[o][z]=\begin{cases} H_z - H_{z-o+1} + 1 & o\le z \\ H_o-H_{o-z} + z/o & o>z \end{cases}.$

You can come up with this by fixing the value of $$o-z$$, then printing out the fractional value of $$dp[o][z]-dp[o-1][z-1]$$ for small $$o$$ and looking for a pattern (is there a better way?).

Implementation

Equivalence to Official Solution:

Via careful accounting, it can be shown that summing $$dp[o][z]$$ over all indices counts all cells in the Young diagram from the official solution exactly twice.

• $$H_z-H_{z-o+1}$$ can be interpreted as summing the weights along the diagonal $$(1,z-o+2)\dots (o-1,z)$$.
• $$H_o-H_{o-z}$$ can be interpreted as summing the weights along the diagonal the diagonal $$(o-z+1,1)\dots (o,z)$$.
• $$z/o$$ can be interpreted as summing the weights along the column $$(o,1)\dots (o,z)$$.
• $$1$$ can be interpreted as summing the weights along the column $$(o,1)\dots (o,o)$$.

(Is there an easier way to see this?)

posted:
last update: