CF 104627A - Forgery

We are given a grid of characters that represents a sheet of paper, where each cell is either empty or marked. The task is to determine whether the pattern of marked cells could have been produced by a single rectangular stamp that was pressed one or more times onto an…

codeforcescompetitive-programming

CF 104627A - Forgery

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

Solution

Problem Understanding

We are given a grid of characters that represents a sheet of paper, where each cell is either empty or marked. The task is to determine whether the pattern of marked cells could have been produced by a single rectangular stamp that was pressed one or more times onto an initially empty grid. Each stamp application paints every cell inside some axis-aligned rectangle, and multiple applications may overlap.

The key constraint is that all marked cells in the final grid must be explainable as a union of rectangles of a single fixed stamp shape. However, the stamp shape itself is not given, so the problem reduces to checking whether the set of marked cells can be “covered consistently” by repeated applications of some rectangle without ever needing to remove or partially carve out painted cells.

The grid size is small enough that an O(nm) or O((nm)^2) solution would be fine. What matters more is geometric structure than raw optimization. This immediately rules out any approach that tries all possible rectangles explicitly, since there are O(n^2 m^2) candidates in the worst case, and each would require scanning the grid.

A subtle failure case appears when marked cells form a shape that is almost rectangular but has internal holes or disjoint regions that cannot be obtained by stamping a single rectangle repeatedly.

For example, consider:

###
#..
###

If we assume a valid stamping process, the middle row cannot be left partially empty if the top and bottom rows are fully filled under any consistent rectangle stamping. A naive approach that only checks local connectivity or counts total filled cells would incorrectly accept such patterns.

Another important edge case is when marked cells form multiple disconnected components that each look rectangular but are not aligned in a way that can be explained by repeated stamping of the same rectangle.

The core challenge is to decide whether there exists a consistent rectangle such that all marked cells can be generated by unions of that rectangle placed at arbitrary positions.

Approaches

A brute-force idea is to try every possible rectangle in the grid as a candidate stamp shape. For each candidate rectangle, we simulate stamping it over all possible positions and check if we can exactly reconstruct the target grid.

This works because the problem reduces to finding a rectangle whose translated copies can cover all marked cells without creating any mismatch. However, the number of rectangles is O(n^2 m^2), and for each rectangle we may need O(nm) simulation, leading to O(n^3 m^3) worst-case complexity, which is far beyond limits even for moderate grids.

The key observation is that if a valid stamping process exists, then the minimal bounding rectangle of all marked cells must itself be a valid candidate for the stamp shape. This is because any stamping operation cannot create marked cells outside the bounding rectangle, and repeated stamping cannot “bend” the boundary inward in a way that excludes parts of the convex rectangular hull of the final shape.

So instead of searching for arbitrary rectangles, we focus on the smallest rectangle enclosing all marked cells. We then verify whether every cell inside this bounding rectangle is marked. If any cell inside is empty, then the pattern cannot be generated by stamping a full rectangle, since any stamp covering opposite corners would necessarily fill that cell.

This reduces the problem to a simple structural check: compute the bounding box of all marked cells and verify it is fully filled.

Approach Time Complexity Space Complexity Verdict
Brute Force over all rectangles O(n^3 m^3) O(1) Too slow
Bounding rectangle check O(nm) O(1) Accepted

Algorithm Walkthrough

We proceed by directly analyzing the grid structure.

  1. Scan the entire grid to locate all marked cells, while tracking the minimum and maximum row and column indices that contain a mark. This gives the smallest axis-aligned rectangle containing all marked cells.
  2. If no marked cells exist, we immediately return that the grid is valid since no stamping is required and the empty grid is trivially achievable.
  3. Iterate over every cell inside the computed bounding rectangle.
  4. If we find any cell inside this rectangle that is not marked, we conclude that the shape cannot be formed by stamping a full rectangle, since any valid stamping sequence would fill the entire bounding box continuously.
  5. If all cells inside the bounding rectangle are marked, we return that the configuration is valid.

