Official

E - XY Game Editorial by evima

Since this game is a two-player zero-sum finite deterministic perfect information game, it suffices to find the Grundy number for each pile. Hereafter, we consider finding the Grundy number for a pile with \(v\) stones.

Also, when \(v\) is a multiple of \(X\) or \(Y\), by considering Alice’s first move, we can reduce it to a problem (with at most two cases) where \(v\) is neither a multiple of \(X\) nor a multiple of \(Y\). Therefore, hereafter we consider cases where \(v\) is neither a multiple of \(X\) nor a multiple of \(Y\).

When \(Y\) is a multiple of \(X\), there is a simple pattern. Specifically, the Grundy number can be calculated as follows:

  • When \(X\equiv 0\bmod 3\):
    • The Grundy number is \((v - 1) \bmod 3\).
  • When \(X\equiv 1\bmod 3\):
    • The Grundy number is \(((v \bmod X) - 1) \bmod 3 \).
  • When \(X\equiv 2\bmod 3\):
    • When \(v \equiv 0\bmod 3\), the Grundy number is \(2\).
    • Otherwise, the Grundy number is \((((v \bmod X) - 1) \bmod 3) \oplus (\left\lfloor\frac vX \right\rfloor \bmod 2)\).

Note that we are not considering situations where \(v\) is a multiple of \(X\). The proof can be done using mathematical induction.

Cases where \(v < Y\) are essentially the same situation as above, so we can calculate the Grundy number based on the above formula. Hereafter, we only consider situations where \(Y\) is not a multiple of \(X\) and \(Y < v\).

Let \(S\) be the set of unreachable numbers of stones, that is, \(S=\lbrace nX | n \in \mathbb{N}_{\geq 0}\rbrace \cup\lbrace nY | n \in \mathbb{N}_{\geq 0}\rbrace \).

For \(a \le b \), when \(a,b\in S\) and \(a+1,a+2,\ldots,b-1 \not \in S\), we call \((a,b)\) an interval. Also, we define the length of the interval as \(b-a\) (note that this is off by \(1\) from the actual length), and the value of the interval as \((b - a) \bmod 3\).

First, the Grundy numbers within an interval are sequentially 012012… or 102102…

For example, when \(X=5,Y=7\), the Grundy numbers are sequentially as follows (positions that are multiples of \(X\) or \(Y\) are represented by x):

0120x1x01x012xx0120xx012x01x0x1021x…

In each interval, 0120 1 01 012 0120 012 01 0 1021 the Grundy numbers are arranged regularly.

Also, the Grundy number arrangement of the next interval can be obtained from the Grundy number arrangement of a certain interval as follows:

  • When the value of the interval is \(0\): The arrangement remains the same. That is, if it is 012…, it remains 012…, and if it is 102…, it remains 102…
  • When the value of the interval is \(1\): It becomes 012… That is, whether it is 012… or 102…, it becomes 012…
  • When the value of the interval is \(2\): The arrangement is reversed. That is, if it is 012…, it becomes 102…, and if it is 102…, it becomes 012…

In other words, to find the Grundy number for a pile of \(v\) stones, we need to find the nearest interval with value \(1\) to the left of that position and count how many intervals with value \(2\) there are to the right of it.

To calculate the Grundy number more quickly, we consider calculating it by the following method:

  • Consider dividing into intervals by multiples of \(X\).
  • Furthermore, make cuts at multiples of \(Y\) to complete the interval arrangement. Since \(X < Y\), there is at most one multiple of \(Y\) in an originally existing interval.

By using this idea, for example, when \(X << Y\) holds, we can collectively process places where many intervals of length \(X\) continue. We will solve this problem based on this idea.

1. When \(X\equiv 0\bmod 3\)

If \(Y\equiv 0 \bmod 3\), the Grundy number is \((v - 1) \bmod 3 \). Hereafter, we consider cases where \(Y \not\equiv 0\bmod 3\).

