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?)