CF 105292K - King Game

Rating: -
Tags: -
Solve time: 1m 30s
Verified: yes

Solution

Problem Understanding

We have two pieces on a $300 \times 300$ board. A move chooses one piece at position $(x,y)$ and moves it to any strictly smaller position inside the rectangle $[1,x] \times [1,y]$. The destination cannot be the current square and cannot be occupied by the other piece.

The game is impartial and finite. Every move decreases at least one coordinate, so the game must eventually end. The player who cannot move loses.

For each starting configuration, we must count how many first moves are winning, assuming optimal play afterwards. The number of test cases is as large as $10^5$, so anything that performs game-theory computation per test case is far too slow. We need a closed-form characterization of winning moves.

A subtle point is that the two pieces are not completely independent. Moving onto the other piece is forbidden. A solution that blindly computes the xor of two independent Grundy numbers will miss this interaction.

Consider:

(1,1) and (2,1)

The larger piece would like to move to $(1,1)$, but that square is occupied, so that move does not exist.

Another important case is when both pieces lie on the same diagonal $x+y=\text{constant}$. For example:

(3,2) and (2,3)

Both positions have the same single-piece Grundy number. A careless xor-based argument would say the position is losing because the xor is zero, which is correct, but we still need to understand why no move can preserve that zero state.

Approaches

The brute-force approach is to treat every pair of piece positions as a game state and compute its Sprague-Grundy value by dynamic programming on the game graph. There are $90{,}000$ board cells, so the number of ordered two-piece states is on the order of $8 \times 10^9$. Even storing the states is impossible.

The key observation is that a single piece already has a very simple structure.

Let $g(x,y)$ be the Grundy number of one piece. From $(x,y)$, every square in the rectangle below and to the left is reachable. If we define

$$k=x+y-2,$$

then every smaller value $0,1,\dots,k-1$ appears among the reachable positions, and no reachable position has value $k$. The mex is therefore exactly $k$.

$$g(x,y)=x+y-2.$$

The board collapses into diagonals. Every square on the same diagonal has the same Grundy number.

Now consider two pieces.

If their diagonal values are different, say $a<b$, then the position behaves exactly like two Nim heaps of sizes $a$ and $b$. Its Grundy number is $a \oplus b$.

If both pieces are on the same diagonal, the position is special. The two pieces occupy different squares but have the same single-piece Grundy number. A direct mex argument shows that such a state has Grundy number $0$.

This immediately gives the winning strategy structure:

If the two diagonal values are equal, the position is losing and there are no winning first moves.

If the diagonal values are different, the only way to move to a losing state is to move the piece with the larger diagonal value onto the smaller diagonal value. Every legal destination on that diagonal is a winning move.

The remaining task is purely geometric: count how many squares of a given diagonal are reachable inside the allowed rectangle, excluding the occupied square if it is reachable.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	$O(\text{all states})$	Impossible	Too slow
Optimal	$O(1)$ per test case	$O(1)$	Accepted

Algorithm Walkthrough

Compute the diagonal values

$$g_1=x_1+y_1-2,\qquad g_2=x_2+y_2-2.$$

If $g_1=g_2$, output 0.

States with equal diagonal values are losing positions, so no move can lead to another losing position. 2. Suppose $g_1>g_2$.

Any winning move must move the first piece onto diagonal $g_2$. 3. Count how many squares on diagonal $g_2$ lie inside the rectangle

$$1 \le p \le x_1,\qquad 1 \le q \le y_1.$$

The diagonal condition is

$$p+q=g_2+2.$$

Let

$$L=\max(1,\ g_2+2-y_1),$$

$$R=\min(x_1,\ g_2+1).$$

Then the number of reachable squares on that diagonal is

$$\max(0,\ R-L+1).$$

If the other piece's square $(x_2,y_2)$ is inside the reachable rectangle of the moving piece, subtract one because moving onto the occupied square is illegal.
If $g_2>g_1$, perform the symmetric computation for the second piece.

Why it works

A single piece at $(x,y)$ has Grundy number $x+y-2$. Every move strictly decreases this value, and every smaller value is reachable.

For two pieces on different diagonals, the game is equivalent to two Nim heaps whose sizes are the diagonal values. The only way to reach a zero Grundy state is to make the two values equal.

For two pieces already on the same diagonal, the state itself has Grundy number $0$. Any move changes one diagonal value and destroys the equality, so every move goes to a nonzero state.

Thus winning moves are exactly the legal moves that place the moved piece onto the other piece's diagonal. Counting those moves reduces to counting lattice points of a diagonal segment inside a rectangle.

Python Solution

import sys
input = sys.stdin.readline

def count_on_diagonal(x, y, k):
    s = k + 2

    left = max(1, s - y)
    right = min(x, s - 1)

    if left > right:
        return 0
    return right - left + 1

