CF 1119C - Ramesses and Corner Inversion

Rating: 1500
Tags: constructive algorithms, greedy, implementation, math
Solve time: 1m 4s
Verified: yes

Solution

Problem Understanding

We are given two matrices, A and B, of size n × m filled with 0s and 1s. We can modify A by repeatedly selecting any submatrix of size at least 2 × 2 and flipping its four corner values. The task is to determine whether it is possible to transform A into B using any sequence of such corner flips.

In practical terms, each corner flip toggles a 0 to 1 or a 1 to 0. Since only corners of rectangles are affected, the smallest rectangle we can operate on is 2 × 2. A single corner cannot be toggled in isolation, and edges that do not belong to at least one 2 × 2 rectangle cannot be modified independently. For example, the bottom-right corner of a 1 × 1 matrix cannot be changed at all, making single-row or single-column matrices a special case.

The problem bounds are moderate: n, m ≤ 500. With up to 250,000 cells, a brute-force attempt that tests all possible submatrices would be too slow, since the number of rectangles in a matrix grows roughly as O(n²m²). We need an approach that checks the feasibility of transforming A into B without simulating every operation explicitly.

Edge cases include very small matrices (1 × n or n × 1) where no operation is possible, and matrices where only the last row or column differs. For instance, if

A = [[0, 1]]
B = [[1, 0]]

no 2 × 2 submatrix exists, so the answer must be No. Any solution must carefully account for these situations.

Approaches

The naive approach is to try all possible 2 × 2 submatrices, flipping corners whenever A[i][j] ≠ B[i][j]. This can work for small matrices but becomes infeasible when n and m approach 500. The worst-case complexity would be O(n²m²) just for checking all rectangles, far too slow for the given limits.

The key observation is that a 2 × 2 flip affects exactly four cells: the top-left, top-right, bottom-left, and bottom-right of the rectangle. Therefore, to match A to B, the differences between the two matrices can be handled locally by propagating flips from top-left to bottom-right. Specifically, if we decide on a flip at position (i, j), it will only affect corners at (i,j), (i,j+1), (i+1,j), (i+1,j+1).

This leads to a greedy algorithm: iterate from the top-left corner, and whenever the current cell differs from B, flip the 2 × 2 submatrix with this cell as the top-left corner. By processing cells in order, each flip addresses the current mismatch without disturbing previous cells that are already correct. The only cells that cannot be covered by a 2 × 2 flip are those in the last row or last column, which must already match B for a solution to exist.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force (all rectangles)	O(n²m²)	O(nm)	Too slow
Greedy Top-Left Propagation	O(nm)	O(nm)	Accepted

Algorithm Walkthrough

Compute the difference matrix D = A XOR B. Each cell is 1 if A differs from B and 0 if they are already equal. This encodes where flips are needed.
Iterate over the matrix from top-left to bottom-right, excluding the last row and last column (i = 0..n-2, j = 0..m-2). For each cell (i,j):

If D[i][j] is 1, apply a flip to the 2 × 2 submatrix with top-left corner (i,j).
Update the four corners in D by toggling them (D[i][j] ^= 1, D[i][j+1] ^= 1, D[i+1][j] ^= 1, D[i+1][j+1] ^= 1).

After processing all possible 2 × 2 flips, check the last row (i = n-1) and last column (j = m-1). If any D[i][j] is 1 in these areas, output No; otherwise, output Yes.

Why it works: Each flip is chosen to fix a mismatch at the top-left of the current 2 × 2 rectangle. Since previous rows and columns have already been fixed, future flips never disturb already corrected cells. The process guarantees that if all differences can be resolved using 2 × 2 flips, the last row and column will automatically be zeroed. Otherwise, a mismatch in these areas cannot be fixed, signaling an impossible transformation.

Python Solution

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
B = [list(map(int, input().split())) for _ in range(n)]

# Step 1: difference matrix
D = [[A[i][j] ^ B[i][j] for j in range(m)] for i in range(n)]

# Step 2: greedy top-left flips
for i in range(n - 1):
    for j in range(m - 1):
        if D[i][j]:
            D[i][j] ^= 1
            D[i][j+1] ^= 1
            D[i+1][j] ^= 1
            D[i+1][j+1] ^= 1

# Step 3: check last row and column
possible = True
for i in range(n):
    if D[i][m-1]:
        possible = False
for j in range(m):
    if D[n-1][j]:
        possible = False

print("Yes" if possible else "No")

Each part mirrors the algorithm steps. The XOR operation builds a difference matrix, the nested loops implement greedy flips, and the final check ensures no unmatched cells remain where a 2 × 2 flip cannot reach. A subtle point is excluding the last row and column from the greedy loop to avoid index errors.

Worked Examples

Sample 1

Input:

i,j	D before flip	Flip applied?	D after flip
0,0	1	Yes	corners toggled
0,1	0	No	unchanged
1,0	1	Yes	corners toggled
1,1	0	No	unchanged

All cells in last row and column are 0 → output Yes. This confirms that greedy flips propagate differences correctly and leave edges consistent.

Sample 2

Input:

i,j	D before flip	Flip applied?	D after flip
0,0	1	Yes	corners toggled

No unmatched cells in last row or column → output Yes. Shows minimal 2 × 2 matrix works correctly.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(nm)	Each cell is visited once; flips are constant-time
Space	O(nm)	Difference matrix stored explicitly

The solution runs well under 1s for n, m ≤ 500 and uses modest memory. The operations are simple XORs, making the code fast in practice.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    n, m = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(n)]
    B = [list(map(int, input().split())) for _ in range(n)]
    D = [[A[i][j] ^ B[i][j] for j in range(m)] for i in range(n)]
    for i in range(n-1):
        for j in range(m-1):
            if D[i][j]:
                D[i][j] ^= 1
                D[i][j+1] ^= 1
                D[i+1][j] ^= 1
                D[i+1][j+1] ^= 1
    possible = all(D[i][m-1] == 0 for i in range(n)) and all(D[n-1][j] == 0 for j in range(m))
    return "Yes" if possible else "No"

# Provided samples
assert run("3 3\n0 1 0\n0 1 0\n1 0 0\n1