CF 102319D - David vs David

We have a two-pile impartial game. A position is represented by the two pile sizes, say (x, y). On a turn, a player may remove any positive number of stones from exactly one pile.

codeforcescompetitive-programming

CF 102319D - David vs David

Rating: -
Tags: -
Solve time: 10m 25s
Verified: yes

Solution

Problem Understanding

We have a two-pile impartial game. A position is represented by the two pile sizes, say (x, y). On a turn, a player may remove any positive number of stones from exactly one pile. They may also remove positive amounts from both piles, but the two removed amounts must differ by at most k. The player with no legal move loses, so (0, 0) is a losing position.

For each of up to 10^5 independent games, we receive the two initial pile sizes and the tolerance k. We need to print 2 exactly when the starting position is losing for the first player, and 1 otherwise. The official statement confirms these bounds and the sample data.

The large coordinate bound, x,y <= 10^9, rules out any dynamic programming indexed by pile size. Even one game could contain about 10^18 different positions. With 10^5 games and a 2 second limit, the intended solution must use a constant or logarithmic amount of arithmetic per game. The fact that k <= 12 is also a strong hint that the tolerance changes the structure in a controlled way rather than requiring a large search over possible tolerances.

There are several edge cases that are easy to mishandle.

The terminal position is special. For input

1
0 0 0

the correct output is

2

because the first player has no move. A formula that only handles positive indices and accidentally treats index zero as an ordinary P-position can get this wrong.

The piles are interchangeable, so the order of the input coordinates must not matter. For

1
2 1 0

the correct output is 2, because (1,2) is a losing Wythoff position. An implementation that assumes the first coordinate is always smaller without actually swapping the values can reject a valid P-position.

The tolerance changes the relevant diagonal spacing. For

1
1 3 1

the correct output is 2. The position is losing because it is one of the generalized Wythoff positions for k=1. Treating the condition as |a-b| < k instead of |a-b| <= k changes the game and gives the wrong classification.

The case where the pile difference is not divisible by k+1 is also significant. For

1
1 2 1

the correct output is 1. Here the difference is 1, while k+1=2, so the position cannot itself be one of the P-positions described by the solution. A careless implementation that only checks whether the difference is "small" rather than whether it matches the required arithmetic progression will misclassify it.

Finally, equality of the piles does not mean a position is losing. For

1
5 5 3

the correct output is 1. The only equal P-position in this game is (0,0), because the generalized P-positions have a positive difference whenever their index is positive.

Approaches

The most direct approach is to solve the game recursively. A position is losing if every legal move goes to a winning position, and it is winning if at least one move goes to a losing position. With memoization, this gives a correct dynamic program.

The problem is the size of the state space. If the initial piles are X and Y, memoization may still require every position (x,y) with 0 <= x <= X and 0 <= y <= Y. That is roughly XY states. Even if we only count the single-pile moves, the total number of transitions examined over all states is

\frac{XY(X+Y+2)}2. ]

For X=Y=10^9, this is about 10^27 transitions before considering the two-pile moves. A recursion without memoization is even worse because it repeatedly explores the same subgames.

The breakthrough is to stop thinking about every position individually and instead characterize exactly which positions are losing. This game is a generalized form of Wythoff Nim. For a positive integer r = k+1, its P-positions are generated by

[ a_n=\left\lfloor n\alpha\right\rfloor, \qquad b_n=a_n+rn, ]

where

[ \alpha=\frac{2-r+\sqrt{r^2+4}}2. ]

This is the standard generalized Wythoff construction, where the two complementary Beatty sequences differ by rn. The corresponding P-position characterization is also known as the k-Wythoff Nim characterization.

The reason r=k+1 appears is particularly clean. Consecutive P-positions have differences

[ b_n-a_n=rn. ]

If we try to move from P-position n to an earlier P-position m, the two removed amounts differ by

[ rn-rm=r(n-m). ]

Since r=k+1, this difference is at least k+1, so such a move violates the allowed bound k. Single-pile moves are impossible between P-positions because the coordinate sequences are complementary.

