E - Sliding Window Sort Editorial by evima
Hints → https://atcoder.jp/contests/arc149/editorial/4961
[1] Rephrasing the problem (1)
The problem gradually shifts the segment to sort, but one can convert the coordinate so that this segment always starts at the left end so that the problem repeats the following operation \(K\) times.
Operation: Sort \((A_0, \ldots, A_{M-1})\) and then circular shift the sequence to the left by \(1\).
Below, we handle this problem. For instance, the sequence \(A = (4,1,5,6,2,3)\) in Sample Input 1 will change as follows:
\((4,1,5,6,2,3) \to (4,5,6,2,3,1) \to (5,6,2,3,1,4)\to (5,6,3,1,4,2) \to (5,6,1,4,2,3)\to (5,6,4,2,3,1).\)
[2] Rephrasing the problem (2)
The operation will look even simpler if we divide the sequence into the left \(M-1\) terms and right \(N-M+1\) terms. The left \(M-1\) terms will always be arranged in ascending order after one or more operations, so let us handle this part simply as a set.
Let us write \(L=M-1\), \(R=N+M-1\) for simplicity. Call the set of the left \(L\) terms of the sequence the left set, and the sequence of the right \(R\) terms of the sequence the right sequence.
Then, the process can be rephrased into the following.
We have a left set with \(L\) terms and a right sequence with \(R\) terms. In the operation, we move the term at the beginning of the right sequence to the left set, and then move the smallest element in the left set to the end of the right sequence.
| Initial state | \(\{1,4\}\) | \((5,6,2,3)\) |
| 1st operation | \(\{4,5\}\) | \((6,2,3,1)\) |
| 2nd operation | \(\{5,6\}\) | \((2,3,1,4)\) |
| 3rd operation | \(\{5,6\}\) | \((3,1,4,2)\) |
| 4th operation | \(\{5,6\}\) | \((1,4,2,3)\) |
| 5th operation | \(\{5,6\}\) | \((4,2,3,1)\) |
[3] Reduction to the case \(K=R\)
The problem can be reduced to the case \(K=R\), where the operation is repeated until every term in the right sequence is inserted into the left set exactly once.
If \(K < R\), where some terms are never inserted into the left set, we can simply ignore those terms.
Consider the case \(K > R\). After the operation is performed \(R\) times, the left set has the largest \(L\) numbers: \(\{R+1, \ldots, N\}\). Afterward, a number inserted into the left set gets deleted immediately, so the \((R+1)\)-th and subsequent operations are simply a circular shift of the right sequence. From this fact, one can restore the state after \(R\) operations from the state after \(K\) operations, so the case \(K>R\) can be reduced to the case \(K=R\).
[4] Counting
Assume that the state after \(K\) operations has the left set \(\{R+1, \ldots, N\}\) and the right sequence \((x_1, \ldots, x_R)\) (if the left set is not this one, the answer is \(0\)). Let us count initial states \(\{a_1, \ldots, a_L\}, (b_1, \ldots, b_R)\) consistent with this.
First, it is necessary that if \(x_{i-1} > x_{i}\), \(b_i = x_i\). This is because all elements in the left set at the end of the \((i-1)\)-th operation are greater than \(x_{i-1}\).
By ignoring those \(b_i\) and \(x_i\), the problem can be reduced to the case \((x_i)\) is increasing. Here, the conditions imposed on \(a_i\) and \(b_j\) can be expressed as follows.
- One of \(a_1, \ldots, a_L, b_1\) is equal to \(x_1\).
- One of \(a_1, \ldots, a_L, b_1, b_2\) is equal to \(x_2\).
- One of \(a_1, \ldots, a_L, b_1, b_2, b_3\) is equal to \(x_3\).
- \(\vdots\)
Then, by considering which of the \(a_i\) and \(b_j\) is equal to \(x_1, x_2, \ldots\) in this order, one can see that there are \((L+1)^{R}\) initial states. In the original problem, the left set is simply a sequence, so the answer gets multiplied by \(L!\).
Sample submission
posted:
last update: