Похибки кодування (Розбір)

Ідея

Нам дано два бінарних рядки $s$ та $g$ довжини $n$. Потрібно серед усіх циклічних зсувів рядка $g$ знайти той, для якого кількість похибок мінімальна. Похибка — це кількість максимальних підвідрізків, на яких відповідні символи рядків відрізняються (тобто кількість "блоків" підряд ідучих позицій, де s_i \neq g'_i).

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

Циклічних зсувів рівно $n$. Для кожного зсуву ми можемо за один прохід порахувати кількість блоків розбіжностей: йдемо зліва направо, і щоразу, коли натрапляємо на позицію s_i \neq g'_i, а попередня позиція або збігалася, або це початок рядка — стартує новий блок.

Оскільки n \le 4 \cdot 10^3 і сума всіх $n$ не перевищує 4 \cdot 10^3, ми можемо собі дозволити перебрати всі $n$ зсувів і для кожного за $O(n)$ порахувати відповідь.

Як реалізувати циклічний зсув?

Замість того щоб кожного разу будувати новий рядок, можна просто зсувати $g$ на місці. На кожному кроці беремо останній символ рядка $g$ і ставимо його на початок — це і є один циклічний зсув вправо:

Підрахунок блоків розбіжностей

Для фіксованого зсуву проходимо по рядку і підтримуємо прапорець $streak$: чи ми зараз "всередині" блоку розбіжностей. Якщо s_i \neq g_i і \mathit{streak} = \mathit{false} — починається новий блок, збільшуємо лічильник. Якщо символи збігаються — скидаємо $streak$.

Відповідь — мінімум по всіх зсувах.

Асимптотика

Зсувів — $n$, для кожного рахуємо блоки за $O(n)$.

Отже маємо O(n^2) на один тестовий випадок, і O\!\left(\left(\sum n\right)^2\right) сумарно, що при обмеженнях задачі не перевищує O\!\left((4 \cdot 10^3)^2\right) = O(1{,}6 \cdot 10^7).

#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'

const ll INF = 1e18;

void solve() {
    ll n;
    string s, s1;
    cin >> n;
    cin >> s >> s1;

    ll res = INF;

    for (int step = 1; step <= n; step++) {
        bool streek = 0;
        ll curr = 0;

        for (int i = 0; i < n; i++) {
            if (s[i] != s1[i]) {
                if (!streek) {
                    streek = 1;
                    curr++;
                }
            } else {
                streek = 0;
            }
        }

        res = min(res, curr);

        // cyclic shift: last character becomes first
        s1 = s1[s1.size() - 1] + s1;
        s1.pop_back();
    }

    cout << res << endl;
}

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