Editorial for COI '10 #1 Sort


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.

The most important observation is that there exists a solution in which at most two cyclic swaps are needed. We can divide the solution into a few separate cases:

  1. Starting array is sorted – in this case, there is no need for any swap.
  2. One swap is enough – If there is number a at the position P in starting array and in position a there is number b, at position b number c, …, at position z there is number P, then this configuration is called interesting. For example, starting array [5, 4, 1, 3, 2] is one big interesting configuration. In this case, only one swap is necessary.
  3. Two swaps are enough – it is easy to show that starting array can be partitioned into a finite number of interesting configurations (or subsets). If we make a cyclic swap with one number from every interesting subset, they all will combine into one big interesting configuration for which is then only one swap needed.

Comments

There are no comments at the moment.