The complementary property is the other half of the solution. The sequences (a_n) and (b_n) contain every positive integer exactly once. This is a direct consequence of Beatty's theorem because the two slopes satisfy

[ \frac1\alpha+\frac1{\alpha+r}=1. ]

That gives us a way to prove that every non-P-position has a move into a P-position.

The final classification is especially simple. Sort the two piles so that x <= y, let d=y-x, and put r=k+1. If d is divisible by r, let

[ n=\frac d r. ]

The position is losing exactly when

[ x=a_n. ]

Otherwise it is winning.

There is one numerical issue left. Computing floor(n*alpha) directly with floating point is risky because n can be as large as 10^9. We can remove floating point completely. Since

\left\lfloor \frac{n(2-r)+n\sqrt{r^2+4}}2 \right\rfloor, ]

let

[ q=\left\lfloor n\sqrt{r^2+4}\right\rfloor. ]

Then

[ q=\left\lfloor\sqrt{n^2(r^2+4)}\right\rfloor, ]

which can be computed exactly with Python's math.isqrt. Hence

[ a_n= \frac{n(2-r)+q}{2} ]

with integer floor division. No floating-point approximation is needed.

Approach Time Complexity Space Complexity Verdict
Brute Force O(XY(X+Y)) per game with memoization O(XY) Too slow
Optimal O(log(x+y)) arithmetic per game O(1) Accepted

Algorithm Walkthrough

  1. For each game, first reorder the piles so that x <= y. The game is symmetric, so this does not change its outcome.
  2. Set r = k + 1. The generalized Wythoff P-positions have the form (a_n,b_n) with

[ b_n-a_n=rn. ]

Thus a position can only be a P-position if y-x is divisible by r. 3. If d = y-x is not divisible by r, immediately classify the position as winning. A P-position has difference exactly rn for some integer n. 4. Otherwise compute n = d // r. The only possible P-position with this difference is (a_n,b_n), so the remaining question is whether x equals a_n. 5. Compute

[ a_n= \left\lfloor n\frac{2-r+\sqrt{r^2+4}}2 \right\rfloor ]

without floating point. Calculate

[ q=\operatorname{isqrt}(n^2(r^2+4)), ]

then use

[ a_n=(n(2-r)+q)//2. ]

The isqrt operation gives the exact integer floor of the square root. 6. If x == a_n, the position is a P-position, so the first player loses and we print 2. Otherwise it is an N-position, so the first player wins and we print 1.

Why it works

The two sequences

[ a_n=\lfloor n\alpha\rfloor, \qquad b_n=\lfloor n(\alpha+r)\rfloor ]

are complementary because their slopes satisfy

[ \frac1\alpha+\frac1{\alpha+r}=1. ]

Consequently, every positive integer appears in exactly one of the two sequences.

Consider two distinct P-positions with indices m < n. Their coordinate differences are both positive, and the difference between the two amounts removed is

k+1. ]

So no legal two-pile move can connect two P-positions. A one-pile move cannot connect them either, because complementarity means no coordinate is shared between different P-position coordinates.

Now take a non-P-position (x,y) with x <= y. If one coordinate belongs to the upper sequence b_n, complementarity lets us reduce the other coordinate to obtain the corresponding P-position using a single-pile move.

The remaining case is x=a_m and y=a_n. If y>b_m, we can reduce y to b_m and reach (a_m,b_m). Otherwise,

[ d=y-x=a_n-a_m<b_m-a_m=rm. ]

Choose

[ j=\left\lfloor\frac d r\right\rfloor. ]

Then j<m and

[ 0\le d-rj\le r-1=k. ]

Since a_j < a_m=x and b_j=a_j+rj <= y, we can reduce both piles to (a_j,b_j). The two removed amounts differ by exactly d-rj, which is at most k. Thus every non-P-position has a move to a P-position.

These two properties are precisely the defining properties of losing positions: no move leaves a P-position, while every other position has a move into one. The classification is consequently correct.

Python Solution

import sys
import math

input = sys.stdin.readline

