Sorted Pairs#13015

Sorted Pairs (Editorial)

Author:

Roman Bilyi

Prepared by:

Yarema Stiahar

Solved by:

First to solve:

N/A

The answer is always at least , and it is always possible to achieve the goal in n+1 coins.

Constructive solution using n+1 coins for any input:

If there are two rows and such that

a[i][1] < a[j][1] \quad \text{and} \quad a[i][2] < a[j][2],

we can fix them with 2 coins by swapping and . Repeat this for all such pairs.

After this, for the remaining rows, a single cycle (see image) can fix all positions using k+1 coins.

Check if coins is possible:

Sort rows by the left value, and let be the permutation of the right column. We can only move:

If some prefix contains all the largest values, it cannot leave that prefix. Thus, the problem can be divided into parts. If any part has odd length, coins is impossible.

Constructive procedure. For each even-length part:

Finish the cycle by moving left to the first element.

This constructs the required cycles using exactly coins whenever all parts have even length.