Трійка#12369

Трійка (Розбір)

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

Ідея

На другому етапі ми можемо лише стискати підвідрізки в їхню суму. Це означає, що фінальний масив $[x, x, x]$ [x,x,x] завжди відповідає деякому розбиттю початкового масиву на три непорожні суцільні частини з однаковими сумами.

Тобто після всіх замін на першому етапі масив має стати таким, щоб існували індекси $1 \leq i < j < n$ 1 \le i < j < n і виконувалось:

$\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

Отже задача насправді така: змінити мінімум елементів, щоб масив можна було розбити на три непорожні підвідрізки з однаковими сумами.

Чому відповідь не більша за 2

Завжди можна змінити не більше двох елементів.

Справді, візьмемо будь-яке розбиття на три непорожні частини, наприклад: $a_{1}, a_{2}, a_{3}, \dots, a_{n}$ { {a_1}, {a_2}, {a_3,\dots,a_n} } Тоді можна змінити один елемент у першій частині і один елемент у другій частині так, щоб суми всіх трьох частин стали однаковими.

Тому відповідь завжди одна з: $[0, 1, 2]$ [ 0,\ 1,\ 2 ]

Отже достатньо навчитися перевіряти:

чи відповідь дорівнює $0$ ;
чи відповідь дорівнює $1$ ;
інакше відповідь $2$ .

Випадок 0 змін

Нехай $S = \sum_{i = 1}^{n} a_{i}$ S = \sum_{i=1}^{n} a_i

Якщо ми не змінюємо жодного елемента, то потрібно, щоб масив уже можна було розбити на три частини з однаковою сумою. Отже обов’язково: $S \equiv 0 (mod 3)$ S \equiv 0 \pmod 3 і кожна частина повинна мати суму $x = S /3$ x = S/3

Через префіксні суми це перевіряється дуже просто:

шукаємо префікс із сумою $x$ ;
далі правіше шукаємо префікс із сумою $2 x$ .

Якщо обидва існують так, що третя частина непорожня, то відповідь $0$ .

Коли достатньо однієї зміни

Нехай ми хочемо змінити рівно один елемент. Тоді після цієї зміни масив має розбитись на три частини з однаковими сумами.

Ключове спостереження: якщо змінюється лише один елемент, то він лежить рівно в одній з трьох частин. Отже дві інші частини вже спочатку мають однакові суми. Саме третю частину ми можемо "дотягнути" однією зміною до цього значення.

Тому треба перевірити, чи існує розбиття на три непорожні частини, де суми двох частин уже однакові.

Нехай другий розріз стоїть після позиції $j$ , де $2 \leq j < n$ 2 \le j < n Тоді три частини такі: $1.. i, i + 1.. j, j + 1.. n$ { {1..i},\ {i+1..j},\ {j+1..n} } для деякого $i < j$ i < j.

Розглянемо три варіанти рівності двох частин.

1) Рівні перша і друга частини

Тоді: $pref [i] = pref [j] - pref [i]$ \text{pref}[i] = \text{pref}[j] - \text{pref}[i] тобто $2 \cdot pref [i] = pref [j]$ 2 \cdot \text{pref}[i] = \text{pref}[j] або $pref [i] = \frac{pref [ j ]}{2}$ \text{pref}[i] = \frac{\text{pref}[j]}{2}

Значить для фіксованого $j$ достатньо знати, чи зустрічався раніше префікс $pref [j] /2$ і чи $pref [j]$ парне.

2) Рівні друга і третя частини

Тоді: $pref [j] - pref [i] = S - pref [j]$ \text{pref}[j] - \text{pref}[i] = S - \text{pref}[j] Звідси: $pref [i] = 2 \cdot pref [j] - S$ \text{pref}[i] = 2 \cdot \text{pref}[j] - S

Отже треба перевірити, чи існував раніше такий префікс.

3) Рівні перша і третя частини

Тоді: $pref [i] = S - pref [j]$ \text{pref}[i] = S - \text{pref}[j]

Тобто теж достатньо перевірити, чи був такий префікс раніше.

Чому цих перевірок достатньо

Для кожного $j$ ми розглядаємо всі можливі $i < j$ i < j неявно через множину вже побачених префіксних сум.

Множина seen містить усі значення: $pref [1], pref [2], \dots, pref [j - 1]$ \text{pref}[1], \text{pref}[2], \dots, \text{pref}[j-1]

Тому кожна з трьох умов вище за $O (1)$ відповідає на питання:

чи існує такий $i$ , що перша і друга частини рівні;
чи існує такий $i$ , що друга і третя частини рівні;
чи існує такий $i$ , що перша і третя частини рівні.

Якщо хоч одна з цих умов виконується, то дві частини вже мають однакову суму, а третю можна виправити однією заміною.

Отже відповідь дорівнює $1$ .

Чому ітерація йде саме по $j = 2 \dots n - 1$ j = 2 \dots n-1

Ми хочемо, щоб усі три частини були непорожні:

перша частина має містити хоча б один елемент $\Rightarrow i \geq 1$ \Rightarrow i \ge 1;
друга частина має бути непорожня $\Rightarrow i < j$ \Rightarrow i < j;
третя частина має бути непорожня $\Rightarrow j < n$ \Rightarrow j < n.

Тому зовнішній цикл іде по $2 \leq j < n$ 2 \le j < n а в seen перед перевіркою додається $pref [j - 1]$ \text{pref}[j-1], щоб індекс $i$ точно був меншим за $j$ .

Підсумковий алгоритм

Для кожного тесту:

Рахуємо префіксні суми.
Перевіряємо, чи можна одразу отримати три рівні суми без змін. Якщо так, відповідь $0$ .
Інакше перебираємо другу межу $j$ і через множину префіксів перевіряємо три умови для однієї зміни. Якщо хоч одна виконується, відповідь $1$ .
Інакше відповідь $2$ .

Коректність

Ми вже довели:

якщо існує розбиття на три рівні суми без змін, код виведе $0$ ;
якщо це неможливо, але існує розбиття, де дві частини вже мають однакову суму, код знайде його і виведе $1$ ;
якщо не підходить ні $0$ , ні $1$ , то завжди можна досягти відповіді за $2$ зміни.

Отже алгоритм завжди знаходить мінімальну кількість змін.

Асимптотика

Для кожного тестового випадку:

обчислення префіксних сум — $O (n)$ ;
перевірка випадку $0$ — $O (n)$ ;
перевірка випадку $1$ через unordered_set — $O (n)$ в середньому.

Отже сумарна складність: $O (n)$ на тест у середньому, а по всіх тестах: $O (\sum n)$ O\left(\sum n\right)

Пам’ять: $O (n)$

Код рішення

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