def solve():
    t = int(input())
    out = []

    for _ in range(t):
        x, y, k = map(int, input().split())

        if x > y:
            x, y = y, x

        r = k + 1
        d = y - x

        if d % r != 0:
            out.append("1")
            continue

        n = d // r

        # a_n = floor(n * (2 - r + sqrt(r^2 + 4)) / 2)
        # floor(n * sqrt(D)) = isqrt(n^2 * D)
        D = r * r + 4
        q = math.isqrt(n * n * D)

        a = (n * (2 - r) + q) // 2

        if x == a:
            out.append("2")
        else:
            out.append("1")

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()

The first part of the loop sorts the two piles. This lets the rest of the code use the convention x <= y and avoids checking both orientations of every P-position.

The variable r is k+1, not k. This off-by-one is the central detail of the game. The P-position differences are multiples of k+1, because two P-positions must be separated by more than the permitted difference k between removed amounts.

The divisibility test comes before any square-root calculation. If d is not divisible by r, there is no possible P-position with that coordinate difference, so the answer is immediately 1.

When d is divisible, n=d/r identifies the only candidate P-position. The code then computes its smaller coordinate a_n.

The expression involving isqrt is exact. Let D=r*r+4. Since

[ \operatorname{isqrt}(n^2D)=\lfloor n\sqrt D\rfloor, ]

we can replace the irrational part of the Beatty formula with an integer. Python integers have arbitrary precision, so the largest intermediate value, around 10^20, cannot overflow.

The // 2 operation is also safe despite the irrational term. If

[ n\sqrt D=q+f,\qquad 0\le f<1, ]

then the quantity being floored is (integer + f)/2. Whether the integer part is even or odd, the fractional part can never push the result across the next integer. Thus the floor is exactly obtained from the integer numerator using // 2.

The code uses sys.stdin.readline as requested. With only a few integer operations and one integer square root per game, the implementation easily avoids constructing any large game-state table.

Worked Examples

Consider the first sample game, (0,0,k=0). Here r=1 and the piles are already ordered.

x y k r d=y-x d % r n a_n Result
0 0 0 1 0 0 0 0 2

The difference is divisible by r, giving n=0. The formula gives a_0=0, which equals x. Hence (0,0) is a P-position and the first player loses. This confirms that the index-zero case is handled naturally by the same formula as all other P-positions.

Now consider the sample game (23,9,k=1). Reordering gives (9,23). Since r=k+1=2, the difference is 14, so the candidate index is n=7.

For r=2, the formula becomes

[ a_n=\lfloor n\sqrt2\rfloor. ]

At n=7,

[ a_7=\lfloor7\sqrt2\rfloor=9. ]

x y k r d n=d/r a_n x == a_n Result
9 23 1 2 14 7 9 Yes 2

So (9,23) is a P-position, matching the sample output 2. The trace also demonstrates why sorting the coordinates is necessary: the original input has the larger pile first.

For a non-P-position near a tolerance boundary, consider (1,13,k=12). Here r=13, and the difference is exactly 12, which is less than r.

x y k r d d % r n a_n Result
1 13 12 13 12 12 not used not used 1

The difference is not divisible by 13, so this cannot be a P-position. In fact, the first player can remove 1 stone from the first pile and 13 from the second, reaching (0,0). The two amounts differ by exactly 12, so the move is legal.

Complexity Analysis

Measure Complexity Explanation
Time O(n log max(x,y)) Each game performs a constant number of integer operations and one isqrt on an integer with O(log max(x,y)) bits.
Space O(1) auxiliary space Apart from the output buffer, the algorithm stores only a constant number of integers per game.

With n <= 10^5 and coordinates at most 10^9, the square-root operands contain only around 67 bits. The algorithm therefore performs a small fixed amount of big-integer arithmetic per query rather than iterating through pile sizes. This is comfortably compatible with the stated 2 second limit and 256 MB memory limit.

Test Cases

import sys
import io
import math

input = sys.stdin.readline

