CF 63E - Sweets Game

The board is a fixed hexagon with 19 cells. Some cells contain chocolates, some are empty. Two players alternate moves, and a move consists of choosing a contiguous segment of chocolates that lies on a straight line parallel to one of the three hexagon directions.

codeforcescompetitive-programmingbitmasksdfs-and-similardpgamesimplementation

CF 63E - Sweets Game

Rating: 2000
Tags: bitmasks, dfs and similar, dp, games, implementation
Solve time: 2m 13s
Verified: yes

Solution

Problem Understanding

The board is a fixed hexagon with 19 cells. Some cells contain chocolates, some are empty. Two players alternate moves, and a move consists of choosing a contiguous segment of chocolates that lies on a straight line parallel to one of the three hexagon directions. Every chosen cell must currently contain a chocolate, and all chosen cells are removed together.

The player who cannot move loses. Since every move removes at least one chocolate, the game always terminates. Karlsson moves first, and we must determine whether the initial position is winning or losing assuming perfect play.

The most important observation about the constraints is that the board size is tiny. There are only 19 cells, so every possible board state fits inside a 19-bit mask. That means the total number of distinct positions is at most $2^{19} = 524288$, which is completely manageable for memoized game DP.

A naive recursive search without memoization would explode because the same positions are reached through many different move orders. For example, removing cell A then B reaches the same position as removing B then A. The branching factor is also fairly large because every line segment of chocolates is a legal move. A plain minimax search would revisit identical states exponentially many times.

The tricky part of the problem is generating legal moves correctly. The board is not rectangular, so careless coordinate handling easily creates invalid lines or misses valid ones.

One easy mistake is treating disconnected chocolates on the same geometric line as removable together. Only contiguous segments are allowed.

Consider this position:

. . .
 . O . .
O . O O .
 . . . .
  . . .

The two isolated chocolates on the same direction cannot be removed together because the middle cell is empty. A buggy implementation that only checks collinearity would incorrectly allow such a move.

Another subtle case is that every single chocolate is always a legal move. If move generation only considers segments of length at least two, the game result becomes wrong.

Example:

. . .
 . . . .
. . O . .
 . . . .
  . . .

The correct answer is "Karlsson" because the first player removes the only chocolate immediately. Missing single-cell moves incorrectly produces "Lillebror".

A third source of bugs is duplicated lines. Since the board has three geometric directions, every cell belongs to multiple lines. If the same segment is generated several times, the algorithm still remains correct, but performance becomes noticeably worse because the DFS explores redundant transitions repeatedly.

Approaches

The direct brute-force idea is to simulate the game recursively. For every position, generate all legal moves, recurse into the resulting positions, and classify the current state as winning if at least one move leads to a losing state.

This logic is correct because impartial combinatorial games obey the standard minimax property. A state is winning if the current player can force the opponent into a losing state.

The problem is repeated work. The same board state can be reached through many sequences of removals. Without memoization, the recursion tree becomes enormous. In the worst case, each move branches into dozens of possibilities, and the depth can reach 19. Even a branching factor around 10 already gives roughly $10^{19}$ recursive paths, which is impossible.

The key observation is that the board is small enough to encode as a bitmask. Each cell gets an index from 0 to 18. A board state becomes a 19-bit integer where bit $i$ tells whether chocolate $i$ exists.

Once states are encoded this way, memoization becomes natural. Every mask is solved once. For each state, we enumerate all removable contiguous segments and check whether removing that segment reaches a losing state.

The remaining challenge is efficient move generation. Instead of dynamically scanning the hexagon every time, we precompute every possible legal segment once at the beginning. The board geometry never changes, only occupancy changes.

The board contains 15 maximal straight lines across the three directions. For every line, every contiguous subsegment is a possible move template. During DFS, a move is legal if all cells of that segment are currently present in the mask.

This transforms the game into standard bitmask DP over at most 524288 states.

Approach Time Complexity Space Complexity Verdict
Brute Force Exponential, roughly $O(b^{19})$ Exponential recursion tree Too slow
Optimal $O(2^{19} \cdot M)$ $O(2^{19})$ Accepted

Here, $M$ is the number of precomputed line segments, which is small enough to act like a constant.

Algorithm Walkthrough

  1. Assign an index from 0 to 18 to every board cell.

We need a compact representation of states. A fixed index for each cell lets us store positions inside a bitmask. 2. Build coordinates for the hexagonal board.

