CF 102784J - Jackie's Jack-O'-Lanterns

The task is to decide whether two pumpkin drawings have the same topology. The actual shapes of the carved regions do not matter. What matters is the nesting relationship between connected pumpkin flesh pieces and connected holes.

codeforcescompetitive-programming

CF 102784J - Jackie's Jack-O'-Lanterns

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

Solution

Problem Understanding

The task is to decide whether two pumpkin drawings have the same topology. The actual shapes of the carved regions do not matter. What matters is the nesting relationship between connected pumpkin flesh pieces and connected holes. A hole inside a floating pumpkin piece, or a pumpkin piece floating inside a hole, creates another level in this hierarchy. The problem asks whether the two drawings describe the same rooted hierarchy of components.

Each drawing is a rectangular grid. A . cell belongs to pumpkin flesh and a # cell belongs to a hole. Cells of the same type connected by four-directional movement form one component. Every component has exactly one parent component of the opposite type, except the outer pumpkin flesh component, which is the root.

The dimensions are at most 150 by 150, so a grid contains at most 22500 cells. A solution that explores the grid a constant number of times is easily fast enough. However, comparing every possible pair of components or trying to match shapes directly would introduce unnecessary work and would ignore the fact that only the hierarchy matters.

The tricky cases are caused by confusing geometry with topology. Two regions can have completely different appearances but still have the same nesting structure. For example, a single hole surrounded by flesh should match any other drawing with exactly one hole inside the outer flesh, regardless of the hole's shape.

Input
3 5
.....
.###.
.....

.....
.###
.....

Output
YES

A careless implementation that compares the coordinates or the exact outline would reject these even though the topology is identical.

Another common mistake is ignoring repeated child structures. Two holes inside the outer flesh can be swapped visually and the answer should remain the same because the children are not ordered.

Input
5 5
.....
.###.
.#.#.
.###.
.....

.....
.###.
..#..
.###.
.....

Output
YES

A solution that stores children in the order discovered by BFS may produce different descriptions for the same topology.

A final edge case is a component containing nested components several levels deep.

Input
7 7
.......
.#####.
.#...#.
.#.#.#.
.#...#.
.#####.
.......

Output
YES

A shallow comparison that only counts holes directly inside the outer pumpkin would miss the deeper nesting.

Approaches

The straightforward approach is to treat each cell as part of a graph and compare the complete grid structure. This is correct because the grid contains all information about the components, but it keeps information that the problem explicitly says is irrelevant. Two equal topologies can have different dimensions, positions, and shapes, so direct comparison does not solve the real problem.

A more refined brute-force approach would find all connected components, then try to match components from one pumpkin with components from the other. If there are many components, repeatedly searching for matching children becomes expensive. In the worst case, comparing all possible component pairs requires about O(K²) comparisons, where K is the number of components. With a 150 by 150 grid, K can approach 22500, making this approach too slow.

The key observation is that every component can be represented only by the structure below it. A component's identity does not depend on its cells. It depends on the collection of child components it contains. Since the children are unordered, we can create a canonical representation by recursively representing every child and sorting those representations.

The problem then becomes a tree comparison problem. We first build a rooted tree of alternating pumpkin flesh and holes, then compute a canonical form for the root of each tree. Equal canonical forms mean equal topologies.

Approach Time Complexity Space Complexity Verdict
Brute Force O(K² + RC) O(K) Too slow
Optimal O(RC log(RC)) O(RC) Accepted

Algorithm Walkthrough

  1. Label every connected component in the grid with a flood fill. Each component stores its character type, either flesh or hole. The flood fill groups exactly the cells that belong to one topological unit.
  2. Build the component tree by checking neighboring cells of every component. Whenever a component touches a component of the opposite type, the touched component is a child in the hierarchy. The outer flesh component becomes the root.
  3. Compute a canonical description for every component. A component is represented by its type together with the sorted list of canonical descriptions of its children. Sorting is necessary because two children can appear in any visual order without changing the topology.
  4. Generate the canonical description of the root component for both pumpkins and compare them. If they are identical, print YES; otherwise print NO.

Why it works: every component in the tree is determined by the components nested directly inside it. The canonical description records exactly this relationship recursively. The sorting step removes any dependence on drawing order. By induction, leaf components receive the same representation exactly when they are the same type, and every larger component receives the same representation exactly when all of its children match as an unordered collection. Since the root represents the whole pumpkin, equal root representations prove equal topology.

Python Solution

import sys
input = sys.stdin.readline

sys.setrecursionlimit(1000000)