def solve():
    t = int(input())
    out = []

    for _ in range(t):
        x, y, k = map(int, input().split())

        if x > y:
            x, y = y, x

        r = k + 1
        d = y - x

        if d % r != 0:
            out.append("1")
            continue

        n = d // r
        D = r * r + 4
        q = math.isqrt(n * n * D)
        a = (n * (2 - r) + q) // 2

        out.append("2" if x == a else "1")

    sys.stdout.write("\n".join(out))

def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    try:
        solve()
        return sys.stdout.getvalue()
    finally:
        sys.stdin = old_stdin
        sys.stdout = old_stdout

sample = """15
0 0 0
23 9 1
97 99 2
1984 6 3
277 348 4
2384 19 5
138 19 6
123 372 7
112 1021 8
99328 9702 9
3172 283401 10
1937 23405 11
421443 503539 12
508320368 822479633 0
924717293 228947159 1
"""

sample_output = """2
2
1
1
1
1
2
1
2
1
1
2
1
2
1"""

assert run(sample) == sample_output, "official sample"

assert run("""1
0 0 0
""") == "2\n", "terminal position"

assert run("""4
1 1 0
1 2 0
2 1 0
1 3 1
""") == """1
2
2
2
""", "classical Wythoff and coordinate symmetry"

assert run("""3
2 4 1
1 13 12
1 14 12
""") == """1
1
2
""", "tolerance boundaries and generalized P-position"

assert run("""3
5 5 3
1000000000 1000000000 12
0 1000000000 0
""") == """1
1
1
""", "equal piles and maximum coordinates"
Test input Expected output What it validates
0 0 0 2 The unique terminal position and index n=0.
1 1 0, 1 2 0, 2 1 0, 1 3 1 1, 2, 2, 2 Classical Wythoff positions, coordinate symmetry, and the k=1 case.
2 4 1, 1 13 12, 1 14 12 1, 1, 2 The distinction between differences divisible by k+1 and the exact P-position check.
5 5 3, 10^9 10^9 12, 0 10^9 0 1, 1, 1 Equal piles, maximum coordinates, and positions where one pile is empty.

Edge Cases

For the terminal position

1
0 0 0

the algorithm gets r=1, d=0, and n=0. The exact square-root expression is zero, so a_0=0. Since x=0, the position is recognized as losing and the output is 2. No special case is actually needed for (0,0).

For reversed coordinates, consider

1
2 1 0

The algorithm first swaps the piles and obtains (1,2). With r=1, the difference is 1, giving n=1. The formula gives a_1=1, so the position is P and the answer is 2. Without the initial swap, a correct P-position could be rejected simply because its coordinates were supplied in the opposite order.

For the tolerance boundary, consider

1
1 13 12

Here r=13 and d=12. Since 12 % 13 != 0, the algorithm immediately returns 1. This is correct because the generalized P-positions have differences 0,13,26,39,.... The position is actually winning by the direct move from (1,13) to (0,0), which removes 1 and 13 stones, whose difference is exactly the allowed tolerance 12.

For an actual P-position at the same tolerance, consider

1
1 14 12

Now d=13, so n=1. With r=13,

[ a_1= \left\lfloor \frac{2-13+\sqrt{173}}2 \right\rfloor =1. ]

Thus (1,14) is a P-position and the output is 2. The pair demonstrates exactly why the relevant spacing is k+1, rather than k.

For equal piles, consider

1
5 5 3

The difference is zero, so n=0 and a_0=0. Since the smaller pile is 5, not 0, the position is not P and the answer is 1. The first player can remove five stones from one pile and reach (0,5), after which the opponent has a move.

For maximum coordinates, consider

1
1000000000 1000000000 12

Again d=0, so only n=0 needs to be considered. The algorithm computes a_0=0, sees that the pile size is not zero, and prints 1. The large coordinate never causes a state-space explosion because the solution does not enumerate any positions.

The final subtle case is an exact floating-point boundary. The formula contains an irrational square root multiplied by an index as large as 10^9. Using float and calling int(n*alpha) can theoretically make the answer wrong if rounding lands on the wrong side of an integer. The implementation avoids that entire class of errors by replacing the irrational calculation with math.isqrt(n*n*(r*r+4)), so every comparison is performed with exact integers.