Editorial for Arcadia Computing Contest 1 P4 - Cyclic Sorting - Olympiads Online Judge

Editorial for Arcadia Computing Contest 1 P4 - Cyclic 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: kevlu8

Let's define a decrease as a point where $a_{i} > a_{i+1}$ ~a_{i} > a_{i+1}~.

Maintain a set data structure, keeping track of the position of decreases (including the last and first element of the array). Then. for every query, update the set. If the number of decreases is exactly $0$ ~0~ or $1$ ~1~, it is possible. Otherwise, it is not.

If it is equal to $1$ ~1~, the number of shifts necessary is simply $\min(d, n-d)$ ~\min(d, n-d)~ where $d$ ~d~ denotes the index of the decrease.

Comments

There are no comments at the moment.