CF 1373B - 01 Game

Rating: 900
Tags: games
Solve time: 2m 24s
Verified: yes

Solution

Problem Understanding

We are given a binary string and two players who alternately remove exactly two adjacent characters from it. Each move deletes a contiguous pair, so the string shrinks by 2 characters each turn. A player loses immediately when they are faced with a string where no adjacent pair exists, which happens when the string length is 0 or 1.

The key question is not about constructing moves but about deciding the winner if both players choose optimally. Alice always moves first, so the game is fully determined by how many valid moves can be made in total before the string becomes too short to continue.

The constraint on the string length is small, at most 100, and there are up to 1000 test cases. This means even an O(n²) simulation per test case would be acceptable, but the structure of the problem suggests we should aim for an O(n) reasoning per string.

A subtle point is that the exact arrangement of 0s and 1s does not really matter for long-term play beyond whether moves exist. Each move only reduces length by 2, and no move creates new adjacency constraints beyond shrinking the string. So the game is fundamentally about how many moves can be played, not about specific patterns.

Edge cases that break naive thinking come from focusing too much on structure instead of parity.

For example, consider a string like 01. Alice removes it immediately and wins. For 1111, Alice removes a pair, Bob removes a pair, and Alice has no move. For 0011, Alice removes a pair, leaving 01, and Bob removes it, leaving empty. Alice then has no move and loses. These examples show that parity of moves, not local structure, decides the result.

A common incorrect intuition is to think that alternating characters or grouping matters. In reality, every move reduces the length by 2, so the number of moves is essentially fixed by how many disjoint adjacent pairs can be removed until the string becomes too short.

Approaches

A brute-force approach would simulate the game state fully. At each step, a player tries every possible adjacent pair removal, recursively evaluates the resulting string, and determines whether any move leads to a losing position for the opponent. This is a standard minimax search over strings.

The issue is that the number of states grows extremely quickly. Even for length 20, the branching factor is up to 19, and states repeat heavily but not in a structured way unless memoization is carefully designed over strings. For length up to 100, this approach becomes completely infeasible.

The key observation is that every move always reduces the length by exactly 2, and no move changes anything else relevant for future move availability except shrinking the string. That means the total number of moves possible is determined solely by how many times we can remove adjacent pairs until the string length becomes 0 or 1.

So the game reduces to counting how many moves exist in total and checking whether Alice makes the last move. If the total number of moves is odd, Alice wins. If it is even, Bob wins.

We do not even need to explicitly compute moves. The number of moves is simply len(s) // 2 because every move deletes exactly two characters and no move depends on which pair is chosen for determining the final count of moves.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force (Minimax over states)	O(exponential)	O(n)	Too slow
Optimal (parity observation)	O(n)	O(1)	Accepted

Algorithm Walkthrough

The algorithm relies on reducing the game to a simple parity check.

Read the string and compute its length. The structure of the characters is irrelevant for the final decision, so we ignore actual content.
Determine how many full moves can be made. Each move removes exactly two characters, so the number of moves is the integer division of the length by 2.
Decide the winner based on parity. If the number of moves is odd, Alice makes the last move and Bob is left without a valid move. If it is even, Bob makes the last move and Alice loses after that.
Output "DA" if Alice wins and "NET" otherwise.

The reason this reduction is valid is that no move ever changes the parity of available structure beyond decreasing length by a fixed amount. There is no branching effect that can increase or decrease the total number of moves depending on strategy, because every move consumes exactly two characters regardless of which adjacent pair is chosen.

Why it works

The invariant is that after any sequence of valid moves, the remaining string length is always n - 2k where k is the number of moves made. The game ends exactly when this value becomes less than 2. Therefore, the maximum number of moves possible is fixed as n // 2, independent of choices. Since both players alternate moves starting with Alice, Alice wins if and only if she gets the last move in this fixed sequence, which is equivalent to n // 2 being odd.

Python Solution

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    s = input().strip()
    moves = len(s) // 2
    if moves % 2 == 1:
        print("DA")
    else:
        print("NET")

The code reads each test case and immediately reduces it to a length computation. The only computation needed is integer division by 2, which corresponds to the total number of deletions possible. The parity check directly determines the winner.

A common mistake is trying to simulate deletions or track actual pairs. That is unnecessary because the game never depends on which specific pair is removed, only on how many removals happen before exhaustion.

Worked Examples

Example 1: `01`

Step	String length	Moves made	Next player
0	2	0	Alice
1	0	1	Bob (no move)

Alice makes exactly one move, which is odd, so she wins.

This confirms that for length 2, Alice always wins because she takes the only possible move.

Example 2: `0011`

Step	String length	Moves made	Next player
0	4	0	Alice
1	2	1	Bob
2	0	2	Alice (no move)

Here there are exactly 2 moves. Bob makes the second move, leaving Alice without a valid move. Since the number of moves is even, Alice loses.

This demonstrates that the final outcome depends only on whether the total number of deletions is odd or even, not on the arrangement of characters.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n) per test case	Each test case only scans the string once to compute its length
Space	O(1)	No extra structures are stored beyond counters

The solution comfortably fits within constraints since the total input size is small and each test case is processed in constant time after reading.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys as _sys
    input = _sys.stdin.readline

    t = int(input())
    out = []
    for _ in range(t):
        s = input().strip()
        moves = len(s) // 2
        out.append("DA" if moves % 2 == 1 else "NET")
    return "\n".join(out)

# provided samples
assert run("3\n01\n1111\n0011\n") == "DA\nNET\nNET"

# minimum size
assert run("1\n1\n") == "NET"

# simple win
assert run("1\n00\n") == "DA"

# alternating pattern
assert run("1\n0101\n") == "NET"

# maximum-ish small test
assert run("1\n" + "01"*50 + "\n") == "NET"

Test input	Expected output	What it validates
`1`	`NET`	single character, no moves
`00`	`DA`	smallest winning case
`0101`	`NET`	even-length alternating pattern
`01*50`	`NET`	larger even structure, parity consistency

Edge Cases

For a single character like 0, the algorithm computes len = 1, so moves = 0, and outputs "NET". This matches the fact that Alice has no valid move immediately.

For a pair like 01, moves = 1, which is odd, so Alice wins. In execution, Alice removes the only pair and Bob cannot move.

For a string like 1111, the algorithm computes moves = 2. Alice makes the first move, Bob the second, and Alice has no move left. The even parity correctly predicts Alice loses.

For alternating strings like 010101, only the length matters. Even though many different removal orders exist, the algorithm still yields moves = 3, meaning Alice wins because she gets the last move.