Kodlaşdırma Səhvləri (Həll təhlili)

İdeya

Bizə uzunluğu $n$ olan iki ikili sətir $s$ və $g$ verilir. $g$ sətirinin bütün dövri sürüşmələri arasında elə birini tapmalıyıq ki, xətaların sayı minimum olsun. Xəta — uyğun simvolların fərqləndiyi maksimal altseqmentlərin sayıdır (yəni s_i \neq g'_i olan ardıcıl mövqelərin "blok"larının sayı).

Əsas müşahidə

Dəqiq $n$ dövri sürüşmə var. Hər sürüşmə üçün bir keçiddə uyğunsuzluq bloklarının sayını hesablaya bilərik: soldan sağa gedirik və hər dəfə s_i \neq g'_i olan mövqeyə rast gəldikdə, əvvəlki mövqe ya uyğun olubsa, ya da bu sətirin başlanğıcıdırsa, yeni blok başlayır.

n \le 4 \cdot 10^3 və bütün $n$-lərin cəmi 4 \cdot 10^3-ü keçmədiyinə görə, bütün $n$ sürüşməni yoxlayıb hər biri üçün cavabı $O(n)$-də hesablaya bilərik.

Dövri sürüşməni necə həyata keçirməli?

Hər dəfə yeni sətir yaratmaq əvəzinə, sadəcə $g$ sətirini yerində sürüşdürə bilərik. Hər addımda sətirin son simvolunu götürüb əvvələ qoyuruq — bu, sağa bir dövri sürüşmədir:

Uyğunsuzluq bloklarının sayılması

Sabit bir sürüşmə üçün sətiri gəzib $streak$ bayrağını saxlayırıq: hazırda uyğunsuzluq blokunun "içində" olub-olmadığımızı göstərir. Əgər s_i \neq g_i və \mathit{streak} = \mathit{false} isə — yeni blok başlayır, buna görə sayğacı artırırıq. Əgər simvollar uyğun gəlirsə — $streak$-i sıfırlayırıq.

Cavab bütün sürüşmələr üzrə minimumdur.

Mürəkkəblik

$n$ sürüşmə var və hər biri üçün blokları $O(n)$-də sayırıq.

Beləliklə, bir test case üçün O(n^2), ümumilikdə isə O\!\left(\left(\sum n\right)^2\right) alırıq; bu da məsələ şərtlərinə görə O\!\left((4 \cdot 10^3)^2\right) = O(1{,}6 \cdot 10^7)-dən çox deyil.

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