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
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:
Each row must contribute exactly one value to a cycle.
Each cycle must alternate between first and second column values, so cycles must have even length.
Sort rows by the left value, and let be the permutation of the right column. We can only move:
To a larger value: i \to j if p[j] > p[i].
To the left: i \to j if j < i.
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:
Start at the leftmost element, move to the rightmost larger value, then to the smallest left value, repeat until reaching the rightmost element.
Pair remaining unused elements from left to right, and for each pair: Move left to the smaller element, then move to the larger element.
Finish the cycle by moving left to the first element.
This constructs the required cycles using exactly coins whenever all parts have even length.