Editorial for Back To School '19: A Circular Game


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: Zeyu

Subtask 1

For the first subtask, we can try every possible spinner position and calculate the minimum time required to set all N spinners to this position. For any spinner, the shortest time will either be going clockwise or counter-clockwise depending on which direction takes less time.

Time Complexity: \mathcal{O}(NM)

Subtask 2

For the second subtask, one can observe that checking the current N spinner positions is enough to find the minimum time required. This is because we can classify the spinners into two groups: spinners that are faster going clockwise and spinners that are faster going counter-clockwise. For every change in the target position the total time changes in relation with the two groups, and thus the current spinner positions will lead to the optimal time.

Time Complexity: \mathcal{O}(N^2)

Subtask 3

For the third and final subtask, we can calculate the total time efficiently by reusing the previously calculated values. Going back to the two groups method, we can maintain the groups using a two-pointer approach after sorting the items. We can then calculate the new time by adding and subtracting the change in group sizes as we loop through all N candidates.

Time Complexity: \mathcal{O}(N \log N)


Comments

There are no comments at the moment.