Zadanie

Diktáty, testy, vyvolávanie, písomky, skúšky, projekty, prezentácie, prerátavanie, príklady, prosím, už stačilo.

Ale škole je to málo. Tu máš, milý Samo, zabalím ti školu na doma, aby si sa nenudil! To Samovi už len chýbalo - domáce úlohy. Je síce šikovný, a žiadna z nich mu nezaberá dlho, ale takú hromadu úloh naposledy videl keď objavil archív KSP.

No čo už, akademický úspech je nadovšetko, všetky domáce úlohy poslušne vypracuje. Niektoré ešte v škole 1, niektoré doma. Keď príde domov, chcel by si však najskôr pár hodín zahrať najnovšiu hitovú videohru: Kosperova Brána 3. To by mu však rodičia museli dovoliť. Jeho tatko po ňom vždy chce, aby mal hotový nejaký počet úloh. Jeho mamka zasa vždy vyžaduje, aby mal hotovú polovicu práce (pozor, nie polovicu úloh).

Spísal si teda počas obednej prestávky2 zoznam úloh v poradí, v ktorom ich plánuje vypracovať, a pripísal k nim aj koľko minút každá úloha trvá.

Počas telocviku zbiera od spolužiakov názory na dĺžku trvania jednotlivých úloh. Zároveň sa snaží podľa počasia vyhodnotiť, akú dobrú bude mať tatko náladu, a koľko hotových úloh od neho bude chcieť. Možno bude Samo musieť prepísať svoj zoznam…

Úloha

Samo má \(n\) domácich úloh. Keďže je šikovný, každá úloha mu trvá jednu, dve, alebo tri minúty.

Počas telocviku má \(q\) rozhovorov so spolužiakmi. Každý rozhovor spôsobí, že prehodnotí trvanie jednej úlohy. Vzápäťí Samo vyhodnotí, že jeho tatko od neho bude chcieť nejaký počet vypracovaných úloh \(x\).

Aby uspokojil oboch rodičov, bude musieť preusporiadať svoj pripravený zoznam úloh tak, aby prvých \(x\) úloh zaberalo presne polovicu času, čo zaberajú všetky úlohy. Preusporiadať ho môže len tak, že niekoľko krát vymení pozície dvoch (nie nutne susediacich) úloh v zozname.

Pomôžte Samovi, a po každom rozhovore a usúdení tatkovej nálady mu skontrolujte, koľko najmenej zmien by musel vo svojom zozname robiť.

Formát vstupu

V prvom riadku vstupu je číslo \(t\) - počet školských dní, v ktorých bude Samo musieť robiť domáce úlohy.

Nasleduje \(t\) popisov jednotlivých dní.

Popis ďna začína riadkom s číslami \(n\) a \(q\), udávajúce počet domácich úloh a počet rozhovorov.

V druhom riadku popisu je \(n\) čísel \(u_1, \cdots, u_n\) - dĺžky jednotlivých úloh, v poradí v akom ich má Samo v zozname.

Potom nasleduje \(q\) riadkov. V \(i\)-tom z nich sú tri čísla \(a_i\), \(b_i\) a \(x_i\), znázorňujúce že Samo prehodnotil trvanie \(a_i\) tej úlohy na \(b_i\) minút, a odhaduje že tatko po ňom bude chcieť aby mal hotových \(x_i\) úloh. Dĺžky úloh sa naozaj zmenia (Samo si ich prepíše v zozname), a ostávajú zmenené aj do budúcna (pokiaľ sa dĺžka opätovne nezmení nejakým neskorším rozhovorom).

Platí \(1 \leq t \leq 100\), \(1 \leq n, q\), \(1 \leq u_i, b_i \leq 3\) a \(1 \leq a_i, x_i \leq n\).

V jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1 2 3 4
\(n, q \leq\) \(100\) \(2 \cdot 10^5\) \(2 \cdot 10^5\) \(10^6\)
súčet \(n,q \leq\) \(2\,000\) \(4 \cdot 10^5\) \(4 \cdot 10^5\) \(10^6\)