The values of the two intervals divided by \(Y\) are one of 0 / 0, 1 / 2, or 2 / 1. In the case of 0 / 0, there is no particular change, but in other cases, an interval with value \(1\) always appears, so we can calculate the Grundy number from there as a starting point.

If the values of the two intervals divided by \(kY\) are 0 / 0, then the values of the two intervals divided by \((k-1)Y\) are other than 0 / 0, so we should check the two largest ones.

2. When \(X\equiv 1\bmod 3\)

When \(Y > 2X\) or \(Y\equiv 0 \bmod 3 \), at least one of four consecutive intervals has value \(1\). Therefore, we consider cases where \(Y < 2X\) and \(Y\not\equiv 0\bmod 3\).

Since the value of the interval divided only by \(X\) before being divided by \(Y\) is \(1\), if \(\displaystyle \frac{Y}{X}\) is somewhat larger than \(1\), we can reach an interval with value \(1\) at an early stage by simulating naively. When \(\displaystyle \frac{Y}{X}\) is close to \(1\), the length on the left side of the interval divided by \(Y\) gradually decreases, so by calculating its destination and skipping collectively, we can quickly reach an interval with value \(1\).

3. When \(X\equiv 2\bmod 3\)

The values of the two intervals divided by \(kY\) are one of 0 / 2, 1 / 1, or 2 / 0. Since the left end of the left interval divided by \(kY\) is \(\displaystyle X\left\lfloor \frac {kY}X \right\rfloor\), the condition for the values of the two intervals divided by \(kY\) to be 1 / 1 can be written as \(\displaystyle kY - X\left\lfloor \frac {kY}X \right\rfloor \equiv 1\bmod 3\). Letting \(\displaystyle c=\left\lfloor \frac YX \right\rfloor\), the condition becomes \(\displaystyle (Y+c)k +\left\lfloor \left(\frac {Y}X-c\right)k \right\rfloor \equiv 1\bmod 3\).

3 - A. When \(Y+c\equiv 0\bmod 3\)

The condition becomes \(\displaystyle \left\lfloor \left(\frac {Y}X-c\right)k \right\rfloor \equiv 1\bmod 3\). Since \(\displaystyle 0 < \frac {Y}X-c < 1\) holds, the maximum \(k\) satisfying the condition and \(\displaystyle kY < v\) can be easily calculated.

3 - B. When \(Y+c\equiv 1\bmod 3\)

The condition becomes \(\displaystyle k+\left\lfloor \left(\frac {Y}X-c\right)k \right\rfloor \equiv 1\bmod 3\).

By searching sequentially for \(k\) satisfying the condition from the maximum possible value for \(k\) (around \(\displaystyle v/Y\)), if not found, the value of \(\displaystyle \left(k+\left\lfloor \left(\frac {Y}X-c\right)k \right\rfloor \right) \bmod 3\) repeats \(0\) and \(2\). Therefore, by setting \(k=2k'+k_0\) (\(k_0 \in \lbrace 0,1\rbrace\)) and dividing by the parity of \(k\), we should calculate the boundaries where the value of \(\displaystyle \left\lfloor \left(\frac {2Y}X-2c-1\right)k'+\left(\frac {Y}X-c\right)k_0\right\rfloor \bmod 3\) changes for each.

3 - C. When \(Y+c\equiv 2\bmod 3\)

The condition becomes \(\displaystyle \left\lfloor \left(\frac {Y}X-c-1\right)k \right\rfloor \equiv 1\bmod 3\). Since \(\displaystyle -1 < \frac {Y}X-c-1 < 0\) holds, the maximum \(k\) satisfying the condition and \(\displaystyle kY < v\) can be easily calculated.

From the above discussion, we can see that the Grundy number for a pile of \(v\) stones can be calculated in \(O(1)\).

By implementing the above appropriately, we can solve this problem. The time complexity is \(O(N)\) per test case.

Be careful with handling endpoints and such in the implementation.

posted:
last update: