Шахівниця (Розбір)

Ідея

Потрібно видалити рівно один рядок та один стовпець таблиці, після чого змінити якомога менше клітинок, щоб отримати шахове розфарбування з нулем у лівому верхньому куті.

Зауважимо, що потрібна таблиця визначається однозначно: у клітинці $(i,j)$ повинно стояти число (i+j)\bmod 2, якщо індексація починається з $1$.

Найпростіше рішення — перебрати всі можливі пари рядка та стовпця, які будемо видаляти, і для кожної з них порахувати кількість неправильних клітинок у таблиці, що залишилася.

Однак існує $nm$ можливих пар, а перевірка кожної потребує $O(nm)$ часу. Загальна складність становитиме O(n^2m^2), що занадто повільно.

Ключове спостереження

Спочатку порівняємо кожну клітинку початкової таблиці з відповідною клітинкою шахового розфарбування.

Визначимо

Тут $\oplus$ позначає побітову операцію XOR.

Таким чином, b_{i,j}=1, якщо клітинка відрізняється від потрібного шахового розфарбування, і b_{i,j}=0 в іншому випадку.

Тепер нехай ми видаляємо рядок $r$ та стовпець $c$.

Усі клітинки, що залишилися, можна розділити на чотири області відносно видаленого рядка та стовпця.

• Ліва верхня: жодна координата не змінюється, тому потрібне значення залишається тим самим.

• Права верхня: індекс стовпця зменшується на один, тому потрібне значення змінюється на протилежне.

• Ліва нижня: індекс рядка зменшується на один, тому потрібне значення змінюється на протилежне.

• Права нижня: обидва індекси зменшуються на один, тому потрібне значення залишається тим самим.

Отже, у лівій верхній та правій нижній областях потрібно змінити всі клітинки, для яких b_{i,j}=1.

У двох інших областях потрібно змінити клітинки, для яких b_{i,j}=0.

Видалені рядок та стовпець не належать жодній із цих областей.

Розв'язок

Можемо обчислювати кількість необхідних змін для кожної пари $(r,c)$ за допомогою двовимірних префіксних сум.

Нехай p_{i,j} — кількість одиниць у прямокутнику від $(1,1)$ до $(i,j)$ у перетвореній таблиці $b$.

Тоді

За допомогою цих префіксних сум можна знайти кількість одиниць у будь-якому прямокутнику за $O(1)$.

Для фіксованого видаленого рядка $r$ та стовпця $c$ позначимо кількості одиниць у чотирьох областях через S_{TL}, S_{TR}, S_{BL} та S_{BR}.

Права верхня область містить (r-1)(m-c) клітинок, а ліва нижня — (n-r)(c-1) клітинок.

Оскільки у цих двох областях потрібно порахувати кількість нулів, загальна кількість необхідних змін дорівнює

Кожну із чотирьох сум можна отримати за $O(1)$ за допомогою префіксних сум.

Таким чином, достатньо перебрати всі можливі рядки та стовпці для видалення, обчислити cost(r,c) і вибрати мінімальне значення.

Відповідь дорівнює

Асимптотика

Побудова двовимірних префіксних сум потребує $O(nm)$ часу.

Існує $nm$ можливих пар видаленого рядка та стовпця, кожну з яких ми перевіряємо за $O(1)$.

Отже, загальна часова складність становить $O(nm)$.

Для зберігання таблиці префіксних сум потрібно $O(nm)$ додаткової пам'яті.

Реалізація

#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;
}