Üçlü#12369

Üçlü (Həll təhlili)

Problem Müəllifi:	Andriy Kholod (Connect)
Hazırlayan:	Andriy Kholod (Connect)
Analiz:	Andriy Kholod (Connect)

Fikir

İkinci mərhələdə yalnız alt massivləri onların cəminə sıxışdıra bilərik. Bu, son massiv $[x, x, x]$ [x,x,x]-nin həmişə ilkin massivdən üç boş olmayan ardıcıl hissəyə bərabər cəmlərlə bölünməsini ifadə edir.

Yəni, birinci mərhələdə bütün əvəzləmələrdən sonra massiv belə olmalıdır ki, $1 \leq i < j < n$ 1 \le i < j < n indeksləri mövcud olsun və aşağıdakı şərt ödənilsin:

$\sum_{k = 1}^{i} a_{k} = \sum_{k = i + 1}^{j} a_{k} = \sum_{k = j + 1}^{n} a_{k}$ \sum_{k=1}^{i} a_k = \sum_{k=i+1}^{j} a_k = \sum_{k=j+1}^{n} a_k

Beləliklə, problem əslində: massivin üç boş olmayan alt massivə bərabər cəmlərlə bölünməsi üçün minimum sayda elementi dəyişməkdir.

Niyə cavab 2-dən böyük deyil

Həmişə iki elementdən çoxunu dəyişə bilməzsiniz.

Həqiqətən, üç boş olmayan hissəyə istənilən bölməni götürün, məsələn: $a_{1}, a_{2}, a_{3}, \dots, a_{n}$ { {a_1}, {a_2}, {a_3,\dots,a_n} } Sonra birinci hissədə bir elementi və ikinci hissədə bir elementi dəyişə bilərsiniz ki, bütün üç hissənin cəmləri bərabər olsun.

Buna görə də, cavab həmişə aşağıdakilərdən biridir: $[0, 1, 2]$ [ 0,\ 1,\ 2 ]

Beləliklə, yoxlamağı öyrənmək kifayətdir:

cavabın $0$ olub-olmadığını;
cavabın $1$ olub-olmadığını;
əks halda, cavabın $2$ olduğunu.

0 dəyişiklik halı

Tutaq ki, $S = \sum_{i = 1}^{n} a_{i}$ S = \sum_{i=1}^{n} a_i

Heç bir elementi dəyişməsək, onda massiv artıq üç bərabər cəmlə bölünə bilməlidir. Beləliklə, aşağıdakı şərt ödənilməlidir: $S \equiv 0 (mod 3)$ S \equiv 0 \pmod 3 və hər hissənin cəmi $x = S /3$ x = S/3

Bu, prefiks cəmləri istifadə edərək çox sadə bir şəkildə yoxlanıla bilər:

$x$ cəminə sahib bir prefiks axtarın;
sonra daha sağda $2 x$ cəminə sahib bir prefiks axtarın.

Hər ikisi mövcud olduqda və üçüncü hissə boş olmadıqda, cavab $0$ -dır.

Bir dəyişiklik kifayət edəndə

Tutaq ki, tam olaraq bir elementi dəyişmək istəyirik. Ondan sonra massiv üç bərabər cəmlə bölünməlidir.

Əsas müşahidə: yalnız bir element dəyişdirilirsə, o, dəqiq üç hissədən birində yerləşir. Beləliklə, digər iki hissənin artıq bərabər cəmləri olmalıdır. Üçüncü hissəni bu dəyərə bir dəyişikliklə "çəkə" bilərik.

Buna görə də, iki hissənin cəmlərinin artıq bərabər olduğu üç boş olmayan hissəyə bölmənin olub olmadığını yoxlamalıyıq.

İkinci kəsik $j$ mövqesindən sonra olsun, burada $2 \leq j < n$ 2 \le j < n Sonra üç hissə: $1.. i, i + 1.. j, j + 1.. n$ { {1..i},\ {i+1..j},\ {j+1..n} } bəziləri üçün $i < j$ i < j.

İki hissənin bərabərliyi üçün üç halı nəzərdən keçirək.

1) Birinci və ikinci hissələr bərabərdir

Onda: $pref [i] = pref [j] - pref [i]$ \text{pref}[i] = \text{pref}[j] - \text{pref}[i] yəni, $2 \cdot pref [i] = pref [j]$ 2 \cdot \text{pref}[i] = \text{pref}[j] və ya $pref [i] = \frac{pref [ j ]}{2}$ \text{pref}[i] = \frac{\text{pref}[j]}{2}

Beləliklə, sabit $j$ üçün, prefiksin $pref [j] /2$ daha əvvəl görüldüyünü və $pref [j]$ -nin cüt olduğunu bilmək kifayətdir.

2) İkinci və üçüncü hissələr bərabərdir

Onda: $pref [j] - pref [i] = S - pref [j]$ \text{pref}[j] - \text{pref}[i] = S - \text{pref}[j] Bundan: $pref [i] = 2 \cdot pref [j] - S$ \text{pref}[i] = 2 \cdot \text{pref}[j] - S

Beləliklə, belə bir prefiksin daha əvvəl olub olmadığını yoxlamalıyıq.

3) Birinci və üçüncü hissələr bərabərdir

Onda: $pref [i] = S - pref [j]$ \text{pref}[i] = S - \text{pref}[j]

Yəni, belə bir prefiksin daha əvvəl olub olmadığını yoxlamaq da kifayətdir.

Niyə bu yoxlamalar kifayətdir

