PROBLEM LINK:
Author: Kevin Atienza
Testers: Sergey Kulik and Vasya Antoniuk
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Easy
PREREQUISITES:
Game theory, Combinatorial game theory, Sprague-Grundy theorem
PROBLEM:
A game is played by two players with N integers A_1, A_2, \ldots, A_N. On his/her turn, a player selects an integer, divides it by 2, 3, 4, 5 or 6, and then takes the floor. If the integer becomes 0, it is removed. The last player to move wins. Which player wins the game?
QUICK EXPLANATION:
The solution uses the Sprague-Grundy theorem. Define G(n) as the following (recursively):
If the bitwise XOR of G(A_1), G(A_2), \ldots, G(A_N) is 0, then the second player wins (Derek), otherwise the first player wins (Henry).
EXPLANATION:
This is an example of an impartial game played under normal play condition, so the Sprague-Grundy theorem applies. The Sprague-Grundy theorem states that every such game is equivalent to a nimber. We can look at each A_i as a game independent of the other values, and the game itself as the sum of these N games. So, the theorem implies that every integer A_i can be replaced by a pile of nim of a certain size, and winning positions are preserved, i.e., winning positions are converted into winning positions, and losing positions are converted into losing positions.
To be more specific, we will convert the game into a game of nim with N piles, where the size of the i th pile is the nimber that is equivalent to A_i. Letâs call this size G(A_i). The proof of the theorem implies that G(n) is equal to the smallest nonnegative integer that is not equal to G(n') for any n' that is a successor of the game, i.e. n' \in \{\lfloor n/2\rfloor, \lfloor n/3\rfloor, \lfloor n/4\rfloor, \lfloor n/5\rfloor, \lfloor n/6\rfloor \}. In other words, G(n) is the minimum excluded value of the set \{G(\lfloor n/2\rfloor), G(\lfloor n/3\rfloor), G(\lfloor n/4\rfloor), G(\lfloor n/5\rfloor), G(\lfloor n/6\rfloor) \}. Since the integer 0 is always removed, we can set G(0) = 0.
But recall that a nim position is winning if and only if the bitwise XOR of the sizes of the piles is nonzero! Thus, in the original game, the first player is winning if the bitwise XOR of the numbers G(A_1), G(A_2), \ldots, G(A_N) is not zero. Thus, we can answer the problem if we can compute G(n) for any n.
If youâre unfamiliar with Sprague-Grundy theorem, we will explain in the appendix why the original game is equivalent to the nim game with pile sizes G(A_1), G(A_2), \ldots, G(A_N).
Computing G(N)
We can easily compute G(N) by definition:
def G(n):
if n == 0:
return 0
else:
return mex({G(n/2), G(n/3), G(n/4), G(n/5), G(n/6)})
def mex(s):
value = 0
while s contains value:
value++
return value
Unfortunately, this is very slow, because each call to G(n) needs five recursions! This easily blows up quickly, and youâll find that it takes a really long time even for G(10^8). For G(10^{18}) thereâs no hope.
We can optimize this by memoizing G(n), that is, storing previously computed values so they only need to be computed once. This solution actually makes computing a single value of G easier; G(10^{18}) now finishes instantly! Sadly though, doing this N = 100 times for T = 1000 cases is still too slow. So how do we compute G much more quickly?
Letâs look at the sequence G(0), G(1), G(2), G(3), \ldots first. Here is the sequence:
To write it more compactly, letâs express it as a sequence of runs:
Where [x,y) denotes the set \{n \in \mathbb{Z} : x \le n < y\}. Notice something interesting if we express the range bounds another way:
Hmmm. It seems that the sequence \{G(n)\} actually follows a simple pattern! Namely:
- G(0) = 0
- If n \in [12^k, 2\cdot 12^k), then G(n) = 1.
- If n \in [2\cdot 12^k, 4\cdot 12^k), then G(n) = 2.
- If n \in [4\cdot 12^k, 6\cdot 12^k), then G(n) = 3.
- If n \in [6\cdot 12^k, 12\cdot 12^k), then G(n) = 0.
But is this true in general? And how do we prove that? Well, it turns out that you can easily prove this by induction:
- For the base case, you can easily compute G(n) for n < 12 by hand to see that the statement is correct.
- For the first case, assume n\in [12^k, 2\cdot 12^k). Then \lfloor n/2 \rfloor \in [6\cdot 12^{k-1}, 12\cdot 12^{k-1}), and G(\lfloor n/2 \rfloor) = 0 by induction, which implies that G(n) \ge 1. On the other hand, G(\lfloor n/j \rfloor) cannot be equal to 1 because \lfloor n/j \rfloor is always in the range [2\cdot 12^{k-1}, 12\cdot 12^{k-1}), and by induction G(\lfloor n/j \rfloor) \not= 1. This implies that 1 is the minimum excluded value, and G(n) is actually 1.
- For the second case, assume n \in [2\cdot 12^k, 4\cdot 12^k). Then we can similarly show that G(\lfloor n/2\rfloor) = 1 and G(\lfloor n/4 \rfloor) = 0, which implies that G(n) \ge 2. On the other hand, G(\lfloor n/j \rfloor) cannot be equal to 2 because \lfloor n/j \rfloor is always in the range [4\cdot 12^{k-1}, 2\cdot 12^k), and by induction G(\lfloor n/j \rfloor) \not= 2. This implies that 2 is the minimum excluded value, and G(n) is actually 2.
- The third and fourth cases can be proven with similar arguments as above.
So now we have another way to compute G(n):
def G(n):
if n == 0:
return 0
k = 0
while 12**(k+1) > n: // '**' is exponentiation
k += 1
q = n / 12**k
if q < 2:
return 1
if q < 4:
return 2
if q < 6:
return 3
return 0
This is much faster than before and is actually fast enough to solve the problem!
We can actually implement G(n) another way by noticing that G(n) = G(\lfloor n/12 \rfloor):
G_small = [0,1,2,2,3,3,0,0,0,0,0,0]
def G(n):
return (if n < 12 then G_small[n] else G(n/12))
This has the same running time as the previous G(n) but is easier to type!
The time complexity of computing G(n) is is O(\log_{12} n) = O(\log n), so the running time of the overall algorithm is O(N \log A_\max), or more tightly, O(\sum_{i=1}^N \log A_i).
Appendix: Equivalence to nim
If youâre unfamiliar with Sprague-Grundy theorem, here weâll try to explain why the original game with the integers [A_1, A_2, \ldots, A_N] is equivalent to the nim game with pile sizes [G(A_1), G(A_2), \ldots, G(A_N)]. Here, âequivalentâ means that the first game is a winning position if and only if the second game is also a winning position.
Recall that in nim, a move consists of choosing a pile and removing a nonzero number of things from the pile. You can also look at it as choosing a pile and then replacing it with a strictly smaller pile. Theyâre clearly equivalent, but thinking of it using the latter way will make it easier to understand this section.
Suppose weâre playing nim with pile sizes [a_1, a_2, \ldots, a_N]. Itâs a well-known fact that this is a winning position if and only if a_1 \oplus a_2 \oplus \ldots \oplus a_N is nonzero, where \oplus denotes bitwise XOR. But why is this true? Hereâs why.
- If a_1 \oplus a_2 \oplus \ldots \oplus a_N = 0, then any move will make the bitwise XOR nonzero. To see why, suppose your move was to reduce the i th pile from a_i to a_i'. Then the new bitwise XOR will be equal to
which is nonzero because $a_i \not= a_i'$.
- If a_1 \oplus a_2 \oplus \ldots \oplus a_N \not= 0, then there exists a move that will make the bitwise XOR equal to 0. To show this, let x = a_1 \oplus a_2 \oplus \ldots \oplus a_N, and let k be the largest 1 bit in x. Thus, there exists an i such that the k th bit of a_i is 1. (Otherwise, the k th bit of x cannot be 0.) The move is to replace a_i with a_i \oplus x. Clearly, doing that move will make the bitwise XOR 0, but itâs only a valid nim move if a_i \oplus x < a_i. But this is true because the largest bit where a_i \oplus x and a_i differ is the k th bit, the k th bit of a_i is 1, and the k th bit of a_i \oplus x is 0. Thus, a_i \oplus x < a_i!
Now that we know the strategy for nim, letâs now prove why the original game is equivalent to the nim game [G(A_1), G(A_2), \ldots, G(A_N)]. Recall that G(n) = \operatorname{mex}\{G(\lfloor n/2\rfloor), G(\lfloor n/3\rfloor), G(\lfloor n/4\rfloor), G(\lfloor n/5\rfloor), G(\lfloor n/6\rfloor) \}, where \operatorname{mex}(S) is the smallest nonnegative integer not in S.
Clearly, any move in the nim game [G(A_1), G(A_2), \ldots, G(A_N)] corresponds to some move in the original game [A_1, A_2, \ldots, A_N] because of the way G(n) is defined: If G(n) = v, then every value v' < v can be obtained as G(\lfloor n/k\rfloor) for some k\in \{2,3,4,5,6\}. Thus, any move in the nim game can be simulated in the original game: Replacing G(n) with a smaller value v' is equivalent to dividing n by k so that G(\lfloor n/k\rfloor) = v'. Thus, we can also simulate a âwinning strategyâ in the nim game in the original game, if such a strategy exists. And if no such strategy exists, i.e., when G(A_1)\oplus G(A_2)\oplus\ldots\oplus G(A_N) = 0, then any move we make will yield a winning position for the next player.
Unfortunately, some moves in the original game actually increase the G-value, and such moves donât have equivalents in the nim game! But thatâs no problem, because we can show that such moves donât matter:
- If youâre in a losing position and perform a move that increases the G-value, then the enemy can respond by replacing that new G-value with the original one. In other words, if G(n) = v and you move so that the G-value becomes v' > v, then the enemy can move so it becomes v again. Such a move exists by our definition of G(n). But weâre now in a position equivalent to the original one!
- If youâre in a winning position, then thereâs no point for you in moving so that the G-value increases. Simply follow the strategy in the equivalent nim game, and if the opponent performs a move that increases the G-value, just respond by replacing it back!
Time Complexity:
O(N\log A_\max)
What might be the reason for not accepting the answer?