8. Ako prežiť domáce úlohy vzorové riešenie

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

1
0
1
-1
2
-1

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

1
-1
0
-1
0

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

-1
1
0
1
1

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