Сжатие

Очень легко привести входные данные в несжатый вид (входные данные были даны в сжатом формате для того, чтобы сделать ограничения больше, но при этом менее зависимыми от времени на чтение данных).

Авторское решение выглядит следующим образом:

Пусть 𝑥
 — ответ на задачу, и изначально он равен 𝑛
. Переберем все строки матрицы и посчитаем длины максимальных по включению отрезков состоящих только из нулей или только из единиц. Пусть длина текущего отрезка равна 𝑙𝑒𝑛
. Тогда присвоим 𝑥:=𝑔𝑐𝑑(𝑥,𝑙𝑒𝑛)
, где 𝑔𝑐𝑑
 — функция, считающая наибольший общий делитель. Затем сделаем тоже самое для столбцов матрицы и выведем ответ.

Как доказать, что это решение работает?

С одной стороны, если какой-то отрезок вида [1+𝑙𝑥,1+(𝑙+1)𝑥]
, где 𝑙
 — это значение из отрезка [0;𝑛𝑥−1]
, содержит различные цифры, то тогда мы не сможем сжать заданную матрицу.

С другой стороны, если предыдущее условие верно, то мы можем сжать каждую строку по следующему алгоритму: откусим первые 𝑥
 символов строки и сожмем оставшуюся строку рекурсивно. После такого сжатия мы получим матрицу размера 𝑛×𝑛𝑥
. И из-за первого условия мы можем сжать оставшуюся матрицу снова при помощи этого алгоритма, если мы применим его к столбцам, а не строкам.

#include <bits/stdc++.h>

using namespace std;

const int N = 5200;

int n;
bool a[N][N];

void parse_char(int x, int y, char c) {
    int num = -1;
    if (isdigit(c)) {
        num = c - '0';
    } else {
        num = c - 'A' + 10;
    }
    for (int i = 0; i < 4; ++i) {
        a[x][y + 3 - i] = num & 1;
        num >>= 1;
    }
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif


    scanf("%d", &n);
    char buf[N];
    for (int i = 0; i < n; ++i) {
        scanf("%s", buf);
        for (int j = 0; j < n / 4; ++j) {
            parse_char(i, j * 4, buf[j]);
        }
    }

    int g = n;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int k = j;
            while (k < n && a[i][k] == a[i][j]) ++k;
            g = __gcd(g, k - j);
            j = k - 1;
        }
    }

    for (int j = 0; j < n; ++j) {
        for (int i = 0; i < n; ++i) {
            int k = i;
            while (k < n && a[k][j] == a[i][j]) ++k;
            g = __gcd(g, k - i);
            i = k - 1;
        }
    }

    cout << g << endl;

    return 0;
}