PROBLEM LINK:
Author: Sergey Kulik
Tester: Kamil Debowski
Editorialist: Pawel Kacprzak
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Permutations, constructive algorithms
PROBLEM:
For a given permutation P of numbers 1, 2, \ldots, N, such that for all i, P[i] \neq i, the goal of the problem is to transform P into another permutation P' such that P' has the smallest possible number of inversion. The only restriction is that we can do that using at most 2 \cdot N^2 moves, and each valid move is a swap of two adjacent elements of the permutation P[i], P[i+1], such that P[i] \neq i and P[i+1] \neq i+1.
Thus, the answer to the problem is a sequence of at most 2 \cdot N^2 valid moves transforming P into P' having the smallest possible number of inversions. Just to recall, inversion is a pair of indices i < j, such that P'[i] > P'[j].
QUICK EXPLANATION:
Observe within the given number of moves, the permutation with no inversions can always be constructed, i.e. the identity permutation for which for all i, P'[i] = i, by placing elements one after another to its final position using some rules starting from the smallest one.
EXPLANATION:
Subtask 1
In the first subtask, we know that N \leq 5, so one can try to generate all possible permutations using sequences of valid moves and return the one with the smallest number of inversions. In fact, this can be the first step towards observing how to convert constructively any permutation to the identity permutation within the given number of moves, which is exactly what we want to do in the second subtask.
Subtask 2
In the second subtask we have N \leq 50, so we want an explicit recipe on how to convert any permutation to identity permutation withing given number of moves. The idea is the following: we are going to first place number 1 to its place, then number 2 to its place and so on. Let’s assume that we have already placed K-1 numbers to their places and we want to move number K to its place now. We are not going to touch any of the already placed numbers from now. The only thing we have to be aware of is the situation when after placing K to its place, there exist two positions i, j such that K < i < j, and P'[j] = j, but P'[i] > j, in other words, number j is already in its place, but number P'[i] is not, and since it is greater than j, in order to move it to its position, we would have to make at least one move involving P'[j], but we cannot do that since this move is not allowed anymore. Having above observations in mind we can use the below constructive approach to place number K to its place:
Let’s assume that K is no in its place, otherwise, we are done. Thus, let i > K be the current position of K in the permutation. There are two cases to consider:
-
For all K-1 < j < i, P'[j] = j+1. In other words, all numbers to the left of position i (not counting the first K-1 elements placed in previous steps) are “one position to the left of their final positions”. In this case, we use consecutive swaps to swap positions i with i-1, then i-1 with i-2, \ldots, and finally K+1 with K. These swaps will result in not only number K on position K, but also all numbers K+1, K+2, \ldots, i on their positions.
-
There exists at least one index x, such that K-1 < x < i, such that P'[x] \neq x+1. Let j be the greatest such index. In this case we swap positions consecutively elements at positions: j with j+1, next j+1 with j+2, \ldots, and finally i-1 with i. This process gets rid of one number for which the condition from the first case does not hold and also moves K one place towards its final position.
Example
Let’s consider an example permutation P = [4, 3, 2, 5, 1]:
First, we want to move 1 to the first position. The condition from the first case does not hold, because P[3] \neq 4, so we perform consecutive swaps resulting in moving number 2 after 1: first we swap numbers 2 and 5, and next numbers 2 and 1, which results in P = [4, 3, 5, 1, 2].
Next, we still want to move 1 to its final position, and the condition from the first case still does not hold, because P[3] \neq 4, so we swap numbers 5 and 1 resulting in permutation P = [4, 3, 1, 5, 2]. After that, again the condition from the first step does not hold, because P[1] \neq 2 (notice that P[2] = 3). Thus we swap first numbers 4 and 3 and then numbers 4 and 1, which result in P = [3, 1, 4, 5, 2]. Next, we again have the second case, because P[1] \neq 2, so we swap numbers 3 and 1, which result in P = [1, 3, 4, 5, 2] and number 1 is placed on its final position.
Next step is to place number 2 to its final position. Notice that now the condition from the first case is fulfilled because all numbers standing before 2 not placed before to their positions fulfill the condition. So, we perform swaps moving 2 directly to its position, i.e. we swap numbers 2 and 5, then numbers 2 and 4 and finally numbers 2 and 3, which result in the final identity permutation P = [1,2,3,4,5] and we are done.
Moreover, it can be proven that the above construction does not use more than 2 \cdot N^2 moves. One helpful observation while proving is that in the first case using M consecutive moves we place exactly M elements to their final positions.
For implementation details please refer to author’s and tester’s solutions. Tester place numbers to their positions starting from the smallest 1, while author does it in the reverse order.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
Tester’s solution can be found here.