Editorial for Baltic OI '03 P5 - Lamps


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.

This task has basically 3 solutions with different complexity.

Solution 1

The first solution is to simply compute all the intermediate patterns. In this case, M different states for each of the N lamps must be computed, yielding an \mathcal O(NM) solution.

Solution 2

A standard approach to improve the solution (for smaller values of M) is to hash the pattern with some function. Then it can be easily checked (probably with \mathcal O(1) complexity), whether the same pattern has ever occurred before.

If the same pattern occurs at different moments t_1 and t_2, then the patterns repeat with cycle of length t_2-t_1. Knowing that, the pattern at the moment M is equal to the pattern at the moment t_1+(M-t_1) \bmod (t_2-t_1).

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 N is 2^N, the number of hash values is exponential to N. This method has a running time complexity \mathcal O(N \times 2^N), which does not depend on M. But it also requires \mathcal O(2^N) of memory.

However, since for most numbers N, the maximum length of the cycle of patterns consisting of N lamps is only a small fraction of 2^N, hash functions with less hash values can be used. For example, one could use only the states of k < N fixed lamps, rather than the states of all lamps, when hashing the pattern. We believe that the most suitable values for k are 20 \dots 24, as the array of 2^k elements should fit into the memory. However, for small values of N (N < 100), this seems to be enough. Although for most (if not all) numbers N, the running time complexity is asymptotically less, than \mathcal O(N \times 2^N), 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 M-1 intermediate patterns, to get the M^\text{th} one.

First of all, we need to prove the following lemma:

Lemma 1. For every prime p and positive integers k, l, which satisfy 1 < l < p^k, the binomial coefficient C(p^k, l) is divisible by p.

Proof. Skipped, but not difficult.

Choosing p = 2, C(2^k, l) is thus an even number.

Let L(l, t) denote the state of lamp l at moment t.

Let \texttt{XOR}(a_1 \times b_1, a_2 \times b_2, \dots, a_i \times b_i) denote

\displaystyle \bigoplus_{j=1}^i \bigoplus_{k=1}^{b_j} a_j = \underbrace{a_1 \oplus a_1 \oplus \dots \oplus a_1}_{b_1\text{ times}} \ \oplus \ \underbrace{a_2 \oplus a_2 \oplus \dots \oplus a_2}_{b_2\text{ times}} \ \oplus \dots \oplus \ \underbrace{a_i \oplus a_i \oplus \dots \oplus a_i}_{b_i\text{ times}}.

As the function \texttt{XOR} is both commutative and associative, we can write:

\displaystyle \begin{aligned}
L(n, n) &= \texttt{XOR}(L(n-1, n-1) \times 1, L(n, n-1) \times 1)\\
&= \texttt{XOR}(\texttt{XOR}(L(n-2, n-2) \times 1, L(n-1, n-2) \times 1), \texttt{XOR}(L(n-1, n-2) \times 1, L(n, n-2) \times 1))\\
&= \texttt{XOR}(L(n-2, n-2) \times 1, L(n-1, n-2) \times 2, L(n, n-2) \times 1)\\
&= \texttt{XOR}(L(n-3, n-3) \times 1, L(n-2, n-3) \times 3, L(n-1, n-3) \times 3, L(n, n-3) \times 1)\\
&= \texttt{XOR}(L(n-j, n-j) \times C(j, j), L(n-j+1, n-j) \times C(j, j-1), L(n-j+2, n-j) \times C(j, j-2), \dots, L(n-1, n-j) \times C(j, 1), L(n, n-j) \times C(j, 0))
\end{aligned}

Choosing j = 2^k, and bearing in mind that C(2^k, l) is even and \texttt{XOR}(a, a) = 0, we get

\displaystyle \begin{aligned}
L(n, n) &= \texttt{XOR}(L(n-2^k, n-2^k) \times C(2^k, 2^k), L(n-2^k+1, n-2^k) \times C(2^k, 2^k-1), L(n-2^k+2, n-2^k) \times C(2^k, 2^k-2), \dots, L(n-1, n-2^k) \times C(2^k, 1), L(n, n-2^k) \times C(2^k, 0))\\
&= \texttt{XOR}(L(n-2^k, n-2^k) \times 1, L(n, n-2^k) \times 1),
\end{aligned}

thus the state of the lamp is determined by the states of 2 lamps 2^k seconds before, and can be computed with a single \texttt{XOR}.

Hence we only need to compute \log M intermediate patterns to get the answer, therefore the time complexity is \mathcal O(N \log M).


Comments

There are no comments at the moment.