Chessboard (Editorial)

Idea

We need to delete exactly one row and one column, then change as few cells as possible to obtain a chessboard pattern with $0$ in the top-left corner.

Notice that the required final table is uniquely determined: the cell at position $(i,j)$ must contain (i+j)\bmod 2, using $1$-based indexing.

A straightforward solution would try every possible pair of a row and a column to delete, then count the mismatching cells in the remaining table.

However, there are $nm$ possible pairs, and checking each one takes $O(nm)$ time. This gives O(n^2m^2), which is too slow.

Key Observation

Let's first compare every cell of the original table with the chessboard pattern.

Define

Here, $\oplus$ denotes the bitwise XOR operation.

Thus, b_{i,j}=1 if the cell differs from the chessboard pattern, and b_{i,j}=0 otherwise.

Now suppose we delete row $r$ and column $c$.

All remaining cells can be divided into four regions relative to the deleted row and column.

• Top-left: neither coordinate changes, so the required value stays the same.

• Top-right: the column index decreases by one, so the required value flips.

• Bottom-left: the row index decreases by one, so the required value flips.

• Bottom-right: both indices decrease by one, so the required value stays the same.

Therefore, in the top-left and bottom-right regions, we need to change cells where b_{i,j}=1.

In the other two regions, we need to change cells where b_{i,j}=0.

The deleted row and column are not included in any of these regions.

Solution

We can calculate the required number of changes for every pair $(r,c)$ using two-dimensional prefix sums.

Let p_{i,j} be the number of ones in the rectangle from $(1,1)$ to $(i,j)$ in the transformed table $b$.

Then

Using these prefix sums, we can find the number of ones in any rectangular region in $O(1)$ time.

For a fixed deleted row $r$ and column $c$, denote the numbers of ones in the four regions by S_{TL}, S_{TR}, S_{BL} and S_{BR}.

The top-right region contains (r-1)(m-c) cells, while the bottom-left region contains (n-r)(c-1) cells.

Since we need to count zeros in these two regions, the number of required changes is

Each of the four sums can be obtained from the prefix sums in constant time.

Thus, we simply enumerate all possible deleted rows and columns, calculate cost(r,c), and take the minimum.

The answer is

Complexity Analysis

Building the two-dimensional prefix sums takes $O(nm)$ time.

There are $nm$ possible pairs of a deleted row and column, and each pair is evaluated in $O(1)$ time.

Therefore, the total time complexity is $O(nm)$.

The prefix sum table requires $O(nm)$ additional memory.

Implementation

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> p(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;

        for (int j = 1; j <= m; j++) {
            int x = (s[j - 1] - '0') ^ ((i + j) & 1);

            p[i][j] = x + p[i - 1][j] + p[i][j - 1]
                        - p[i - 1][j - 1];
        }
    }

    int ans = n * m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int tl = p[i - 1][j - 1];

            int tr = p[i - 1][m] - p[i - 1][j];

            int bl = p[n][j - 1] - p[i][j - 1];

            int br = p[n][m] - p[i][m]
                   - p[n][j] + p[i][j];

            int cost = tl + br;

            cost += (i - 1) * (m - j) - tr;
            cost += (n - i) * (j - 1) - bl;

            ans = min(ans, cost);
        }
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}