A Game of Cards

Let us define a few things first.

• The initial state array is denoted as A.
• The final state array is denoted as B.
• |P| is the size of an array P.
• Pi is the prefix of length i of the array P. Here, 1 ≤ i ≤ |P|.
• P[i] denotes the ith element of the array P. Here, 1 ≤ i ≤ |P|.
• Let C[i][j] denote the maximum value of the elements A[k] where i<k<j. This can be precalculated.
• We write A -> B if it is possible to reach state B from state A using the given move.

Now, let's split the problem in two parts.

• whether there is a solution
• finding the lexicographically smallest solution

First we look for the existence of a solution.

Now let A[i] = B[j]. We define OK[i][j] = 1 if Ai -> Bj , and OK[i][j] = 0 otherwise. We also define Last[i][j] to be the highest positive value k ≤ i such that OK[k][j] = 1, or -1 if no such k exists.

For simplicity, we add a small negative value in the beginning and the end of both the arrays A and B. So, OK[0][0] = 1, OK[0][i] = 0 for i>0. Last[0][0] = 0 and Last[0][i] = -1 for i>0. A has N+2 elements now, B has M+2. We will, obviously, be using 0-based indexing here.

Now, the following code can be used to calculate OK[i][j] and Last[i][j] for a specific i>0 and all j>0 in O(M) time given Last[i-1][j] has already been calculated for all j.

for (int j=1; j<=m+1; j++) {
    if (A[i] != B[j]) continue;
    if (Last[i-1][j-1] == -1) continue;
    int k = Last[i-1][j-1];
    if (C[k][i] < A[k] || C[k][i] < A[i]) {
        OK[i][j] = 1;
    }
}
for (int j=1; j<=m+1; j++) {
    if ( OK[i][j] == 1 ) {
         Last[i][j] = i;
     }
     else {
         Last[i][j] = Last[i-1][j];
     } 
}

We repeat this process for all i ≤ n+1. After this, if Last[n+1][m+1] = n+1, a solution exists. Otherwise it doesn't.

We move on to finding the lexicographically smallest solution.

Let Prev[i][j] = Last[i-1][j-1] when OK[i][j] = 1, Prev[i][j] = -1 otherwise.

Let sol1 and sol2 be two solution arrays of length m such that

• OK[sol1[i]][i] = 1 for 0 ≤ i ≤ m+1
• Prev[sol1[i]][i] = sol1[i-1]
• OK[sol2[i]][i] = 1 for 0 ≤ i ≤ m+1
• Prev[sol2[i]][i] = sol2[i-1]

Let k <= m+1 be such a value for which

• sol1[k] != sol2[k]
• sol1[i] = sol2[i] for i < k
• sol1[k] < sol2[k]

Now, this implies that A[Prev[sol1[k]][k]] > C[Prev[sol1[k]][k]][sol2[k]]. Therefore, sol2 would produce a lexicographically smaller move list.

We simply have to trace back from the m+1th element to the first element using the Prev array to find the optimal solution array. From there, the move list can be generated in O(N2). The judge code has the details.

Judge solution: Link
Complexity: O(N2)
Alternate: Sourav Sen Tonmoy