t = int(input())
ans = []

for _ in range(t):
    x1, y1, x2, y2 = map(int, input().split())

    g1 = x1 + y1 - 2
    g2 = x2 + y2 - 2

    if g1 == g2:
        ans.append("0")
        continue

    if g1 > g2:
        res = count_on_diagonal(x1, y1, g2)

        if x2 <= x1 and y2 <= y1:
            res -= 1

        ans.append(str(res))
    else:
        res = count_on_diagonal(x2, y2, g1)

        if x1 <= x2 and y1 <= y2:
            res -= 1

        ans.append(str(res))

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

The function count_on_diagonal counts lattice points satisfying

$$p+q=k+2$$

inside a rectangle. Instead of iterating over coordinates, it computes the valid range of $p$ directly.

The subtraction step is the only interaction between the two pieces. If the occupied square lies inside the moving piece's reachable rectangle, it would otherwise be counted as a valid destination, so it must be removed.

All arithmetic easily fits in standard Python integers. The board size is only 300, but the solution never depends on that limit.

Worked Examples

Example 1

Input:

1 2 3 4

Here:

$$g_1=1,\quad g_2=5.$$

The second piece has the larger value and must move onto diagonal 1.

Variable	Value
Target diagonal	1
Rectangle	$1 \le p \le 3,\ 1 \le q \le 4$
Reachable squares on diagonal 1	$(1,2),(2,1)$
Occupied square	$(1,2)$
Winning moves	1

Output:

The trace shows why the occupied square must be removed from the count.

Example 2

Input:

6 6 2 2

Variable	Value
$g_1$	10
$g_2$	2
Target diagonal	2
Reachable diagonal squares	$(1,3),(2,2),(3,1)$
Occupied square	$(2,2)$
Winning moves	2

Output:

This example demonstrates that multiple winning destinations may exist on the same diagonal.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(1)$	Constant amount of arithmetic per test case
Space	$O(1)$	No auxiliary structures depending on input size

With $10^5$ test cases, constant-time processing is easily fast enough.

Test Cases

# helper: run solution on input string, return output string
import sys, io

def solve():
    input = sys.stdin.readline

    def count_on_diagonal(x, y, k):
        s = k + 2
        left = max(1, s - y)
        right = min(x, s - 1)
        if left > right:
            return 0
        return right - left + 1

    t = int(input())
    out = []

    for _ in range(t):
        x1, y1, x2, y2 = map(int, input().split())

        g1 = x1 + y1 - 2
        g2 = x2 + y2 - 2

        if g1 == g2:
            out.append("0")
        elif g1 > g2:
            res = count_on_diagonal(x1, y1, g2)
            if x2 <= x1 and y2 <= y1:
                res -= 1
            out.append(str(res))
        else:
            res = count_on_diagonal(x2, y2, g1)
            if x1 <= x2 and y1 <= y2:
                res -= 1
            out.append(str(res))

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

def run(inp: str) -> str:
    backup_stdin = sys.stdin
    backup_stdout = sys.stdout

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

    solve()

    result = sys.stdout.getvalue()

    sys.stdin = backup_stdin
    sys.stdout = backup_stdout

    return result

# provided sample
assert run("""5
1 2 3 4
3 1 4 2
6 6 2 2
3 2 2 3
1 12 3 9
""") == """1
2
2
0
0"""

# custom cases
assert run("""1
1 1 2 1
""") == "0"

assert run("""1
2 1 1 2
""") == "0"

assert run("""1
3 3 1 1
""") == "0"

assert run("""1
300 300 299 300
""") == "299"

Test input	Expected output	What it validates
`(1,1) (2,1)`	`0`	Unique diagonal-0 square cannot be occupied
`(2,1) (1,2)`	`0`	Equal diagonal values form a losing state
`(3,3) (1,1)`	`0`	Occupied target square removes the only candidate
`(300,300) (299,300)`	`299`	Large coordinates and many winning moves

Edge Cases

Consider:

1
3 2 2 3

Both pieces have diagonal value $3$. The position is already a losing state. Any move decreases one diagonal value and breaks the equality. The algorithm detects $g_1=g_2$ and immediately outputs:

Now consider:

1
3 3 1 1

The larger piece has value $4$, the smaller has value $0$. To create a losing state we would need to move onto diagonal 0. That diagonal contains only the single square $(1,1)$, which is occupied. The count on the diagonal is 1, the occupied square is reachable, so we subtract 1 and obtain:

Finally:

1
6 6 2 2

Diagonal 2 contains three squares:

(1,3), (2,2), (3,1)

The occupied square $(2,2)$ is removed, leaving two legal winning moves. The algorithm returns:

which matches the expected result.