V druhej sade navyše platí, že \(x_i = \frac{n}{2}\) (zaokrúhlené nahor).

V tretej sade navyše platí, že dĺžky úloh sa nemenia (\(b_i\) bude rovné dĺžke úlohy \(a_i\)).

Formát výstupu

Pre každý deň, po \(i\)-tom rozhovore vypíšte jedno číslo - najmenší počet zmien, ktoré by Samo musel urobiť v svojom zozname, aby súčet dĺžok prvých \(x_i\) úloh bol rovný súčtu dĺžok všetkých zvyšných. Ak to Samo nevie dosiahnuť, vypíšte namiesto toho \(-1\).

Pripomíname, že zmena je vymenenie poradia dvoch (nie nutne susediacich) úloh v zozname, a Samo tieto zmeny počas telocviku reálne nevykonáva.

Príklady

Input:

2
8 5
1 1 2 3 1 2 3 1
4 1 4
7 1 4
7 1 3
5 2 5
6 1 5
1 1
2
1 1 1

Output:

1
0
1
-1
2
-1

Zoznam dĺžok úloh vyzeral po jednotlivých rozhovoroch nasledovne
1 1 2 3 1 2 3 1 (začiatok)
1 1 2 1 1 2 3 1
1 1 2 1 1 2 1 1
1 1 2 1 1 2 1 1
1 1 2 1 2 2 1 1
1 1 2 1 2 1 1 1
Po prvom rozhovore trvali úlohy dokopy 12 minút. Aby prvé štyri trvali toľko koľko zvyšné, mohol by Samo jednou zmenou vymeniť štvrtú a šiestu. Po druhom rozhovore trvajú prvé štyri úlohy toľko, čo posledné štyri, nemusel by teda robiť žiadne zmeny. Po piatom rozhovore môže vymeniť napríklad tretiu úlohu so šiestou a piatu so siedmou. Trvanie prvých piatich a zvyšných troch je potom rovnaké.

Input:

2
10 3
1 2 3 2 2 1 2 3 2 2
3 1 5
8 2 5
1 2 5
3 2
1 1 2
1 2 2
3 3 2

Output:

1
-1
0
-1
0

Príklad vstupu druhej sady

Input:

2
10 3
1 2 3 2 2 1 2 3 2 2
3 3 3
8 3 6
1 1 5
3 2
1 2 1
1 1 1
2 2 2

Output:

-1
1
0
1
1

Príklad vstupu tretej sady

Riešenia na našu úlohu sa líšia v tom, koľko práce potrebujú spraviť na aktualizáciu trvania domácej úlohy (a všetkej informácie, ktorú potrebujú mať vypočítanú, aby rýchlo odpovedali na otázku), a za akých podmienok to zvládnu.

V prvej sade si vieme dovoliť pre každú otázku zrátať informácie pomaly.

V druhej aj tretej sade si potrebujeme informácie zrátať rýchlo, no máme to uľahčené: v druhej sade bude otázka vždy rovnaká, a v tretej sade budú otázky rôzne, nebudeme však musieť aktualizovať trvania úloh.

Na plný počet potom už musíme vedieť aktualizovať dĺžky úloh rýchlo, a zároveň vedieť rýchlo odpovedať na všetky možné otázky.

Vymieňanie úloh

Pri zodpovedaní konkrétnej otázky \(x\) nás nezaujíma konkrétne poradie úloh v zozname, keďže Samo vie vymieňať úlohy bezohľadu na ich umiestnenie. Relevantné je len to, koľko úloh každej dĺžky 1 až 3 je vrámci prvých \(x\), a koľko vrámci zvyšku.

Ozbrojení týmito šiestimi číslami potom vieme zrátať najmenší počet výmen (alebo že to nie je možné) pažravo: najprv chceme povymieňať úlohy dĺžky 3 za úlohy dĺžky 1, keďže tieto výmeny zmenia rozdiel súčtov oboch častí zoznamu o 4, a ak to nestačí, povymieňame potrebný počet úloh dĺžky 3 za 2, a 2 za 1.

