Editorial for COCI '14 Contest 7 #2 Kriza
Submitting an official solution before solving the problem yourself is a bannable offence.
A naive approach comes down to simulating each attempt at unlocking the door. Given the fact that Sisyphus has to move at most keys to the other side when facing each door, having visited doors in total, the complexity of such algorithm is which is enough for of points on this task.
We need to notice that, when facing the door, the rightmost key on the pendant unlocks door and that there is a constant number of keys on the pendant between keys marked with and . Then it's to find out how many misplaced keys Sisyphus has placed in the door with a fixed label . This leads us to a solution of the complexity which is enough for of points on this task.
Finally, we should notice that different states of keys on the pendant are necessarily a part of a cycle of length . If we fill out an array , where tells us how many misplaced keys Sisyphus has placed starting from the first to the door (for ), we can answer the given question in . Filling out array is done in the complexity , which is enough for of points on this task.
Additionally, we need to be careful about the first unlocking. In other words, the transition from the initial state to the state after the first door that could, but doesn't have to, be a part of the cycle described in the previous paragraph. Also, we need to notice that the solution can overflow a 32-bit integer.
Comments