Editorial for COCI '22 Contest 3 #2 Dirigent


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.

For the first subtask, we can try breaking the circle at each position and then check whether it results in a sorted sequence. The complexity of such an approach is \mathcal{O}(qn^2).

For the second subtask, we can see that it is sufficient to try and break the circle at a position which will result in 1 being first in the sequence. In this approach, we check if the sequence is sorted only once and not n times. The complexity is, therefore, \mathcal{O}(qn).

For all points, let us focus on neighbours (all pairs of students that are holding hands). There are also n such pairs. Let us call a pair good if the one on the right (in the clockwise direction) has the bigger number and bad otherwise.

Observe that the condition from the task holds if and only if there is exactly 1 bad pair. For full points, we will try to maintain the number of bad pairs.

After each swap, at most 4 pairs of neighbours change, so we can easily maintain that number. The complexity of such an approach is \mathcal{O}(n+q) because we have to initially count the number of bad pairs and also update it after each swap.


Comments

There are no comments at the moment.