Подарунок#12321

Подарунок (Розбір)

Автор задачі:	Андрій Холод (Connect)
Підготував:	Андрій Холод (Connect)
Аналіз:	Андрій Холод (Connect)

Розв’язок

1) Як описати всі операції змінними

Нехай $r_{i} \in {0, 1}$ r_i \in \{0,1\} — чи інвертуємо рядок $i$ , а $c_{j} \in {0, 1}$ c_j \in \{0,1\} — чи інвертуємо стовпець $j$ . Тоді після всіх операцій елемент стане: $[A_{i, j}^{'} = A_{i, j} \oplus r_{i} \oplus c_{j}]$ [ A'_{i,j} = A_{i,j} \oplus r_i \oplus c_j ]

Умова гарності: $[A_{i, j} \oplus r_{i} \oplus c_{j} = A_{i^{'}, j^{'}} \oplus r_{i^{'}} \oplus c_{j^{'}}]$ [ A_{i,j} \oplus r_i \oplus c_j \;=\; A_{i',j'} \oplus r_{i'} \oplus c_{j'} ] де $i^{'} = n - i + 1$ i' = n-i+1, $j^{'} = m - j + 1$ j' = m-j+1.

Переносимо відоме в одну сторону: $[(r_{i} \oplus r_{i^{'}}) \oplus (c_{j} \oplus c_{j^{'}}) = A_{i, j} \oplus A_{i^{'}, j^{'}}]$ [ (r_i \oplus r_{i'}) \oplus (c_j \oplus c_{j'}) = A_{i,j} \oplus A_{i',j'} ]

2) Зводимо до змінних лише для пар

Розіб’ємо рядки на пари $(i, i^{'})$ (i, i') і стовпці на пари $(j, j^{'})$ (j, j'). Кількість пар: $[R = ⌊ n /2 ⌋, C = ⌊ m /2 ⌋]$ [ R=\lfloor n/2 \rfloor,\quad C=\lfloor m/2 \rfloor ]

Введемо нові змінні: $[R_{i} = r_{i} \oplus r_{i^{'}}, C_{j} = c_{j} \oplus c_{j^{'}}]$ [ R_i = r_i \oplus r_{i'},\quad C_j = c_j \oplus c_{j'} ] для $i = 0.. R - 1$ i=0..R-1, $j = 0.. C - 1$ j=0..C-1.

Тоді для кожної пари рядків $i$ і пари стовпців $j$ маємо рівняння: $[R_{i} \oplus C_{j} = W_{i, j}]$ [ R_i \oplus C_j = W_{i,j} ] де $[W_{i, j} = A_{i, j} \oplus A_{i^{'}, j^{'}}]$ [ W_{i,j} = A_{i,j} \oplus A_{i',j'} ]

3) Необхідна умова існування (перевірка 2х2)

Для фіксованих $i$ і $j$ розглянемо 4 клітинки: $[(i, j), (i^{'}, j^{'}), (i, j^{'}), (i^{'}, j)]$ [ (i,j),\ (i',j'),\ (i,j'),\ (i',j) ] Має виконуватись: $[A_{i, j} \oplus A_{i^{'}, j^{'}} = A_{i, j^{'}} \oplus A_{i^{'}, j}]$ [ A_{i,j}\oplus A_{i',j'} = A_{i,j'} \oplus A_{i',j} ] бо обидва вирази дорівнюють $R_{i} \oplus C_{j}$ R_i \oplus C_j (один раз через $(j, j^{'})$ (j,j'), інший раз через переставлені стовпці). Якщо для хоча б одного такого блока значення різні — рішення не існує, відповідь $- 1$ .

Саме це робиться в коді:

$x = A_{i, j} \oplus A_{i^{'}, j^{'}}$ x = A_{i,j} \oplus A_{i',j'}
$y = A_{i, j^{'}} \oplus A_{i^{'}, j}$ y = A_{i,j'} \oplus A_{i',j}
якщо $x \neq = y$ x \ne y — друкуємо $- 1$
інакше $W_{i, j} = x$ W_{i,j} = x

4) Фіксації при непарних $n$ або $m$

Якщо $n$ непарне, існує центральний рядок $mi d$ . Для нього $i = i^{'}$ i=i' і тому $r_{i} \oplus r_{i^{'}} = 0$ r_i \oplus r_{i'}=0. Тоді з умови: $[A_{mi d, j}^{'} = A_{mi d, j^{'}}^{'} \Rightarrow (c_{j} \oplus c_{j^{'}}) = A_{mi d, j} \oplus A_{mi d, j^{'}}]$ [ A'_{mid,j} = A'_{mid,j'} \Rightarrow (c_j \oplus c_{j'}) = A_{mid,j} \oplus A_{mid,j'} ] Тобто для кожної пари стовпців отримуємо фіксоване значення $C_{j}$ C_j.

Аналогічно, якщо $m$ непарне, є центральний стовпець $mi d c$ і він фіксує кожен $R_{i}$ R_i: $[(r_{i} \oplus r_{i^{'}}) = A_{i, mi d c} \oplus A_{i^{'}, mi d c}]$ [ (r_i \oplus r_{i'}) = A_{i,midc} \oplus A_{i',midc} ]

У коді це робиться через setVal і масиви fixedR/fixedC.

5) Графова інтерпретація рівнянь

Маємо систему: $[R_{i} \oplus C_{j} = W_{i, j}]$ [ R_i \oplus C_j = W_{i,j} ] Це — двочастковий граф: вершини зліва — $R_{i}$ R_i, справа — $C_{j}$ C_j, а ребро $(i, j)$ має “вагу” $W_{i, j}$ W_{i,j}.

Якщо ми знаємо значення однієї вершини, то з ребра одразу знаємо сусіда: $[C_{j} = R_{i} \oplus W_{i, j}, R_{i} = C_{j} \oplus W_{i, j}]$ [ C_j = R_i \oplus W_{i,j},\quad R_i = C_j \oplus W_{i,j} ] Отже, по зв’язній компоненті всі значення визначаються однозначно (з точністю до глобального XOR, якщо компонент не зафіксований).

Саме тому розв’язок робить BFS по компонентах і розставляє значення змінним.

6) Мінімізація кількості операцій

Важливо: ми мінімізуємо кількість операцій рядків/стовпців, а не кількість одиниць у матриці.

Як це пов’язано з $R_{i}$ R_i і $C_{j}$ C_j?

Якщо $R_{i} = 1$ R_i = 1, то в парі рядків $(i, i^{'})$ (i,i') потрібно інвертувати рівно один рядок (це коштує 1 операцію). Якщо $R_{i} = 0$ R_i=0 — або інвертуємо обидва, або жодного (можна зробити 0 операцій у цій парі, бо "обидва" ніколи не вигідно). Тобто мінімальна ціна для пари — це просто $R_{i}$ R_i.
Аналогічно для $C_{j}$ C_j — ціна пари стовпців дорівнює $C_{j}$ C_j.

Отже мінімізувати кількість операцій — це мінімізувати: $[\sum_{i} R_{i} + \sum_{j} C_{j}]$ [ \sum_i R_i + \sum_j C_j ]

7) Що робимо у зв’язній компоненті

Під час BFS для компоненти рахуємо:

$t o t$ — кількість вершин у компоненті (і $R$ -вершин, і $C$ -вершин),
$o n es$ — скільки з них отримали значення 1,
$co m pF i x e d$ compFixed — чи є у компоненті хоча б одна “зафіксована” вершина (через середній рядок/стовпець).

Якщо компонент зафіксований, то значення вже єдині $\Rightarrow$ вартість компоненти = $o n es$ .

Якщо компонент не зафіксований, то можна одночасно інвертувати всі значення в компоненті: $[R_{i} \leftarrow R_{i} \oplus 1, C_{j} \leftarrow C_{j} \oplus 1]$ [ R_i \leftarrow R_i \oplus 1,\quad C_j \leftarrow C_j \oplus 1 ] і всі рівняння збережуться. Тоді ми можемо вибрати дешевший з двох варіантів: $[min (o n es, t o t - o n es)]$ [ \min(ones,\ tot-ones) ]

Сума по всіх компонентах і є відповіддю.

8) Асимптотика

Зберігаємо лише $R \cdot C \leq 2500 \cdot 2500 = 6.25 \cdot 1 0^{6}$ R \cdot C \le 2500 \cdot 2500 = 6.25 \cdot 10^6 значень $W$ .

BFS у такому “повному двочастковому графі” реалізований як:

з вершини-рядка проходимо по всіх $C$ стовпцях;
з вершини-стовпця — по всіх $R$ рядках.

У найгіршому випадку це $O (R \cdot C)$ O(R \cdot C) переходів, що вкладається в обмеження.

Пам’ять: $O (nm)$ для зчитування (у коді матриця як рядки) і $O (R C)$ для $W$ .

Код рішення

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
#define pb push_back

static int n, m, R, C;
static vector<string> s;
static vector<vector<int>> W;

static vector<int> valR, valC;
static vector<int> fixedR, fixedC;
static vector<int> visR, visC;

static deque<int> q;
static ll answer;

int bitAt(int i, int j) {
    return s[i][j] - '0';
}

bool setVal(vector<int>& val, vector<int>& fx, int idx, int need) {
    if (val[idx] == -1) {
        val[idx] = need;
        fx[idx] = 1;
        return true;
    }
    return val[idx] == need;
}

bool pushRow(int i, int v) {
    if (valR[i] == -1) valR[i] = v;
    else if (valR[i] != v) return false;
    return true;
}

bool pushCol(int j, int v) {
    if (valC[j] == -1) valC[j] = v;
    else if (valC[j] != v) return false;
    return true;
}

bool bfs_component(int start) {
    bool compFixed = false;
    ll ones = 0, tot = 0;

    q.clear();
    q.push_back(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop_front();

        if (node < R) {
            int i = node;
            if (visR[i]) continue;
            visR[i] = 1;

            tot++;
            if (fixedR[i]) compFixed = true;
            if (valR[i] == 1) ones++;

            int vr = valR[i];
            for (int j = 0; j < C; j++) {
                int needC = vr ^ W[i][j];
                if (!pushCol(j, needC)) return false;
                if (!visC[j]) q.push_back(R + j);
            }
        } else {
            int j = node - R;
            if (visC[j]) continue;
            visC[j] = 1;

            tot++;
            if (fixedC[j]) compFixed = true;
            if (valC[j] == 1) ones++;

            int vc = valC[j];
            for (int i = 0; i < R; i++) {
                int needR = vc ^ W[i][j];
                if (!pushRow(i, needR)) return false;
                if (!visR[i]) q.push_back(i);
            }
        }
    }

    if (compFixed) answer += ones;
    else answer += min(ones, tot - ones);

    return true;
}

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

    s.assign(n, "");
    for (int i = 0; i < n; i++) {
        s[i].reserve(m);
        for (int j = 0; j < m; j++) {
            char c;
            cin >> c;
            s[i].push_back(c);
        }
    }

    R = n / 2;
    C = m / 2;

    W.assign(R, vector<int>(C, 0));

    valR.assign(R, -1);
    valC.assign(C, -1);
    fixedR.assign(R, 0);
    fixedC.assign(C, 0);
    visR.assign(R, 0);
    visC.assign(C, 0);

    answer = 0;

    for (int i = 0; i < R; i++) {
        int i2 = n - 1 - i;
        for (int j = 0; j < C; j++) {
            int j2 = m - 1 - j;

            int a1 = bitAt(i, j);
            int a2 = bitAt(i2, j2);
            int a3 = bitAt(i, j2);
            int a4 = bitAt(i2, j);

            int x = a1 ^ a2;
            int y = a3 ^ a4;

            if (x != y) {
                cout << -1 << endl;
                return;
            }
            W[i][j] = x;
        }
    }

    if (n & 1) {
        int mid = n / 2;
        for (int j = 0; j < C; j++) {
            int j2 = m - 1 - j;
            int need = bitAt(mid, j) ^ bitAt(mid, j2);
            if (!setVal(valC, fixedC, j, need)) {
                cout << -1 << endl;
                return;
            }
        }
    }

    if (m & 1) {
        int midc = m / 2;
        for (int i = 0; i < R; i++) {
            int i2 = n - 1 - i;
            int need = bitAt(i, midc) ^ bitAt(i2, midc);
            if (!setVal(valR, fixedR, i, need)) {
                cout << -1 << endl;
                return;
            }
        }
    }

    for (int i = 0; i < R; i++) {
        if (valR[i] != -1 && !visR[i]) {
            if (!bfs_component(i)) {
                cout << -1 << endl;
                return;
            }
        }
    }
    for (int j = 0; j < C; j++) {
        if (valC[j] != -1 && !visC[j]) {
            if (!bfs_component(R + j)) {
                cout << -1 << endl;
                return;
            }
        }
    }

    for (int i = 0; i < R; i++) {
        if (!visR[i]) {
            if (valR[i] == -1) valR[i] = 0;
            if (!bfs_component(i)) {
                cout << -1 << endl;
                return;
            }
        }
    }
    for (int j = 0; j < C; j++) {
        if (!visC[j]) {
            if (valC[j] == -1) valC[j] = 0;
            if (!bfs_component(R + j)) {
                cout << -1 << endl;
                return;
            }
        }
    }

    cout << answer << endl;
}

signed main() {
    speed;
    int test = 1;
    // cin >> test;
    while (test--) solve();
    return 0;
}

C++