Editorial for COCI '13 Contest 2 #3 Slom
Submitting an official solution before solving the problem yourself is a bannable offence.
Given the current word, it is easy to reconstruct what that word looked like before one blink. Let's call it a reverse blink. We can find the initial word by repeating the reverse blink times. This solution is of the complexity
, which is good enough to gain
of points.
After a bit of scribbling on paper, it is easily noticed that the reverse blinking is periodical, meaning that after reverse blinks, the word will transform into the initial form. Hence, if we repeat the reverse blink
times, it is the same as we repeated it just
times.
The solution requires only finding the number (which can be done by simply repeating the reverse blink until the word is transformed into the initial form) and then repeat the reverse blink
times.
It is shown that is always less than
, meaning the total complexity of this algorithm is at most
, which is fast enough for
of points.
Comments