Ako sa môžeme uistiť, že takáto pažravá stratégia funguje? Zvolíme prístup, ktorý sa často hodí pri riešení úloh: dokážeme, že ak existuje nejaké riešenie, tak ho vieme transformovať na naše pažravé riešenie.

Pozrime sa teda na nejaké riešenie (BÚNV je súčet úloh vľavo väčší ako vpravo). Ak sme v ňom nejakú úlohu vymenili viac ako raz, teda vymeníme úlohy \(a, b\) a niekedy neskôr \(c, a\), tak namiesto toho sme mohli rovno vymeniť \(c, b\). Dôsledok je aj to, že nikdy nevymeníme najprv 3 za 2 a potom 2 za 1. Ak niekedy vymeníme 1 za 2 (kratšiu za dlhšiu), musíme to nejakou výmenou odčiniť; ak neskôr vymeníme 2 za 1 alebo 3 za 1, platí predošlá úvaha, inak vieme vymienať len 3 za 2, čo sme však mohli aj predtým ( nezískali sme ani 3ku vľavo ani 2ku vpravo navyše), a teda vieme túto výmenu 1,2 a jednu 3,2 vynechať. Podobne vieme ukázať, že nemusíme nikdy vymeniť 2 za 3.

Z týchto dvoch pozorovaní vieme, že ľubovoľné riešenie vieme prepísať na také, v ktorom vymieňame len 3 za 1, a buď 3 za 2 alebo 2 za 1 (ale nie oboje). No a ak máme dve výmeny 3-za-2 (2-za-1), ak máme napravo 1ku nazvyš (naľavo 3ku nazvyš), môžeme namiesto toho vymeniť 3-za-1. Ak nemáme napravo 1ku nazvyš (naľavo 3ku nazvyš), tak naše riešenie už spravilo všetky výmeny 3-za-1, teda už bolo pažravé.

Takto sme ukázali, že ľubovoľné riešenie ktoré zarovná trvanie úloh v oboch častiach zoznamu vieme prepísať na pažravé, teda pažravý prístup nikdy nespôsobí, že riešenie nenájdeme. Zároveň sme to spravili len tým, že sme niektoré výmeny pomazali, a tak vidíme že pažravé riešenie spraví menej výmen, ako iné s ktorým začneme. Hurá!

Ako naše pažravé riešenie nájdeme? Pri každom druhu výmen (3 za 1, 3 za 2, 2 za 1) si zrátame, koľko výmen môžeme urobiť (minimum výskytov v prvej a druhej časti zoznamu), a koľko ich chceme urobiť (rozdiel trvania oboch častí zoznamu, deleno koľko ho výmena zmení). Následne túto výmenu spravíme buď koľko krát môžeme, alebo koľko krát chceme, podľa toho ktoré je menšie.

Ak po vykonaní výmen všetkých troch typov obe časti nemajú rovnaké trvanie (buď lebo nevychádza parita, alebo pretože nevieme nasúkať dosť dlhých úloh do kratšej časti), odpovieme -1, inak povieme koľko výmen sme vykonali.

Odporúčame si toto zrátanie naprogramovať ako osobitnú funkciu, ktorú potom zavoláte s pripravenými počtami úloh rôznej dĺžky v oboch častiach zoznamu. Potom môžete vylepšovať to, ako tieto počty počas prepisovania dĺžok úloh získavate, pre rôzne vstupné sady. Dbajte na to, aby vaša funkcia netrvala dlhšie, ak sú počty úloh vyššie - mala by všetko zrátať v \(O(1)\).