Hər $j$ üçün, $i < j$ i < j olan bütün mümkün $i$ -ləri artıq görüldüyü prefiks cəmləri vasitəsilə nəzərdən keçiririk.

seen dəsti bütün dəyərləri ehtiva edir: $pref [1], pref [2], \dots, pref [j - 1]$ \text{pref}[1], \text{pref}[2], \dots, \text{pref}[j-1]

Beləliklə, yuxarıdakı üç şərtdən hər biri $O (1)$ -də sualı cavablayır:

birinci və ikinci hissələrin bərabər olduğu bir $i$ -nin olub olmadığını;
ikinci və üçüncü hissələrin bərabər olduğu bir $i$ -nin olub olmadığını;
birinci və üçüncü hissələrin bərabər olduğu bir $i$ -nin olub olmadığını.

Əgər bu şərtlərdən ən az biri ödənilirsə, onda iki hissənin artıq bərabər cəmləri var və üçüncüsü bir əvəzləmə ilə düzəldilə bilər.

Beləliklə, cavab $1$ -dir.

Niyə iterasiya dəqiq $j = 2 \dots n - 1$ j = 2 \dots n-1 üçün gedir

Biz üç hissənin də boş olmalarını istəyirik:

birinci hissə ən azı bir elementi ehtiva etməlidir $\Rightarrow i \geq 1$ \Rightarrow i \ge 1;
ikinci hissə boş olmamalıdır $\Rightarrow i < j$ \Rightarrow i < j;
üçüncü hissə boş olmamalıdır $\Rightarrow j < n$ \Rightarrow j < n.

Buna görə də, xarici döngü $2 \leq j < n$ 2 \le j < n üzərində gedir və yoxlamadan əvvəl $pref [j - 1]$ \text{pref}[j-1] seenə əlavə olunur ki, $i$ indeksinin mütləq $j$ -dən kiçik olduğunu təmin etsin.

Son Alqoritm

Hər test halı üçün:

Prefiks cəmlərini hesablayın.
Dəyişiklik etmədən üç bərabər cəmi dərhal əldə etməyin mümkün olub olmadığını yoxlayın. Əgər belədirsə, cavab $0$ -dır.
Əks halda, ikinci sərhəd $j$ -ni iterasiya edin və prefiks dəsti istifadə edərək bir dəyişiklik üçün üç şərti yoxlayın. Əgər ən az biri ödənilirsə, cavab $1$ -dir.
Əks halda, cavab $2$ -dir.

Düzgünlük

Artıq sübut etmişik:

əgər dəyişiklik etmədən üç bərabər cəmlə bölmə varsa, kod $0$ -ı çıxaracaq;
əgər bu mümkün deyilsə, amma iki hissənin artıq bərabər cəmləri olan bir bölmə varsa, kod bunu tapacaq və $1$ -i çıxaracaq;
əgər nə $0$ , nə də $1$ uyğun deyilsə, onda həmişə $2$ dəyişikliklə cavabı əldə etmək mümkündür.

Beləliklə, alqoritm həmişə minimum dəyişiklik sayını tapır.

Asimptotiklər

Hər test halı üçün:

prefiks cəmlərini hesablamaq — $O (n)$ ;
$0$ halını yoxlamaq — $O (n)$ ;
unordered_set istifadə edərək $1$ halını yoxlamaq — ortalama $O (n)$ .

Beləliklə, ümumi mürəkkəblik: $O (n)$ orta hesabla, və bütün testlər üzrə: $O (\sum n)$ O\left(\sum n\right)

Yaddaş: $O (n)$

Həll Kodu

#include <bits/stdc++.h>
#include <random>
// fast_pragmas

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,tune=native")

// fast_pragmas ended

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

using namespace std;

#define ull unsigned long long
#define ll long long
#define ld long double
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define pb push_back
#define ln log
#define lg log10
#define log log2
#define here cout<<"HERE"<<endl

const ll clasik = 5e5 + 7;
const ll mln = 1e6 + 7;
const ll mod = 1e9 + 7;
//const ll mod = 998244353;
const ll block_size = 450;
const ll INF = 1e17;

ll df[clasik];

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

    vector<ll> a(n + 1), pref(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }

    ll S = pref[n];

    bool zero = false;

    if (S % 3 == 0) {
        ll x = S / 3;
        bool first_found = false;

        for (int i = 1; i < n; i++) {
            if (pref[i] == x) first_found = true;
            if (pref[i] == 2 * x && first_found) {
                zero = true;
                break;
            }
        }
    }

    if (zero) {
        cout << 0 << endl;
        return;
    }

    bool one = false;
    unordered_set<ll> seen;
    seen.reserve(n * 2);

    for (int j = 2; j < n; j++) {
        seen.insert(pref[j - 1]);

        if (pref[j] % 2 == 0 && seen.count(pref[j] / 2)) {
            one = true;
            break;
        }

        if (seen.count(2 * pref[j] - S)) {
            one = true;
            break;
        }

        if (seen.count(S - pref[j])) {
            one = true;
            break;
        }
    }

    if (one) cout << 1 << endl;
    else cout << 2 << endl;
}

signed main() {

    //freopen("deciding_points_input.txt" , "r" , stdin);
    //freopen("outputA.txt" , "w" , stdout);

    speed;
    int test;
    test = 1;
    //precalc();
    cin >> test;
    for (int tt = 1; tt <= test; tt++) {
        //cout << "Case #" << tt << ": ";
        solve();
    }

    return 0;
}

C++