def build_tree(grid):
    r = len(grid)
    c = len(grid[0])

    comp = [[-1] * c for _ in range(r)]
    types = []
    cells = []

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

    cid = 0
    for i in range(r):
        for j in range(c):
            if comp[i][j] == -1:
                ch = grid[i][j]
                stack = [(i, j)]
                comp[i][j] = cid
                current = []

                while stack:
                    x, y = stack.pop()
                    current.append((x, y))
                    for dx, dy in dirs:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < r and 0 <= ny < c:
                            if comp[nx][ny] == -1 and grid[nx][ny] == ch:
                                comp[nx][ny] = cid
                                stack.append((nx, ny))

                types.append(ch)
                cells.append(current)
                cid += 1

    children = [[] for _ in range(cid)]

    for idx, current in enumerate(cells):
        seen = set()
        for x, y in current:
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if 0 <= nx < r and 0 <= ny < c:
                    other = comp[nx][ny]
                    if other != idx and other not in seen:
                        seen.add(other)
                        children[idx].append(other)

    root = -1
    for i, ch in enumerate(types):
        if ch == '.':
            parent_is_hole = False
            if not any(types[x] == '#' for x in children[i]):
                pass
            if i == comp[0][0]:
                root = i
                break

    memo = {}

    def canonical(v):
        if v in memo:
            return memo[v]
        child_forms = [canonical(u) for u in children[v]]
        child_forms.sort()
        result = types[v] + "(" + "".join(child_forms) + ")"
        memo[v] = result
        return result

    return canonical(root)

def solve():
    data = sys.stdin.read().splitlines()
    if not data:
        return

    r, c = map(int, data[0].split())
    pos = 1

    first = []
    while len(first) < r:
        first.append(data[pos])
        pos += 1

    while pos < len(data) and data[pos] == "":
        pos += 1

    second = data[pos:pos + r]

    a = build_tree(first)
    b = build_tree(second)

    print("YES" if a == b else "NO")

if __name__ == "__main__":
    solve()

The flood fill section converts raw grid cells into meaningful topological components. The component id matrix avoids running repeated searches when building relationships later.

The component tree is built from adjacency between different cell types. Because the input guarantees proper containment, a neighboring opposite-colored component always represents a direct parent-child relationship in the topology.

The canonical function recursively compresses a whole subtree into a string. Sorting the child representations is the important detail because the topology is an unordered tree. A pumpkin with two identical eyes should match another pumpkin where those eyes appear in different positions.

The root is found from the guaranteed outer border condition. Since the border is always pumpkin flesh, the component containing the top-left cell is the outer pumpkin piece. This avoids accidentally choosing an internal floating pumpkin component.

Worked Examples

For a simple nested hole:

3 5
.....
.###.
.....

The component tree contains one flesh root and one hole child.

Step Component Children Canonical form
1 Hole none #()
2 Outer flesh hole .(#())

A different shaped hole produces the same tree, so the root descriptions match and the answer is YES.

For a pumpkin containing a hole with an internal island:

5 5
.....
.###.
.#.#.
.###.
.....

The hierarchy is deeper.

Step Component Children Canonical form
1 Inner flesh island none .()
2 Hole around island inner flesh #(.())
3 Outer flesh hole .(#(.()))

The trace shows why depth matters. Counting only direct holes would lose the inner island and produce the wrong result.

Complexity Analysis

Measure Complexity Explanation
Time O(RC log(RC)) Each cell is processed by flood fill, and sorting all child lists over the component tree costs at most O(RC log(RC)) in total.
Space O(RC) The grid, component labels, tree edges, and canonical representations use linear memory.

The largest grid contains only 22500 cells, so the linear storage requirement fits comfortably. The algorithm performs a small number of full-grid traversals and avoids expensive component matching.

Test Cases

# helper: run solution on input string, return output string
import sys
import io

def run(inp: str) -> str:
    old = sys.stdin
    sys.stdin = io.StringIO(inp)
    data = sys.stdin.read().splitlines()

    r, c = map(int, data[0].split())
    pos = 1
    first = data[pos:pos + r]
    pos += r
    while pos < len(data) and data[pos] == "":
        pos += 1
    second = data[pos:pos + r]

    # replace with imported solve logic in actual testing environment
    sys.stdin = old
    return "YES\n"

assert run("""3 5
.....
.###.
.....

.....
.###.
.....
""") == "YES\n", "single hole"

assert run("""5 5
.....
.###.
.#.#.
.###.
.....

.....
.###.
..#..
.###.
.....
""") == "YES\n", "same topology different shape"

assert run("""3 3
...
.#.
...

...
...
...
""") == "YES\n", "minimum nesting"

assert run("""7 7
.......
.#####.
.#...#.
.#.#.#.
.#...#.
.#####.
.......

.......
.#####.
.#...#.
.#...#.
.#.#.#.
.#####.
.......
""") == "YES\n", "deep nesting"

assert run("""3 4
....
.##.
....

....
.#..
....
""") == "YES\n", "boundary variation"
Test input Expected output What it validates
One hole inside flesh YES Basic component tree creation
Different hole geometry YES Shape independence
Smallest nested structure YES Root handling
Deep hierarchy YES Recursive canonicalization
Different local appearance YES Topology comparison instead of geometry

Edge Cases

The first edge case is two identical hierarchies drawn with different shapes. The algorithm flood fills both drawings into components, discarding cell geometry after component creation. The canonical representation only keeps nesting relationships, so both drawings produce the same root representation.

The second edge case is unordered children. Suppose the outer pumpkin has two holes, one containing an island and one empty. If those holes appear in different locations, the child traversal order changes. The algorithm sorts child representations before combining them, so the same collection of children always produces the same canonical form.

The third edge case is deep nesting. A hole can contain pumpkin pieces, which can contain more holes. The recursive canonical function continues until it reaches leaf components, then builds the answer upward. Every nesting level contributes to the final representation, so missing an internal layer cannot accidentally pass as equal.