// A[i] je pocet uloh dlzky i vlavo, B[i] vpravo
int zrataj_vymeny(vector<int> A, vector<int> B) {
    int rozdiel = A[1] - B[1] + 2 * (A[2] - B[2]) + 3 * (A[3] - B[3]);
    // nech presuvame z vacsieho A do mensieho B
    if (rozdiel < 0) {
        rozdiel = -rozdiel;
        swap(A, B);
    }
    // lubovolna vymena zmeni rozdiel o parnu hodnotu
    // ak je rozdiel neparny, neda sa
    if (rozdiel % 2) {
        return -1;
    }
    rozdiel /= 2;

    // zratame kolko 3-za-1 vymen chceme, vieme
    // spravime ich minimum z toho
    int chcem_3_za_1 = rozdiel / 2;
    int viem_3_za_1 = min(A[3], B[1]);
    int vymenim_3_za_1 = min(chcem_3_za_1, viem_3_za_1);
    rozdiel -= 2 * vymenim_3_za_1;
    A[3] -= vymenim_3_za_1;
    B[1] -= vymenim_3_za_1;

    // to iste pre 3-za-2 a 2-za-1
    // mozeme to zratat sucasne, kedze sme dokazali
    // ze nebudeme nikdy robit obe
    int viem_3_za_2 = min(A[3], B[2]);
    int viem_2_za_1 = min(A[2], B[1]);
    int viem_jednotkovych_vymen = max(viem_3_za_2, viem_2_za_1);
    int chcem_jednotkovych_vymen = rozdiel; // uplne nepotrebne, ale pre pochopenie
    int vymenim_jednotkove = min(chcem_jednotkovych_vymen, viem_jednotkovych_vymen);
    rozdiel -= vymenim_jednotkove;

    // ak ostal nejaky rozdiel, tak sa to neda
    if (rozdiel != 0)
        return -1;
    // inak vratime kolko vymen sme spravili
    return vymenim_3_za_1 + vymenim_jednotkove;
}

Hoďme na to for cyklus

Najjednoduchšie riešenie: budeme si udržovať pole s dĺžkami úloh, a aby sme zistili koľko akých úloh je v prvých \(x\) a vo zvyšku, jednoducho ho prejdeme a zrátame si to.

Udržujeme si teda pole veľkosti \(n\). Každú zmenu dĺžku úlohy vieme priamo vykonať v našom poli v \(O(1)\). Pre každú otázku musíme prejsť celé naše pole aby sme zrátali počty rôznych úloh v oboch častiach nášho zoznamu, čo nám trvá \(O(n)\).

Keďže otázok aj aktualizácií je \(q\), toto nám zaberie \(O(nq)\) času. Naše pole úloh nám zaberie \(O(n)\) pamäte.

#include <bits/stdc++.h>
using namespace std;

int zrataj_vymeny(vector<int> A, vector<int> B) {
    // ... //
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        vector<int> v(n);
        for (int i = 0; i < n; i++)
            cin >> v[i];
        for (int i = 0; i < q; i++) {
            int a, b, x;
            cin >> a >> b >> x;
            a--;
            v[a] = b;
            vector<int> A = {0, 0, 0, 0};
            vector<int> B = {0, 0, 0, 0};
            // prejdeme vsetky ulohy a zratame kolko akych je
            // vlavo a vpravo od x
            for (int j = 0; j < x; j++)
                A[v[j]]++;
            for (int j = x; j < n; j++)
                B[v[j]]++;

            cout << zrataj_vymeny(A, B) << "\n";
        }
    }
}

Keď si úlohy vieme dopredu rozdeliť

V prvých dvoch sadách máme síce príliš veľa úloh a otázok, aby sme si mohli dovoliť prepočítavať niečo na všetkých úlohách, máme však nejaké záruky navyše.

V druhej sade sa vždy pýtame otázku \(x = \frac{n}{2}\). Dve časti zoznamu, ktoré budeme musieť vyvážiť, budú teda vždy rovnaké, a potrebujeme si len udržiavať počet úloh dĺžky 1, 2 a 3 v nich.

