E - Reverse and Inversion Editorial by evima
We will explain two solutions:
\(\mathrm{O}(N\log M)\) solution from the characteristics of the operation: Here
\(\mathrm{O}(N\log M)\) solution from optimization of DP: https://atcoder.jp/contests/arc154/editorial/5600
\(f(P)\) equals \(\sum_{i=1}^{N} (\)the number of indices \(j\) such that \(j<i,P_j > P_i)\times i -\sum_{i=1}^{N} (\)the number of indices \(j\) such that \(i<j,P_i > P_j)\times i\).
Below, let \(g(i):= (\)the number of indices \(j\) such that \(j<i,P_j > P_i)-(\)the number of indices \(j\) such that \(i<j,P_i > P_j)\). Additionally, let \(\mathrm{inv}(i) := (\)the index \(j\) such that \(P_j = i)\).
Then, we have \(g(i) = i - P_i\).
Proof
For $P=(1,2,\dots,N)$, we have $P_x=x$, so $g(x)=x-x(=0)$. Now, let us choose an element to the left of $x$ and move it to the right of $x$. Then, $g(\mathrm{inv}(x))$ decreases by $1$, regardless of whether that element is larger or smaller than $x$. Similarly, when an element to the right of $x$ is moved to the left of $x$, $g(\mathrm{inv}(x))$ increases by $1$. Thus, $g(i)=i-P_i$.Thus, we have \(f(P) = \sum_{i=1}^{N} i(i-P_i)\). Therefore, for integers \(1 \le i \le N\), we want to find the expected value of the index of the position of the element \(P_i\) after \(M\) operations.
Here is an important property.
- For an element involved in one or more operations, the distribution of its final position is symmetrical.
Proof
First, for the $i$-th element from the left, there are $\min(i, N-i+1, j, N-j+1)$ ways to reverse an interval to affect it so that it becomes the $j$-th from the left.
For an element, let us look at the last operation that affected it. Assume that the element was the $i$-th from the left. From the above, there are equal numbers of ways to move it to the $j$-th and to the $(N-j+1)$-th. Thus, the distribution of the final position of this element is symmetrical, even after taking the sum for all $i$.It is easy to find the probability that an element is involved in one or more operations, in which case the expected value of the index of its position is \(\frac{N+1}{2}\), in \(\mathrm{O}(\log M)\) time. The expected value otherwise is equal to its original position.
Thus, the problem can be solved in \(\mathrm{O}(N\log M)\) time.
posted:
last update: