Editorial for Yet Another Contest 8 P1 - Permutation Sorting

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Josh

Subtask 1

If the permutation is already sorted, then no operations are necessary, and the answer is $0$ ~0~.

Otherwise, we must sort exactly one subarray. Observe that the elements which are not part of this subarray form some prefix and suffix of the original permutation. Thus, it suffices to count the largest prefix and suffix which contain the correct elements, and count the number of remaining elements.

Time complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~

Observation

Each index does not need to be involved more than one operation. Otherwise, we could take two operations which include this index, and merge their intervals to form a single operation with a smaller cost. Thus, it suffices to determine whether each index should be included in an operation or not. For any two adjacent indices which are both included in an operation, we would include them in the same operation.

Subtask 2, Alternative 1

For any index $X$ ~X~ with $P_X \ne X$ ~P_X \ne X~, all of the cells between $X$ ~X~ and $P_X$ ~P_X~ (inclusive) must be included in at operation, in order for this element to end up at the correct position. If we mark these cells for all values of $X$ ~X~, then the number of cells marked at least once is the answer.

Time complexity: $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~

Subtask 2, Alternative 2

An index $X$ ~X~ does not need to be included in an operation if the following criteria holds:

$X = P_X$ ~X = P_X~
$P_Y < X$ ~P_Y < X~ for all $Y < X$ ~Y < X~

It suffices to check this criteria naively for all $X$ ~X~.

Time complexity: $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~

Subtask 3, Alternative 1

We can optimize alternative 1 of subtask 2. Construct a list of all intervals $[\min(X, P_X), \max(X, P_X)]$ ~[\min(X, P_X), \max(X, P_X)]~ for all indices $X$ ~X~ with $P_X \ne X$ ~P_X \ne X~. The answer is the size of the union of these intervals. We can use a standard interval merging algorithm, or use a difference array.

Time complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~ or $\mathcal{O}(N\log{N})$ ~\mathcal{O}(N\log{N})~

Subtask 3, Alternative 2

We can optimize alternative 2 of subtask 2. Simplify the second condition as $\max(P_1, P_2, \dots, P_{X-1}) < X$ ~\max(P_1, P_2, \dots, P_{X-1}) < X~, or equivalently since $X = P_X$ ~X = P_X~, $\max(P_1, P_2, \dots, P_X) = X$ ~\max(P_1, P_2, \dots, P_X) = X~. We can then keep a running prefix maximum as we loop through all indices $X$ ~X~.

Time complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~

Comments

There are no comments at the moment.