A convenient representation uses axial hex coordinates. Every cell can then be identified by two coordinates $(x, y)$, and straight lines correspond to simple coordinate conditions. 3. Group cells into the three line directions.

In axial coordinates:

  • constant $x$
  • constant $y$
  • constant $x + y$

each define one family of straight lines on the hexagon. 4. For every maximal line, generate all contiguous segments.

Suppose a line contains cells $[a,b,c,d]$. Then all legal move templates are:

  • $[a]$
  • $[b]$
  • $[c]$
  • $[d]$
  • $[a,b]$
  • $[b,c]$
  • $[c,d]$
  • $[a,b,c]$
  • $[b,c,d]$
  • $[a,b,c,d]$

Each segment becomes a bitmask. 5. Read the input board and construct the initial state mask.

If a cell contains "O", set its bit in the mask. 6. Run memoized DFS on the mask.

For every precomputed move mask:

  • check whether all bits of the move are present in the current state
  • if yes, remove them and recurse

If any resulting state is losing, mark the current state as winning. 7. If no move leads to a losing state, mark the state as losing.

This means every possible move gives the opponent a winning continuation. 8. Print "Karlsson" if the initial state is winning, otherwise print "Lillebror".

Why it works

The DFS computes the standard winning and losing classification for impartial games under normal play rules.

Every legal move strictly decreases the number of chocolates, so recursion always terminates.

For each state, the algorithm examines all legal moves exactly once. A state is winning precisely when there exists a move to a losing state. Otherwise all moves lead to winning states, so the current state is losing.

The precomputed segments represent exactly the allowed moves because every legal move is a contiguous segment along one of the three board directions, and every such segment appears in one maximal line.

Python Solution

import sys
from functools import lru_cache
from collections import defaultdict

input = sys.stdin.readline

# build axial coordinates for radius-2 hexagon
coords = []
for x in range(-2, 3):
    y_min = max(-2, -x - 2)
    y_max = min(2, -x + 2)
    for y in range(y_min, y_max + 1):
        coords.append((x, y))

idx = {p: i for i, p in enumerate(coords)}

# generate all line segments
groups = defaultdict(list)

for i, (x, y) in enumerate(coords):
    groups(("x", x)).append((y, i))
    groups(("y", y)).append((x, i))
    groups(("z", x + y)).append((x, i))

moves = []

for key in groups:
    arr = sorted(groups[key])
    cells = [i for _, i in arr]
    n = len(cells)

    for l in range(n):
        mask = 0
        for r in range(l, n):
            mask |= 1 << cells[r]
            moves.append(mask)

# remove duplicates
moves = list(set(moves))

# input rows correspond to these lengths
row_lengths = [3, 4, 5, 4, 3]

board = []
for _ in range(5):
    board.extend(input().split())

mask = 0
ptr = 0

for length in row_lengths:
    for _ in range(length):
        if board[ptr] == "O":
            mask |= 1 << ptr
        ptr += 1

@lru_cache(None)
def win(state):
    for mv in moves:
        if (state & mv) == mv:
            nxt = state ^ mv
            if not win(nxt):
                return True
    return False

print("Karlsson" if win(mask) else "Lillebror")

The first section constructs the hexagonal board using axial coordinates. A radius-2 hexagon naturally contains 19 cells, matching the problem board exactly. Using coordinates instead of hardcoding adjacency makes line generation much cleaner.

The three line families correspond to constant x, constant y, and constant x + y. Every straight direction on a hex grid belongs to one of these groups.

For each line, the code generates every contiguous subsegment incrementally. The variable mask grows as the right endpoint expands, which avoids rebuilding masks repeatedly.

The input parsing deserves attention because the visual formatting of the statement can be misleading. The board always contains exactly 19 tokens split across row lengths 3,4,5,4,3. Using split() safely ignores extra spaces.

The DFS uses memoization through lru_cache. Since every move removes at least one bit, recursion depth never exceeds 19.

The legality test:

(state & mv) == mv

checks whether every chocolate required by the move still exists. This is safer than counting bits or iterating cell-by-cell.

The next state is formed with XOR because all bits in mv are guaranteed to be present already.

Worked Examples

Example 1

Input:

. . .
 . . O .
. . O O .
 . . . .
  . . .

The occupied cells form this initial mask structure:

