CF 102780F - A word game

CF 102780F - A word game

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

Solution

Problem Understanding

The game is played on a word, but the order of letters is not the part that matters. A move only cares about how many copies of each letter remain. If a letter appears several times, a player may remove one copy, remove exactly two copies, or remove every remaining copy of that letter. The player who makes the total number of remaining letters become zero wins.

The input is one uppercase word with at most 40 characters. The output tells which player has a winning strategy if both players choose moves optimally. The original problem is from the Central Russia Regional Contest 2019.

The small word length means that a simple search over all game states might look possible at first. However, the number of possible states grows quickly because every different distribution of letters creates a different position. A solution that explores all states can approach exponential time, which is unnecessary even for length 40. We need to find a mathematical property of each letter count instead.

The main edge cases come from treating the moves as ordinary removals. A careless solution may assume that a letter with a count divisible by three is always losing because removing one or two letters resembles a take-away game. This fails because removing all copies is a special move. For example, input AAA has answer Alice. The count is three, but Alice can remove all three letters immediately.

Another common mistake is ignoring letters that appear only once. For input A, the answer is Alice because the only move removes the final letter. A solution that only checks pairs or complete groups would incorrectly mark it as losing.

A third edge case is that the whole word does not have a single game value. For input AB, the answer is Bob, because each letter contributes independently and their effects cancel. A solution that only looks at the total length would miss this interaction.

Approaches

The direct approach is to model the current word state and recursively try every possible move. For every letter, we can decrease its count by one, decrease it by two if possible, or set it to zero. If a recursive state has at least one move leading to a losing state, it is winning. Otherwise it is losing.

This brute force method is correct because it exactly follows the definition of optimal play. The problem is the number of states. With 26 possible letter counts, even a short word can create many different distributions. The worst case is exponential in the number of letters, because every possible subset of removals can appear as a separate state.

The observation that changes the problem is that every letter type behaves like an independent game component. This is a standard impartial game situation, where each component has a Grundy value and the whole position is determined by xor-ing those values.

Consider only one letter that appears c times. Let g(c) be its Grundy value. Its moves go to c - 1, c - 2, and 0 when those moves exist. Computing the first values gives:

Count	Grundy value
0	0
1	1
2	2
3	3
4	1
5	2
6	3

The pattern repeats every three counts. A positive count that is divisible by three has value 3, while the other counts have value equal to their remainder.

The entire word is then just the xor of the 26 letter values. If the xor is not zero, Alice can move to a zero xor position and win. If the xor is zero, every move gives Bob a winning position.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	Exponential	Exponential	Too slow
Optimal	O(n + 26)	O(26)	Accepted

Algorithm Walkthrough

1. Count how many times each uppercase letter appears in the word. The game state depends only on these frequencies, not on the positions of letters.
2. For every letter with frequency c, calculate its Grundy value. If c is zero, it contributes nothing. Otherwise, use c % 3 and replace a remainder of zero with value 3.
3. Xor all 26 values together. The xor combines the independent games represented by different letters.
4. Print Alice when the xor is non-zero. Print Bob when the xor is zero.

The reason the last step works is that a zero xor position is losing in impartial combinatorial games. A non-zero xor position always has a move to a zero xor position, while a zero xor position cannot move to another zero xor position.

Why it works:

Each letter frequency is an independent pile. A move changes exactly one pile and does not affect the others. The Grundy value summarizes every possible future of one pile. The xor of all pile values is therefore the complete value of the word. If this value is zero, both players face a losing state. If it is non-zero, the current player has a move that makes the xor zero, leaving the opponent in a losing state.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    s = input().strip()

    cnt = [0] * 26
    for ch in s:
        cnt[ord(ch) - ord('A')] += 1

    x = 0
    for c in cnt:
        if c:
            value = c % 3
            if value == 0:
                value = 3
            x ^= value

    print("Alice" if x else "Bob")

if __name__ == "__main__":
    solve()

The array cnt stores the independent game components. There are only 26 of them, so the implementation never needs to simulate moves.

The Grundy conversion is done only for positive frequencies. Zero frequency letters have value zero and do not affect the xor. The special handling of multiples of three is necessary because a pile of size three is not equivalent to a pile of size zero. The move that removes all letters changes the repeating pattern.

The final xor is stored in x. Python integers do not overflow, although the values here are very small anyway. The input contains one word, so a single call to readline is enough.

Worked Examples

For ZADACHA, the letter counts are:

Letter	Count	Grundy value	Current xor
A	3	3	3
C	1	1	2
D	1	1	3
H	1	1	2
Z	1	1	3

The final xor is non-zero, so Alice wins.

For WORD, the counts are:

Letter	Count	Grundy value	Current xor
W	1	1	1
O	1	1	0
R	1	1	1
D	1	1	0

The final xor is zero, so Bob wins.

These traces show why the result depends on letter frequencies rather than the original order of the word.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Counting the letters takes one pass over the word, then only 26 values are processed.
Space	O(1)	The algorithm stores only the 26 counters.

The maximum length is only 40, so the linear solution is easily within the limits. The constant memory usage also remains unchanged for larger inputs.

Test Cases

import sys
import io

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

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

    solve()

    result = sys.stdout.getvalue().strip()

    sys.stdin = old_stdin
    sys.stdout = old_stdout
    return result

assert run("ZADACHA\n") == "Alice", "sample 1"
assert run("WORD\n") == "Bob", "sample 2"

assert run("A\n") == "Alice", "single letter"
assert run("AAA\n") == "Alice", "all equal letters"
assert run("AB\n") == "Bob", "xor cancellation"
assert run("A" * 40 + "\n") == "Bob", "maximum size multiple of three"

Test input	Expected output	What it validates
A	Alice	A single removable letter must be winning.
AAA	Alice	The all-letters move changes the Grundy pattern for multiples of three.
AB	Bob	Independent letters combine through xor, not by total length.
40 copies of A	Bob	Large frequency handling and repeated Grundy values.

Edge Cases

For input AAA, the algorithm counts one letter with frequency three. Its Grundy value is 3, so the xor is 3 and Alice is printed. This handles the case where removing all copies is better than taking one or two copies.

For input A, the count is one, giving Grundy value 1. The xor is non-zero, so Alice wins immediately by removing the only letter.

For input AB, both letters have frequency one and both contribute value 1. The xor becomes 1 ^ 1 = 0, so the position is losing. Every move leaves exactly one letter, and the opponent removes the final letter.

For a word containing 40 copies of the same letter, the count is 40. The Grundy value is 40 % 3 = 1, so the position is winning. The algorithm handles the maximum input size without depending on the number of possible moves.