FDIVGAME - Editorial

PROBLEM LINK:

Contest
Practice

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):

G(n) = \begin{cases} 0 & \text{if $n = 0$} \\ 1 & \text{if $n = 1$} \\ 2 & \text{if $n \in \\{2,3\\}$} \\ 3 & \text{if $n \in \\{4,5\\}$} \\ G(\lfloor n/12 \rfloor) & \text{if $n \ge 6$} \end{cases}

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:

\begin{array}{r|rrrrrrrrrrrrrrr} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 \\ \hline G(n) & 0 & 1 & 2 & 2 & 3 & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 2 \end{array}

To write it more compactly, let’s express it as a sequence of runs:

\begin{array}{r|r} \text{$n$ range} & G(n) \\ \hline [0,1) & 0 \\ [1,2) & 1 \\ [2,4) & 2 \\ [4,6) & 3 \\ [6,12) & 0 \\ [12,24) & 1 \\ [24,48) & 2 \\ [48,72) & 3 \\ [72,144) & 0 \\ [144,288) & 1 \\ [288,576) & 2 \\ [576,864) & 3 \\ [864,1728) & 0 \\ [1728,3456) & 1 \\ [3456,6912) & 2 \\ [6912,10368) & 3 \\ [10368,20736) & 0 \end{array}

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:

\begin{array}{r|r} \text{$n$ range} & G(n) \\ \hline [0,1) & 0 \\ [1,2) & 1 \\ [2,4) & 2 \\ [4,6) & 3 \\ [6,12) & 0 \\ [1\cdot 12,2\cdot 12) & 1 \\ [2\cdot 12,4\cdot 12) & 2 \\ [4\cdot 12,6\cdot 12) & 3 \\ [6\cdot 12,12\cdot 12) & 0 \\ [1\cdot 12^{2},2\cdot 12^{2}) & 1 \\ [2\cdot 12^{2},4\cdot 12^{2}) & 2 \\ [4\cdot 12^{2},6\cdot 12^{2}) & 3 \\ [6\cdot 12^{2},12\cdot 12^{2}) & 0 \\ [1\cdot 12^{3},2\cdot 12^{3}) & 1 \\ [2\cdot 12^{3},4\cdot 12^{3}) & 2 \\ [4\cdot 12^{3},6\cdot 12^{3}) & 3 \\ [6\cdot 12^{3},12\cdot 12^{3}) & 0 \end{array}

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
\begin{aligned} & a_1 \oplus a_2 \oplus \ldots \oplus a_i' \oplus \ldots \oplus a_N\\ &= (a_1 \oplus a_2 \oplus \ldots \oplus a_i \oplus \ldots \oplus a_N) \oplus a_i \oplus a_i'\\ &= 0 \oplus a_i \oplus a_i'\\ &= a_i \oplus a_i' \end{aligned}
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)

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester

3 Likes

Is this classified as an ‘easy’ problem? I thought it was pretty hard and of course I’ve never heard of the Sprague-Grundy theorem.

1 Like

Between Player A and B,if SG Theorum says Player A wins,then does it means that its 100% guaranteed that player A will actually win or the Theorum just tell which player is mostly likely to win?

@shadab_123 If SG theorem says Player A wins, then YES it’s 100% guaranteed that player A actually wins! That’s why it’s “theorem”. :slight_smile:

How can it be possible that code runs perfectly fine on Codechef’s IDE but on submitting the same code for the particular problem it shows wrong answer. :confused: What might be the reason for not accepting the answer? :slight_smile:

calculating G(n) was the tough part… if u know sprague-Grundy theorem…

Short problem analysis for all SNCKQL16 problems: SnackDown Online Qualifier 2016 – aleigorithms

1 Like

Hi
I did exactly the short version of the problem.
https://www.codechef.com/viewsolution/10227452
I still got WA during contest.
Can someone please help?
-My first time for any coding competition

can someone explain how grundy numbers are calculated for this problem??

@salgarkarap

  while(a>12){
    a=a/12;
  }

I think it should be: while(a>=12)

[Editorialist][1] Excellent explanation…
[1]: kevinsogo | CodeChef User Profile for Kevin Atienza | CodeChef

2 Likes

@tony_hager
It still doesn’t work.

Great editorial!!

Yeah, I think it should be medium.

It means that if both players play optimally then player A is guaranteed to win.

1 Like