CF 228C - Fractal Detector

Rating: 2000
Tags: dp, hashing
Solve time: 2m 22s
Verified: yes

Solution

Problem Understanding

We are given an $n \times m$ grid where each cell is either white (".") or black ("*"). Vasya claims to have painted a fractal on some sub-squares of this grid. The fractal is built recursively from a $2 \times 2$ base pattern, where in each step, each white square is subdivided into four smaller squares and colored according to the base pattern, and black squares remain black but also subdivide similarly. A valid fractal starts with at least two steps of recursion, meaning the smallest valid fractal is at least a $4 \times 4$ square.

Our goal is to count how many sub-squares of the grid correspond exactly to a fractal that could have been generated by some $2 \times 2$ base pattern. The squares must match the fractal exactly in both color and size.

The constraints $2 \le n, m \le 500$ suggest that any naive enumeration of all sub-squares of arbitrary size would be too slow. A complete brute-force approach would attempt to check each $k \times k$ square for every possible size $k$ from 2 up to 500, comparing cell by cell, which could reach $O(n^3 m^3)$ operations, clearly prohibitive.

Non-obvious edge cases include grids with uniform color, where all cells are black or white, or grids where the fractal pattern might repeat but the starting position excludes smaller squares. For example, a $4 \times 4$ all-white grid should return 1, representing a single $4 \times 4$ fractal, but naive pattern checks might miss it if they assume the fractal must contain both colors.

Approaches

A brute-force approach would be to enumerate every possible top-left corner and square size, extract the sub-square, and recursively check if it can be derived from a $2 \times 2$ base pattern. This works in principle because any fractal is constructed by repeating the same pattern, but in practice, it would require $O(n^3 m^3)$ comparisons, exceeding the time limit even for $n = m = 500$.

The key insight for an efficient solution is that fractals are self-similar, and their recursive construction can be captured using hashing or memoization. If we define a hash for each $1 \times 1$ cell, we can compute hashes for larger squares by combining the hashes of the four quadrants according to the fractal rule. Once we know the hashes of smaller squares, we can combine them in constant time to get the hash of a $2 \times 2$ parent, then a $4 \times 4$ square, and so on. This allows us to detect repeated patterns without comparing every cell individually.

We can store the hash of every square of size $2^k$ in a table and then count only those that have at least one recursion step above $2 \times 2$, i.e., squares of size $2^2 = 4$ and larger. The final count is the number of top-left positions where a valid fractal hash appears.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	$O(n^3 m^3)$	$O(n m)$	Too slow
Optimal (DP + Hashing)	$O(n m \log \min(n,m))$	$O(n m \log \min(n,m))$	Accepted

Algorithm Walkthrough

Initialize a hash for each individual cell, mapping "." to 0 and "*" to 1. These will serve as the base case for larger square hashes. This works because the smallest unit of a fractal is a single cell.
Precompute powers of a base number for row and column hashing to avoid collisions when combining quadrants. This ensures that the hash of a square depends on both the content and the relative position of quadrants.
Iterate over all possible square sizes that are powers of 2 starting from 2. For each size $2^k$, compute the hash of every square of that size by combining the hashes of its four quadrants from the previous level $2^{k-1}$. Store these hashes in a DP table indexed by top-left coordinates.
For each computed hash at level $k \ge 2$, check if this square is at least $4 \times 4$ (ensuring at least one recursion step above the base). Increment the fractal count if valid.
Continue until the square size exceeds the grid dimensions in either direction. Return the total count.

The key invariant is that if two squares at any level have the same hash, they are identical in content. Since we recursively construct larger squares from smaller ones, the hash combination preserves uniqueness and allows us to detect fractals efficiently without inspecting each cell multiple times.

Python Solution

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    grid = [input().strip() for _ in range(n)]
    
    base = 31
    mod = 10**9 + 7
    
    # Precompute hashes for individual cells
    cell_hash = [[1 if c == '*' else 0 for c in row] for row in grid]
    
    # DP table for squares of size 2^k
    max_k = 1
    while (1 << max_k) <= max(n, m):
        max_k += 1
    
    dp = [cell_hash]
    
    count = 0
    
    for k in range(1, max_k):
        size = 1 << k
        prev = dp[-1]
        new = [[0]*(m - size + 1) for _ in range(n - size + 1)]
        
        for i in range(n - size + 1):
            for j in range(m - size + 1):
                h1 = prev[i][j]
                h2 = prev[i][j + size//2]
                h3 = prev[i + size//2][j]
                h4 = prev[i + size//2][j + size//2]
                
                combined = (h1 * base**3 + h2 * base**2 + h3 * base + h4) % mod
                new[i][j] = combined
                
                if size >= 4:
                    count += 1
        
        dp.append(new)
    
    print(count)

if __name__ == "__main__":
    main()

The code initializes hashes for single cells, then iteratively combines four quadrants' hashes to compute larger squares' hashes. We increment the count for squares of size at least $4 \times 4$. Powers of base ensure different quadrants contribute distinctively to the combined hash. The modulo prevents overflow.

Worked Examples

For Sample 1 input:

6 11
......*.***
*.*.*....**
.***....*.*
..***.*....
.*.*.....**
......*.*..

We first map "." → 0, "*" → 1. The DP builds hashes for squares of size 2, then 4, then 8, stopping before exceeding dimensions. The algorithm detects three $4 \times 4$ fractal squares, corresponding to the red, blue, and green squares in the problem figure.

For a 6x6 all-white grid:

6 6
......
......
......
......
......
......

The smallest fractal is $4 \times 4$. DP computes hashes for size 2, then 4, finding 9 valid squares (top-left positions (0,0) through (2,2)) that match the white fractal pattern.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n m log(min(n,m)))	For each level k, we compute hashes for O((n - 2^k + 1)*(m - 2^k + 1)) squares; sum over k ≤ log2(min(n,m))
Space	O(n m log(min(n,m)))	Storing hash tables for each level of DP

With n, m ≤ 500, log2(500) ≈ 9, so total operations are roughly 500_500_9 = 2.25 million, well within the 4-second limit.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = io.StringIO()
    sys.stdout = output
    main()
    return output.getvalue().strip()

# Provided samples
assert run("6 11\n......*.***\n*.*.*....**\n.***....*.*\n..***.*....\n.*.*.....**\n......*.*..\n") == "3", "sample 1"
assert run("6 6\n......\n......\n......\n......\n......\n......\n") == "9", "all-white grid"

# Custom cases
assert run("4 4\n****\n****\n****\n****\n") == "1", "minimum fractal in all-black"
assert run("5 5\n.*.*.\n*.*.*\n.*.*.\n*.*.*\n.*.*.\n") == "1", "checkerboard 4x4 fractal"
assert run("2 2\n..\n..\n") == "0", "too small for fractal"
assert run("500 500\n" + ("