Editorial for COCI '14 Contest 7 #2 Kriza


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.

A naive approach comes down to simulating each attempt at unlocking the door. Given the fact that Sisyphus has to move at most N keys to the other side when facing each door, having visited K doors in total, the complexity of such algorithm is \mathcal O(NK) which is enough for 40\% of points on this task.

We need to notice that, when facing the i^\text{th} door, the rightmost key on the pendant unlocks door i-1 and that there is a constant number of keys on the pendant between keys marked with i and j. Then it's \mathcal O(1) to find out how many misplaced keys Sisyphus has placed in the door with a fixed label i. This leads us to a solution of the complexity \mathcal O(K) which is enough for 60\% 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 N. If we fill out an array A[], where A[i] tells us how many misplaced keys Sisyphus has placed starting from the first to the i^\text{th} door (for i \le N), we can answer the given question in \mathcal O(1). Filling out array A[] is done in the complexity \mathcal O(N), which is enough for 100\% 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

There are no comments at the moment.