Editorial for Baltic OI '03 P5 - Lamps
Submitting an official solution before solving the problem yourself is a bannable offence.
This task has basically solutions with different complexity.
Solution 1
The first solution is to simply compute all the intermediate patterns. In this case, different states for each of the lamps must be computed, yielding an solution.
Solution 2
A standard approach to improve the solution (for smaller values of ) is to hash the pattern with some function. Then it can be easily checked (probably with complexity), whether the same pattern has ever occurred before.
If the same pattern occurs at different moments and , then the patterns repeat with cycle of length . Knowing that, the pattern at the moment is equal to the pattern at the moment .
The most intuitive hash function to use is to simply view the representation of the pattern as a binary number. Since the number of different patterns of length is , the number of hash values is exponential to . This method has a running time complexity , which does not depend on . But it also requires of memory.
However, since for most numbers , the maximum length of the cycle of patterns consisting of lamps is only a small fraction of , hash functions with less hash values can be used. For example, one could use only the states of fixed lamps, rather than the states of all lamps, when hashing the pattern. We believe that the most suitable values for are , as the array of elements should fit into the memory. However, for small values of , this seems to be enough. Although for most (if not all) numbers , the running time complexity is asymptotically less, than , we do not know any better bound.
Solution 3
The third solution is based on the fact that we do not need to calculate all the intermediate patterns, to get the one.
First of all, we need to prove the following lemma:
Lemma 1. For every prime and positive integers , , which satisfy , the binomial coefficient is divisible by .
Proof. Skipped, but not difficult.
Choosing , is thus an even number.
Let denote the state of lamp at moment .
Let denote
As the function is both commutative and associative, we can write:
Choosing , and bearing in mind that is even and , we get
thus the state of the lamp is determined by the states of lamps seconds before, and can be computed with a single .
Hence we only need to compute intermediate patterns to get the answer, therefore the time complexity is .
Comments