Nech \(A_1, A_2, A_3\) je počet úloh dĺžky 1 až 3 v prvej polovici zoznamu, a \(B_1, B_2, B_3\) v druhej polovici. Na začiatku si tieto hodnoty vieme prejdením celého poľa zrátať - pripočítavame do \(A\) pre prvú polovicu úloh, a do \(B\) pre druhú. Následne, keď sa zmení dĺžka úlohy \(a_i\) na \(b_i\), pozrieme sa do poľa úloh, akú má úloha \(a_i\) momentálne dĺžku, odpočítame ju z \(A\) alebo \(B\) podľa toho do ktorej polovice patrí \(a_i\), a následne ju zmeníme a pripočítame späť. Potom zavoláme našu pripravenú funkciu ktorá zistí či a na koľko výmen vieme \(A\) a \(B\) vyrovnať, a zmlsneme 2 body za program navyše.

Pamäťová zložitosť zostáva \(O(n)\) keďže si pamätáme pole úloh, a konštatne veľa čísel navyše. Časová zložitosť je \(O(n+q)\), keďže pre každú zmenu spravíme konštatne veľa operácií (odpočítanie - zmenenie - pripočítanie) a zavoláme našu pripravenú funkciu.

#include <bits/stdc++.h>
using namespace std;

int zrataj_vymeny(vector<int> A, vector<int> B) {
    // ... //
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        vector<int> v(n);
        vector<int> A = {0, 0, 0, 0};
        vector<int> B = {0, 0, 0, 0};

        // predratame si, kolko akych uloh je
        // v prvej a druhej polovici zoznamu
        for (int i = 0; i < n; i++) {
            cin >> v[i];
            if (2 * i < n)
                A[v[i]]++;
            else
                B[v[i]]++;
        }

        for (int i = 0; i < q; i++) {
            int a, b, x;
            cin >> a >> b >> x;
            a--;
            // preratame si hodnotu v tej polovici
            // do ktorej uloha patri
            if (a < x) {
                A[v[a]]--;
                A[b]++;
            } else {
                B[v[a]]--;
                B[b]++;
            }
            // prepiseme si ju
            v[a] = b;

            cout << zrataj_vymeny(A, B) << "\n";
        }
    }
}

Keď sa úlohy nemenia

V tretej sade máme inú garanciu: dĺžky úloh sa nemenia. Musíme však zodpovedať rôzne otázky.

Môžeme zvoliť jeden z dvoch prístupov - predpočítať si všetky otázky, alebo pripraviť sa odpovedať na otázky rýchlo.

Prvé riešenie bude veľmi podobné riešeniu druhej sady - majme polia \(A\) a \(B\), v ktorých si budeme udržiavať počty úloh všetkých dĺžok, v \(A\) po úlohu \(x\), a v \(B\) napravo. Na začiatku sú všetky úlohy v \(B\) (akoby \(x = 0\)). Teraz budeme pomyselné \(x\) posúvať doprava: postupne prejdeme úlohy do prvej po \(n\)-tú, odpočítame ju z \(B\), pripočítame do \(A\), našou funkciou zrátame výsledok, a zapíšeme si ho do poľa odpovedí. Nakonci máme odpovede pre všetky \(x\) od \(1\) po \(n\), a vypisujeme ich ako si ich vstup pýta.

Druhé riešenie je použiť prefixové súčty (viď kuchárka ) - zrátame si ich osobitne pre všetky tri dĺžky úloh. Potom pomocou nich vieme v \(O(1)\) zistiť koľko ktorých úloh je do \(x\) a po \(x\), a opäť len funkciou zrátať výsledok.

Obe riešenia si nazačiatku niečo pre všetky úlohy predpočítajú, a pre každú úlohu spravia \(O(1)\) práce. Následne vedia odpovedať na otázky v \(O(1)\). Majú teda pamäťovú zložitosť \(O(n)\) a časovú \(O(n+q)\)

#include <bits/stdc++.h>
using namespace std;

