Nasser's Grid Components#13101

Nasser's Grid Components (Editorial)

Problem Author:	Mohammad Nasser (MOAGEZA)
Prepared by:	Mohammad Nasser (MOAGEZA)
Edited by:	Hasan Saleh (MathModel)

Solution

General Idea:

Let $L_{c}$ L_c be the size of the largest connected component using only columns $1, \dots, c$ 1, \ldots, c, and let $R_{c}$ R_c be the size of the largest connected component using only columns $c, \dots, m$ c, \ldots, m. A split at column $c$ gives exactly $L = L_{c}$ L = L_c and $R = R_{c + 1}$ R = R_{c+1}, so the answer is

1 \leq c < m min ∣ L_{c} - R_{c + 1} ∣ .

\min_{1 \le c < m} \left| L_c - R_{c+1} \right|.

Computing $L_{c}$ L_c for all $c$ :

Adding a new column to the left part never splits a component; it can only create new cells, or merge existing components together. So we can use a Disjoint Set Union (DSU) that stores the size of each component, and add the columns one by one from left to right:

For each cell $(i, j)$ in column $j$ , if $a_{i, j} = a_{i - 1, j}$ a_{i,j} = a_{i-1,j}, merge the two cells (vertical edge).
If $a_{i, j} = a_{i, j - 1}$ a_{i,j} = a_{i,j-1}, merge the two cells (horizontal edge to the previous column).
Maintain $mx$ , the maximum component size seen so far. Since component sizes never decrease, after finishing column $j$ we have $L_{j} = mx$ L_j = \mathit{mx}.

Computing $R_{c}$ R_c for all $c$ :

Do exactly the same thing in the opposite direction: use a fresh DSU, add the columns from $m$ down to $1$ , merging each cell with the cell below it and with the cell to its right. After finishing column $j$ , set $R_{j} = mx$ R_j = \mathit{mx}.

Combining:

Iterate over all $1 \leq c < m$ 1 \le c < m and take the minimum of $∣ L_{c} - R_{c + 1} ∣$ |L_c - R_{c+1}|.

Complexity:

Each of the $n \cdot m$ n \cdot m cells performs a constant number of DSU operations in each of the two passes. With path compression, the solution runs in $O (\sum n \cdot m \cdot α (n \cdot m))$ \mathcal{O}\!\left(\sum n \cdot m \cdot \alpha(n \cdot m)\right) time, which is practically linear, and uses $O (n \cdot m)$ \mathcal{O}(n \cdot m) memory.

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

struct DSU {
    vector<int> p;
    DSU(int n) : p(n) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    void unite(int a, int b) { p[find(a)] = find(b); }
};

void solve() {
    int n, m;
    cin >> n >> m;
    int sz = n * m + 5;
    vector<vector<int>> a(n + 2, vector<int>(m + 2, 0)), pos(n + 2, vector<int>(m + 2, 0));
    vector<int> res(sz, 0), L(m + 2, 0), R(m + 2, 0);

    int p = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            pos[i][j] = p;
            res[p] = 1;
            p++;
        }

    auto join = [&](DSU &d, int u, int v, int &mx) {
        int x = d.find(u), y = d.find(v);
        if (x == y) return;
        d.unite(x, y);
        int z = d.find(x);
        res[z] = res[x] + res[y];
        mx = max(mx, res[z]);
    };

    // left to right
    DSU l(sz);
    int mx = 1;
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            if (a[i][j] == a[i - 1][j]) join(l, pos[i][j], pos[i - 1][j], mx);
            if (a[i][j] == a[i][j - 1]) join(l, pos[i][j], pos[i][j - 1], mx);
        }
        L[j] = mx;
    }

    // right to left
    for (int p2 = 1; p2 < sz; p2++) res[p2] = 1;
    DSU r(sz);
    mx = 1;
    for (int j = m; j >= 1; j--) {
        for (int i = 1; i <= n; i++) {
            if (i + 1 <= n && a[i][j] == a[i + 1][j]) join(r, pos[i][j], pos[i + 1][j], mx);
            if (j + 1 <= m && a[i][j] == a[i][j + 1]) join(r, pos[i][j], pos[i][j + 1], mx);
        }
        R[j] = mx;
    }

    int ans = 1e9;
    for (int c = 1; c < m; c++)
        ans = min(ans, abs(L[c] - R[c + 1]));
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}