Step Current State Winning Move Found Result
1 Three chocolates remain Try removing one chocolate Opponent still wins
2 Try removing adjacent pair Opponent still wins
3 Try removing all three Opponent still wins
4 No winning move exists None Losing

The final answer is "Lillebror".

This trace demonstrates that having multiple moves does not imply a winning state. Every move leaves a position where the opponent can force victory.

Example 2

Input:

. . .
 . . . .
. . O . .
 . . . .
  . . .
Step Current State Move Chosen Next State
1 Single chocolate Remove that cell Empty board
2 Empty board No legal move Losing

The final answer is "Karlsson".

This confirms the base game property: the empty state is losing because the current player has no legal moves.

Complexity Analysis

Measure Complexity Explanation
Time $O(2^{19} \cdot M)$ Each state is solved once, iterating over all move masks
Space $O(2^{19})$ Memoization table stores one value per state

The number of move masks is small because the board itself is fixed. Even in the worst case, the total work easily fits inside the limits. Around half a million states with lightweight bit operations is completely safe in Python.

Test Cases

# helper: run solution on input string, return output string
import sys, io
from functools import lru_cache
from collections import defaultdict

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

    coords = []
    for x in range(-2, 3):
        y_min = max(-2, -x - 2)
        y_max = min(2, -x + 2)
        for y in range(y_min, y_max + 1):
            coords.append((x, y))

    groups = defaultdict(list)

    for i, (x, y) in enumerate(coords):
        groups(("x", x)).append((y, i))
        groups(("y", y)).append((x, i))
        groups(("z", x + y)).append((x, i))

    moves = []

    for key in groups:
        arr = sorted(groups[key])
        cells = [i for _, i in arr]

        for l in range(len(cells)):
            mask = 0
            for r in range(l, len(cells)):
                mask |= 1 << cells[r]
                moves.append(mask)

    moves = list(set(moves))

    board = []
    for _ in range(5):
        board.extend(input().split())

    mask = 0

    for i, c in enumerate(board):
        if c == "O":
            mask |= 1 << i

    @lru_cache(None)
    def win(state):
        for mv in moves:
            if (state & mv) == mv:
                if not win(state ^ mv):
                    return True
        return False

    print("Karlsson" if win(mask) else "Lillebror")

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    out = io.StringIO()
    backup = sys.stdout
    sys.stdout = out

    solve()

    sys.stdout = backup
    return out.getvalue().strip()

# provided sample
assert run(""". . .
. . O .
. . O O .
. . . .
. . .
""") == "Lillebror", "sample 1"

# single chocolate
assert run(""". . .
. . . .
. . O . .
. . . .
. . .
""") == "Karlsson", "single chocolate"

# full board
assert run("""O O O
O O O O
O O O O O
O O O O
O O O
""") in ["Karlsson", "Lillebror"], "maximum board"

# two disconnected chocolates
assert run(""". . .
. O . .
. . O . .
. . . .
. . .
""") == "Lillebror", "two isolated chocolates"

# adjacent pair
assert run(""". . .
. . . .
. O O . .
. . . .
. . .
""") == "Karlsson", "pair position"
Test input Expected output What it validates
Single chocolate Karlsson Single-cell moves are generated
Full board Valid output Handles largest state space
Two disconnected chocolates Lillebror Disconnected cells cannot be removed together
Adjacent pair Karlsson Multi-cell contiguous moves work correctly

Edge Cases

Consider two chocolates lying on the same geometric direction but separated by an empty cell:

. . .
 . O . .
. . O . .
 . . . .
  . . .

A buggy implementation might allow removing both together because they appear aligned. The algorithm avoids this because moves are generated only from contiguous segments inside a maximal line. Since the empty middle cell breaks contiguity, no move mask contains both chocolates simultaneously.

The DFS sees only single-cell removals. After one chocolate is removed, the remaining player removes the other and wins. The result is "Lillebror".

Now consider the smallest non-empty board:

. . .
 . . . .
. . O . .
 . . . .
  . . .

The generated move set includes all length-1 segments, so the lone chocolate is removable. The recursive call reaches state 0, which has no legal moves and is losing. Hence the original state is winning and the output is "Karlsson".

Another subtle case is duplicate move generation from overlapping line logic. The implementation removes duplicates with:

moves = list(set(moves))

Without this, correctness would still hold, but DFS would repeatedly examine identical transitions. Deduplication keeps the search compact and avoids unnecessary recursion overhead.