Editorial for Baltic OI '03 P5 - Lamps - DMOJ: Modern Online Judge

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$ ~3~ solutions with different complexity.

Solution 1

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

Solution 2

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

If the same pattern occurs at different moments $t_1$ ~t_1~ and $t_2$ ~t_2~, then the patterns repeat with cycle of length $t_2-t_1$ ~t_2-t_1~. Knowing that, the pattern at the moment $M$ ~M~ is equal to the pattern at the moment $t_1+(M-t_1) \bmod (t_2-t_1)$ ~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$ ~N~ is $2^N$ ~2^N~, the number of hash values is exponential to $N$ ~N~. This method has a running time complexity $\mathcal O(N \times 2^N)$ ~\mathcal O(N \times 2^N)~, which does not depend on $M$ ~M~. But it also requires $\mathcal O(2^N)$ ~\mathcal O(2^N)~ of memory.

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

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

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

Proof. Skipped, but not difficult.

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

Let $L(l, t)$ ~L(l, t)~ denote the state of lamp $l$ ~l~ at moment $t$ ~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}$ ~\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$ ~j = 2^k~, and bearing in mind that $C(2^k, l)$ ~C(2^k, l)~ is even and $\texttt{XOR}(a, a) = 0$ ~\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$ ~2~ lamps $2^k$ ~2^k~ seconds before, and can be computed with a single $\texttt{XOR}$ ~\texttt{XOR}~.

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

Comments

There are no comments at the moment.