CF 105638K - Hile counts the Qi

Rating: -
Tags: -
Solve time: 57s
Verified: yes

Solution

Problem Understanding

The board is a grid containing three types of cells: black stones, white stones, and empty intersections. Stones of the same color that touch orthogonally form a single connected group. For every such group, we need to determine how many distinct empty cells are directly adjacent to any stone in the group in the four cardinal directions. These adjacent empty cells represent the liberties, and they are counted per group, not per stone.

The task is to compute, separately for black and white, how many connected groups have exactly one distinct liberty cell.

The grid size is small enough to allow quadratic traversal comfortably. Even if the board is up to a few thousand in each dimension, a solution that performs a constant amount of work per cell and uses flood fill will remain within limits. This rules out any idea that recomputes reachability or adjacency repeatedly per stone, since that would drift toward cubic behavior in dense cases.

A naive but important failure mode comes from counting liberties per stone instead of per group. Consider a line of two black stones with a single empty cell adjacent to both. If we count per stone, we would think each stone has one liberty and conclude incorrectly that both are atari independently. The correct interpretation is that both stones belong to one group whose liberty set has size one.

Another subtle issue arises when the same empty cell touches multiple stones of a group. It must be counted once, not once per adjacency. For example, a plus-shaped group surrounding a single empty center would have one liberty, not four.

Approaches

A brute force approach would examine every stone and perform a local search outward to determine all connected stones in its group, then recompute its liberties by scanning neighbors again. This quickly repeats the same work many times because every stone in a group would trigger a full traversal of the same component. In the worst case of a fully filled board, this degenerates into repeatedly exploring large regions, producing a cubic or near cubic number of operations.

The key observation is that groups are disjoint connected components in a grid graph. Once we identify a component, all required information about it, including its liberty set, can be computed exactly once. This suggests a standard flood fill over same-colored cells, during which we accumulate all adjacent empty cells into a set. Each cell is processed exactly once, and each edge is inspected at most a constant number of times.

This transforms the problem into a connected components traversal with auxiliary aggregation.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n²·k) worst case	O(n²)	Too slow
Optimal Flood Fill	O(n²)	O(n²)	Accepted

Algorithm Walkthrough

Traverse every cell in the grid. When a cell contains a stone and has not been visited yet, treat it as the starting point of a new connected component.
Run a breadth first search or depth first search restricted to cells of the same color. Mark every visited stone so it is never processed again. This ensures each stone belongs to exactly one component traversal.
While exploring the component, whenever a neighboring cell is empty, record its coordinates in a set associated with this component. The set is required so that the same empty intersection reached from multiple stones is counted only once.
After the traversal finishes, check the size of the collected set of liberties. If it is exactly one, increment the counter for that stone color.
Continue until all cells have been processed, and output the two counters.

The reason we explicitly separate traversal and liberty collection is that liberties are a property of the entire connected structure, not individual stones. Mixing per-stone logic would reintroduce duplication of work.

Why it works

Each flood fill discovers exactly one connected component of stones. Because adjacency is four-directional and restricted to same-color expansion, no component can be split or merged incorrectly during traversal. Every empty cell adjacent to the component is discovered at least once through one of its bordering stones, and the use of a set guarantees uniqueness. Therefore the final set of liberties is exactly the true liberty set of the group, making the “exactly one liberty” condition correct for classification.

Python Solution

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**7)

def solve():
    n = int(input().strip())
    grid = [list(input().strip()) for _ in range(n)]

    visited = [[False] * n for _ in range(n)]

    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    black_atari = 0
    white_atari = 0

    def bfs(sr, sc):
        stack = [(sr, sc)]
        visited[sr][sc] = True
        color = grid[sr][sc]
        liberties = set()

        while stack:
            r, c = stack.pop()
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if nr < 0 or nr >= n or nc < 0 or nc >= n:
                    continue
                if grid[nr][nc] == 'E':
                    liberties.add((nr, nc))
                elif not visited[nr][nc] and grid[nr][nc] == color:
                    visited[nr][nc] = True
                    stack.append((nr, nc))

        return color, len(liberties)

    for i in range(n):
        for j in range(n):
            if grid[i][j] != 'E' and not visited[i][j]:
                color, lib_count = bfs(i, j)
                if lib_count == 1:
                    if color == 'B':
                        black_atari += 1
                    else:
                        white_atari += 1

    print(black_atari, white_atari)

if __name__ == "__main__":
    solve()

The implementation keeps a global visited array so that each stone is processed once. The stack-based DFS is used instead of recursion to avoid stack overflow in large connected regions.

The set liberties is the crucial structure that prevents double counting of empty cells shared by multiple stones. Each time a boundary to an empty cell is encountered, it is inserted into the set, and duplicates are automatically ignored.

Worked Examples

Example 1

Input:

5
BWEEW
BBEWE
WEEBW
BBWEE
WBWBE

We track components as they are discovered.

Start Cell	Color	Component Size	Liberties Found (set size)	Result
(0,0)	B	multiple	1	count
(0,1)	already visited	-	-	skip
(0,4)	W	multiple	2	no count
(1,0)	B	multiple	1	count
(2,0)	W	multiple	1	count

This trace shows that multiple stones collapse into single components, and only components with exactly one distinct liberty are counted.

Example 2

Input:

5
WBEEW
EWBBB
BEWBE
EEWBB
BBEBE

Start Cell	Color	Component Size	Liberties Found (set size)	Result
(0,0)	W	single	0	no
(0,4)	W	single	0	no
(1,2)	B	multiple	2	no
(3,4)	B	multiple	1	count

This example highlights that groups with zero liberties are not atari, and only exact single-liberty groups qualify.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Each cell is visited once in DFS, and each edge is checked a constant number of times
Space	O(n²)	Visited array and recursion stack plus liberty set in worst case

The grid is traversed in linear time relative to its size, and each stone belongs to exactly one component exploration, which ensures the solution comfortably handles the maximum board size within limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from __main__ import solve
    return sys.stdout.getvalue()

# provided samples
assert run("""5
BWEEW
BBEWE
WEEBW
BBWEE
WBWBE
""").strip() == "1 2"

assert run("""5
WBEEW
EWBBB
BEWBE
EEWBB
BBEBE
""").strip() == "0 4"

# single stone atari
assert run("""3
EEE
EBE
EEE
""").strip() == "1 0"

# no liberties case
assert run("""3
BBB
BBB
BBB
""").strip() == "0 0"

# single large white group with one liberty
assert run("""3
WWW
WEW
WWW
""").strip() == "0 1"

Test input	Expected output	What it validates
single B surrounded	1 0	single group with exactly one liberty
full black block	0 0	zero liberties case
white ring with hole	0 1	multiple stones sharing one liberty
provided samples	correct outputs	correctness on mixed boards

Edge Cases

A key edge case is when multiple stones share the same single liberty cell. In that situation, a per-stone approach would incorrectly multiply count that liberty, but the set-based aggregation ensures it is counted once. For example, a 2x2 block of stones with a single adjacent empty cell should produce a liberty set of size one for the whole component.

Another case is when a stone is on the border of the board. Out-of-bounds positions must not be treated as liberties, since only in-board empty cells count. The boundary checks in the DFS explicitly skip invalid coordinates, preventing phantom liberties.

A final case is isolated stones with no adjacent empty cells. These represent groups with zero liberties and must not be counted as atari. The algorithm naturally handles this because the liberty set remains empty, and only size exactly equal to one is accepted.