Industrial Nim

Observation 1

Strip away the industrial flavor text, and this is just Nim. Every dumper is a pile whose size is the number of stones in it.

So by Bouton’s theorem:

• if the xor of all pile sizes is $0$, the position is losing for the first player;
• otherwise it is winning.

So the answer is determined by

$$X = \bigoplus_{i=1}^{n} \left(x_i \oplus (x_i+1) \oplus \cdots \oplus (x_i+m_i-1)\right).$$

If $X \neq 0$, print tolik, else print bolik.

The only real problem is computing those huge consecutive xors without doing something stupid like iterating $10^{16}$ times. That would be... ambitious.

Observation 2: xor of a consecutive range

Define

$$pref(t)=0\oplus1\oplus2\oplus\cdots\oplus t.$$

Then for any $l \le r$,

$$l\oplus(l+1)\oplus\cdots\oplus r = pref(r)\oplus pref(l-1).$$

Why? Because everything from $0$ to $l-1$ appears twice and cancels in xor.

So quarry $i$ contributes

$$g_i = pref(x_i+m_i-1) \oplus pref(x_i-1).$$

Now we just need $pref(t)$ in $O(1)$.

Observation 3: the $pref(t)$ pattern

This is the classic xor-prefix pattern. Compute a few values:

$$\begin{aligned} pref(0)&=0 \\ pref(1)&=1 \\ pref(2)&=3 \\ pref(3)&=0 \\ pref(4)&=4 \\ pref(5)&=1 \end{aligned}$$

The answer depends only on $t \bmod 4$:

$$pref(t)= \begin{cases} t,& t\equiv 0 \pmod 4,\\ 1,& t\equiv 1 \pmod 4,\\ t+1,& t\equiv 2 \pmod 4,\\ 0,& t\equiv 3 \pmod 4. \end{cases}$$

One way to remember it: xor over every full block of four numbers vanishes:

$$(4k)\oplus(4k+1)\oplus(4k+2)\oplus(4k+3)=0.$$

So only the leftover tail matters.

Algorithm

For each quarry:

1. Let $l=x_i, \quad r=x_i+m_i-1.$
2. Compute $g_i = pref(r)\oplus pref(l-1).$
3. Accumulate $X \mathrel{\hat{=}} g_i.$

At the end:

• if $X \neq 0$, output tolik;
• otherwise output bolik.

Why this is correct

We can package the proof into three tiny lemmas.

Lemma 1

A Nim position is losing iff the xor of all pile sizes is $0$.

This is the standard theorem for normal-play Nim.

Lemma 2

For any $l \le r$,

$$l\oplus(l+1)\oplus\cdots\oplus r = pref(r)\oplus pref(l-1).$$

Proof.

$$pref(r)=0\oplus1\oplus\cdots\oplus(l-1)\oplus l\oplus\cdots\oplus r.$$

Xor this with

$$pref(l-1)=0\oplus1\oplus\cdots\oplus(l-1),$$

and the common prefix cancels. Done.

Lemma 3

For every $t \ge 0$,

$$pref(t)= \begin{cases} t,& t\equiv 0 \pmod 4,\\ 1,& t\equiv 1 \pmod 4,\\ t+1,& t\equiv 2 \pmod 4,\\ 0,& t\equiv 3 \pmod 4. \end{cases}$$

Proof. Check the first four values, then note the pattern repeats because each block of four consecutive integers xors to $0$.

From Lemma 2 and Lemma 3, each quarry’s contribution is computed correctly in $O(1)$. From Lemma 1, the final xor decides the winner. So the algorithm is correct.

Complexity

For each of the $n$ quarries we do only constant work.

• Time: $O(n)$
• Extra memory: $O(1)$

That’s it. The whole problem is basically “remember the xor-prefix formula and don’t panic because the numbers look huge.”