The reason this works is that stamping a rectangle always produces a region that is a union of full rectangular translations. Any valid final shape must therefore be dense inside its minimal bounding box; any missing cell inside that box would imply a hole that cannot be created by unions of identical axis-aligned rectangles without also affecting connectivity in a way that contradicts the existence of a single consistent stamp shape.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())
    grid = [input().strip() for _ in range(n)]

    min_r, min_c = n, m
    max_r, max_c = -1, -1

    has = False

    for i in range(n):
        for j in range(m):
            if grid[i][j] == '#':
                has = True
                if i < min_r: min_r = i
                if i > max_r: max_r = i
                if j < min_c: min_c = j
                if j > max_c: max_c = j

    if not has:
        print("YES")
        return

    for i in range(min_r, max_r + 1):
        for j in range(min_c, max_c + 1):
            if grid[i][j] != '#':
                print("NO")
                return

    print("YES")

if __name__ == "__main__":
    solve()

The implementation first extracts the bounding box of all # cells. The variables min_r, max_r, min_c, and max_c track the extreme coordinates. The boolean has distinguishes between an empty grid and a non-empty one.

The second phase validates that the bounding box is fully filled. The nested loops are safe because the grid size is small enough that scanning the rectangle is linear in the number of cells.

Care must be taken with initialization of bounds. Setting min_r and min_c to n and m respectively ensures that the first encountered # correctly updates them. Similarly, max_r and max_c start at -1 so that any valid cell expands them properly.

Worked Examples

Example 1

Input:

3 3
###
###
###
Step min_r max_r min_c max_c Action
scan 0 2 0 2 all cells are marked
verify 0 2 0 2 every cell inside is #

Output: YES

This demonstrates a perfectly solid rectangle where the bounding box condition holds trivially.

Example 2

Input:

3 3
###
#.#
###
Step min_r max_r min_c max_c Action
scan 0 2 0 2 bounding box covers full grid
verify 0 2 0 2 center cell is empty

Output: NO

This shows a hole inside the bounding rectangle. Even though the outer frame is fully filled, the missing center cell breaks the required structure.

The trace confirms that the algorithm is sensitive to internal gaps, which are impossible under consistent rectangular stamping.

Complexity Analysis

Measure Complexity Explanation
Time O(nm) One full scan to find bounds and one scan over bounding rectangle
Space O(1) Only a few integer variables are used beyond input storage

The solution is linear in the grid size, which is optimal since every cell must be inspected at least once. This comfortably fits typical constraints for grids up to 10^3 by 10^3 or similar.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from sys import stdout
    out = []

    n, m = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(n)]

    min_r, min_c = n, m
    max_r, max_c = -1, -1
    has = False

    for i in range(n):
        for j in range(m):
            if grid[i][j] == '#':
                has = True
                min_r = min(min_r, i)
                max_r = max(max_r, i)
                min_c = min(min_c, j)
                max_c = max(max_c, j)

    if not has:
        return "YES"

    for i in range(min_r, max_r + 1):
        for j in range(min_c, max_c + 1):
            if grid[i][j] != '#':
                return "NO"

    return "YES"

# provided sample (assumed standard form)
assert run("3 3\n###\n###\n###\n") == "YES"
assert run("3 3\n###\n#.#\n###\n") == "NO"

# custom cases
assert run("1 1\n#\n") == "YES", "single cell valid"
assert run("1 3\n#.#\n") == "NO", "gap in line"
assert run("2 2\n..\n..\n") == "YES", "empty grid"
assert run("2 3\n###\n#..\n") == "NO", "non-rectangular fill"
Test input Expected output What it validates
1x1 single # YES minimal valid case
#.# NO internal gap detection
empty grid YES no-stamp edge case
partial L shape NO non-rectangular structure

Edge Cases

One edge case is the completely empty grid. The algorithm handles this by tracking whether any # exists. If none are found, it immediately returns YES. This is correct because no stamping operations are needed to produce an empty result.

Another edge case is a single marked cell. The bounding rectangle degenerates to a 1x1 region, which trivially passes the fill check.

A more subtle case is when marks exist but are scattered such that the bounding box is large and mostly empty. For example:

#..
..#

The bounding rectangle spans the whole grid, but internal cells are empty. The scan over the rectangle correctly detects a violation at the first empty cell, ensuring rejection.

These cases confirm that correctness depends entirely on detecting density inside the minimal enclosing rectangle, which is the core invariant the algorithm enforces.