int zrataj_vymeny(vector<int> A, vector<int> B) {
    // ... //
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        vector<int> v(n);
        vector<vector<int>> prefixy = vector<vector<int>>(4, vector<int>(n + 1, 0));
        // predratame si prefixove sucty pre vsetky dlzky uloh
        for (int i = 0; i < n; i++) {
            cin >> v[i];
            for (int j = 0; j < 4; j++)
                prefixy[j][i + 1] = prefixy[j][i];
            prefixy[0][i + 1] += v[i];
            prefixy[v[i]][i + 1] += 1;
        }

        for (int i = 0; i < q; i++) {
            int a, b, x;
            cin >> a >> b >> x;
            // nemusime nic preratavat, kedze mame zaruku ze v[a-1] == b
            vector<int> A(4, 0);
            vector<int> B(4, 0);
            // zratame si z nich, kolko ktorych uloh je pred a po x
            for (int j = 1; j <= 3; j++) {
                A[j] = prefixy[j][x];
                B[j] = prefixy[j][n] - A[j];
            }

            cout << zrataj_vymeny(A, B) << "\n";
        }
    }
}

Keď to treba zvládnuť naraz…

Posledné spomenuté riešenie má do plného počtu bodov len jediný háčik - ak by sa zmenila dĺžka nejakej úlohy, aby bol náś prefixový súčet správny, museli by sme všetko napravo od nej prepočítať, a to trvá dlho.

Kiežby existovala dátová štruktúra, ktorá vie na nejakom intervale čísla posčítavať, a aj ich postupne po jednom meniť…

A takých dátových štruktúr existuje dokonca viacero!

Jeden dobrý kandidát je intervalový strom. Môžeme si v jeho vrcholoch udržiavať počty všetkých dĺžok úloh, alebo si postaviť viacero jednoduchých stromov, každý na jedno trvanie úloh. Postavíme ich zo vstupu, pri prepisovaní úloh voláme update, a pri odpovedaní na otázky zrátame úlohy do \(x\) a od \(x\) query operáciami, a odpoveď dorátame našou funkciou.

Pamäťová zložitosť intervalového stromu je \(O(n)\). Jeho vytvorenie nás trvá \(O(n)\), každá zmena nám zaberie \(O(\log n)\) na spracovanie, a zrátať úlohy na dvoch intervaloch tiež \(O(\log n)\). Dokopy je teda časová zložitosť \(O(n + q \log n)\).

Pre záujemcov naučiť sa dačo nové, ďalším dobrým kandidátom na dátovú štruktúru je Binary Indexed Tree, tzv. Fínsky strom. Žiaľ, chýba k nemu článok v kuchárke, môžete si o ňom však prečítať na wikipédií, a pozrieť si naše vzorové riešenie, ktoré ho využíva.

#include <bits/stdc++.h>
using namespace std;

int zrataj_vymeny(vector<int> A, vector<int> B) {
    // ... //
}

// Finsky strom
struct FT {
    vector<int> s;
    FT(int n) : s(n) {}
    void update(int pos, int dif) {
        for (; pos < s.size(); pos |= pos + 1)
            s[pos] += dif;
    }
    int query(int pos) {
        int res = 0;
        for (; pos > 0; pos &= pos - 1)
            res += s[pos - 1];
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        vector<int> v(n);
        // finsky strom pre vsetky dlzky uloh
        FT fts[] = {FT(0), FT(n), FT(n), FT(n)};
        for (int i = 0; i < n; i++) {
            cin >> v[i];
            fts[v[i]].update(i, 1);
        }

        for (int i = 0; i < q; i++) {
            int a, b, x;
            cin >> a >> b >> x;

            a--;
            fts[v[a]].update(a, -1);
            v[a] = b;
            fts[b].update(a, 1);

            vector<int> A(4, 0), B(4, 0);

            for (int j = 1; j <= 3; j++) {
                A[j] = fts[j].query(x);
                B[j] = fts[j].query(n) - A[j];
            }

            cout << zrataj_vymeny(A, B) << "\n";
        }
    }
}

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.