CF 2027E1 - Bit Game (Easy Version)

CF 2027E1 - Bit Game (Easy Version)

Rating: 2800
Tags: bitmasks, brute force, games, math
Solve time: 1m 17s
Verified: no

Solution

Problem Understanding

Each test case gives us several independent piles of stones. Every pile behaves like a small game on its own: on your turn you pick a pile and remove some positive number of stones from it, but the move is heavily constrained. If the pile currently has value x, and its limit is a, then you are allowed to remove a number d only if 1 ≤ d ≤ a and d is a bit-subset of x, meaning every bit set in d must also be set in x (formally x & d = d).

The game ends when a player cannot make any valid move in any pile. Since players alternate moves and Alice starts, we are asked to determine whether the starting position is winning or losing under optimal play.

The structure is not a standard Nim heap where you can remove any number up to a limit. Here, the allowed moves depend on the bit structure of the current pile size, which couples arithmetic constraints with binary structure. Each pile is independent in terms of moves, but the game is a disjunctive sum, so the final outcome depends on XOR-like game values (Grundy numbers), not simple parity.

The constraints imply up to 10^4 piles per test and total 10^4 over all tests. This rules out any solution that simulates moves or builds full state graphs per pile. Even iterating over all submasks of x_i per pile would be too slow since a number up to 2^30 can have an exponential number of submasks.

Edge cases arise when a pile has no valid move at all. For example, if x = 8 and a = 3, no submask of 8 lies in [1, 3], so the pile is inert. A naive solver that assumes every pile contributes some value to the game would incorrectly treat such piles as non-zero components.

Another subtle case occurs when a is large but x has very sparse bits. For instance, x = 16 and a = 15 still gives no move even though a is large, because all valid submasks of 16 are {16, 0} and 16 is out of range.

Finally, the most dangerous pitfall is assuming independence of bits in x. The constraint d ⊆ x means we only choose subsets of set bits, not arbitrary values up to a.

Approaches

A brute-force approach would treat each pile as a game state and compute its Grundy number. From a state (x, a), we enumerate all valid moves d, transition to (x - d, a), and compute mex of reachable states. However, this immediately explodes: each x up to 2^30 can have up to 2^k submasks, and across piles this becomes infeasible even once, let alone per test case.

The key observation is that the pile transitions depend only on the binary structure of x and the cap a, and the state space collapses into a small combinatorial structure. Instead of tracking all subtractions, we reinterpret the move as choosing a non-empty submask of x bounded by a, which is equivalent to choosing a subset of set bits of x whose numeric value does not exceed a.

This turns each pile into a constrained subtraction game over a bitset, and the Grundy value depends only on the highest bit where a and x differ and the structure below it. After analyzing transitions, one finds that each pile reduces to a simple XOR-contribution: each pile contributes either 0 or 1 to the global XOR depending on whether a allows at least one valid move and whether the parity of reachable states collapses.

The game becomes a Nim heap sum of independent 1-bit games, so the answer reduces to computing the XOR of pile values derived from a per-pile condition.

Algorithm Walkthrough

We reduce each pile to a binary decision: whether it contributes a winning “token” or not.

1. For each pile, compute whether there exists at least one valid move d.

This is equivalent to checking whether there is any non-zero submask of x such that d ≤ a. 2. If no such d exists, the pile is terminal and contributes 0. 3. Otherwise, we determine whether the pile is “active” in the sense that the first player can force a move that flips parity of the overall game state. This reduces to checking whether the highest bit of x that exceeds a blocks all moves or not. 4. We assign each pile a Grundy contribution of either 0 or 1 depending on this reachability condition. 5. XOR all contributions across piles. 6. If the final XOR is non-zero, Alice wins; otherwise Bob wins.

The key reduction is that every pile behaves like a single Nim heap of size 0 or 1 after collapsing all valid move dynamics into a parity outcome.

Why it works

Each pile is an impartial game, so the full game is the XOR sum of pile Grundy values. The allowed moves form a downward-closed set over submasks of x, truncated by a, which guarantees that all reachable states are structurally equivalent except for whether a move exists at all. This forces the Grundy function to collapse into a binary state: losing positions are exactly those where no valid submask exists, and all others evaluate to a uniform winning class. Since all winning positions have Grundy value 1 and losing positions have 0, the global game reduces to XOR over these indicators.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        x = list(map(int, input().split()))
        
        xor_val = 0
        
        for ai, xi in zip(a, x):
            # check if any valid move exists: need submask d of x with d <= a
            # equivalent to: there exists bit in x that fits within a's constraints
            # simplest characterization: if xi & ai is non-zero, we can form a move
            if (xi & ai) != 0:
                # pile contributes 1 in reduced game
                xor_val ^= 1
        
        print("Alice" if xor_val else "Bob")

if __name__ == "__main__":
    solve()

The code compresses each pile into a single binar