4. Zabudnuté algoritmy vzorové riešenie

3
1
14 1
0
2
13 3
14 1
2
13 3
14 1

1
3

3
2
47 5
42 3
3
42 13
13 4
7 6
1
47 2
5
47 1
47 3
42 12
13 5
47 12

0
1
1
1
2

Jednoduché riešenie

Skúsme najprv vymyslieť priamočiare riešenie. Budeme si pre každú úlohu pamätať, ktoré algoritmy na ňu potrebujeme vedieť a na akej úrovni. Vždy, keď sa Hodobox niečo naučí, prejdeme všetky úlohy a spočítame tie, pre ktoré už vie všetky algoritmy dosť dobre.

Pre jednoduchosť si pri každom algoritme pre každú úlohu okrem toho, na akú úroveň ho potrebujeme vedieť, zapamätáme aj to, ako dobre ho vieme – znalosť algoritmu. Na začiatku je to nula pre každý algoritmus každej úlohy. Postupne, ako sa bude Hodobox algoritmy učiť, budeme tieto čísla zvyšovať.

Po načítaní zoznamov algoritmov pre jednotlivé úlohy začneme postupne spracovávať Hodoboxove akcie. Pri každej akcii prejdeme každú z \(n\) úloh a spočítame, koľko z nich vie vyriešiť. To vieme pre jednu úlohu spočítať jednoducho: Postupne sa pozrieme na všetky potrebné algoritmy, a overíme, či ich už Hodobox vie na dostatočne dobrej úrovni. Ak nájdeme algoritmus, ktorý má potrebnú úroveň ostro vyššiu ako znalosť, tak sa ho Hodobox ešte musí učiť.

Popri tomto prechádzaní vo všetkých úlohách aj zvyšujeme znalosť algoritmu, ktorý sa Hodobox v tejto akcii naučil.

 Akú má toto riešenie časovú a pamäťovú zložitosť?

Časová zložitosť pre načítanie vstupu závisí od jednotlivých počtov algoritmov. Pre úlohu \(i\) načítanie trvá \(O(1+a_i)\). Jednotka je tu pre načítanie čísla \(a_i\). To je podstatné hlavne ak \(a_i = 0\). Na celkové načítanie vstupu potrebujeme načítať všetky úlohy, a tak čas potrebný na načítanie celého vstupu bude súčet časov pre jednotlivé úlohy: \(\sum_{i=1}^{n} (1+a_i) = \sum_{i=1}^{n} 1 + \sum_{i=1}^{n} a_i = n + \sum_{i=1}^{n} a_i\). Ak si označíme \(\sum a_i = A\), tak načítanie vstupu má časovú zložitosť \(O(n+A)\).

Koľko trvá spracovanie jednej Hodoboxovej akcie? Prechádzame každú úlohu, a pre ňu každý algoritmus, čo je znova súčet počtov algoritmov pre všetky úlohy. Teda aj spracovanie jednej akcie trvá \(O(n+A)\). Spracovanie všetkých akcií bude trvať \(O(p(n+A))\).

Celkovo je časová zložitosť \(O(n + A + p(n+A)) = O(p(n+A))\).

Pamäťová zložitosť je \(O(n+A)\), keďže si musíme zapamätať všetky úlohy a algoritmy, ktoré sú pre ne potrebné.

#include<cstdio>
#include<vector>

using namespace std;

struct algoritmus {
    int cislo;
    // Na koľko ho Hodobox musí vedieť.
    int potrebna_uroven;
    // Na koľko ho Hodobox vie.
    int znalost;
};

int main() {
    int n;
    scanf(" %d", &n);
    // Tu si budem pre každú úlohu pamätať algoritmy, ktoré na ňu potrebujem vedieť.
    vector< vector< algoritmus > > ulohy;

    for (int i = 0; i<n; ++i) {
        int a;
        scanf(" %d", &a);
        vector< algoritmus > algoritmy(a);
        for (int j = 0; j<a; ++j) {
            int x,y;
            scanf(" %d %d", &x, &y);
            algoritmy[j].cislo = x;
            algoritmy[j].potrebna_uroven = y;
            // Na začiatku vie Hodobox všetky algoritmy na nula.
            algoritmy[j].znalost = 0;
        }
        ulohy.push_back(algoritmy);
    }

    int p;
    scanf(" %d", &p);
    for (int i = 0; i<p; ++i) {
        int c, u;
        scanf(" %d %d", &c, &u);

        // Pre každú úlohu sa pozrieme, či už vie všetky potrebné algoritmy dostatočne dobre.
        int pocet_uloh = 0;
        for (int j = 0; j<n; ++j) {
            // Predpokladáme že ju vie vyriešiť.
            bool viem = true;

            // Prejdeme cez všetky algoritmy potrebné na túto úlohu.
            for (unsigned k = 0;  k < ulohy[j].size(); k++) {

                // Ak je toto algortimus, ktorý sa práve Hodobox naučil o
                // 'u' lepšie, tak si pripočítame, že ho už vie o 'u' lepšie.
                if (ulohy[j][k].cislo == c) {
                    ulohy[j][k].znalost += u;
                }

                // Zistíme, či už má Hodobox dostatočnú znalosť algoritmu 'k' na úlohu 'j'.
                if (ulohy[j][k].znalost < ulohy[j][k].potrebna_uroven) {
                    viem = false;
                }
            }
            // Ak vie všetky algoritmy dostatočne, tak zvýšime počet úloh.
            if (viem) pocet_uloh++;
        }
        printf("%d\n", pocet_uloh);
    }
    return 0;
}

Skoro vzorové riešenie

Predošlé riešenie funguje, ale pozrime sa, či by vyriešilo úlohu aj pre najväčšie vstupy. Tam môžu premenné \(p\), \(n\) aj \(A\) nadobúdať hodnoty až po \(10^6\). Keďže časová zložitosť je \(O(p(n+A))\), bolo by to rádovo až \(10^6\cdot (10^6 + 10^6)) = 2\cdot10^{12}\) operácií, no bežný počítač zvláda za sekundu približne “len” \(10^9\) operácií. Pokúsme sa teda navrhnúť efektívnejší algoritmus.

Pozrime sa na to, čo sme počítali v predošlom riešení zbytočne veľakrát.

Prvou takou vecou bolo, že sme po každej akcii prešli všetky úlohy, a spočítali tie, ktoré vie Hodobox vyriešiť. Po jednej akcii sa ale výsledok (počet riešiteľných úloh) nezmení o veľa. Mohli by sme mať teda jedno počítadlo: počet riešiteľných úloh. V každej akcii by sme toto počítadlo len zvýšili o úlohy, ktoré sa stali riešiteľnými naučením tohoto algoritmu a potom by sme hodnotu tohto počítadla vypísali ako výsledok. Zavedenie počítadla nám samo osebe ešte nezlepší zložitosť, ale je to prvým krokom k lepšiemu riešeniu.

Druhá vec, ktorú sme robili pri každej akcii, bola, že sme prešli všetky algoritmy každej úlohy. V jednej akcii sa ale Hodobox naučil len jeden algoritmus, ktorý bol potrebný len pre pár úloh. Čo ak by sme si pre každý algoritmus pamätali všetky úlohy, ktoré ho potrebujú? Potom by sme pri spracovávaní Hodoboxovej akcie prešli naozaj iba tie úlohy, pri ktorých sa niečo zmenilo.

Zoznamy úloh pre každý algoritmus si budeme pamätať v dvojrozmernom poli dvojíc¹. \(i\)-ty prvok tohto poľa bude jednorozmerné pole takýchto dvojíc: (úroveň algoritmu \(i\) (potrebná na vyriešenie úlohy), číslo úlohy).

Keďže každý prvok nášho poľa (zoznam) patrí jednému algoritmu a my vieme, že najväčšie číslo algoritmu je \(10^6\), tak veľkosť poľa si môžme zvoliť \(10^6+1\).²

V inom riešení by sme si počas načítavania vstupu mohli pole naťahovať. V premennej \(max\_alg\) by sme si udržiavali najväčšie nájdené číslo algoritmu a vždy, keď by sme našli algoritmus s číslom \(x\) väčším než \(max\_alg\), tak by sme naše pole rozšírili na dĺžku \(x+1\).

Pre každý algoritmus \(i\) máme teda zoznam úloh, pre ktoré potrebujeme algoritmus \(i\) vedieť lepšie. Mohli by sme teda povedať, že je to zoznam úloh, ktoré sú blokované algoritmom \(i\). Každá úloha je na začiatku blokovaná všetkými svojimi algoritmami. Keď si Hodobox zlepší znalosť algoritmu \(i\), mohli by sme tento zoznam prejsť a odstrániť tie úlohy, pre ktoré už vie Hodobox algortimus dostatočne dobre.³

Na vstupe vždy dostaneme len číslo \(u\), o ktoré sa Hodoboxova znalosť algoritmu \(i\) zvýšila. Na to, aby sme vedeli povedať, aká je nová úroveň znalosti algoritmu (v predošlej poznámke sme ju označovali \(y\)) si pre každý algoritmus chceme pamätať jeho aktuálnu úroveň v poli. Na začiatku vie Hodobox každý algoritmus na nula a pri každej akcii upravíme znalosť jedného algoritmu (y += u). Toto pole pre úrovne môžeme spraviť veľkosti \(10^6+1\), alebo veľkosti \(max\_alg+1\).

Poslednou otázkou zostáva: Kedy vie Hodobox vyriešiť novú úlohu? Vtedy, ak už úloha nie je v žiadnom zozname – vtedy, keď nie je blokovaná žiadnym algoritmom. Pre každú úlohu by sme teda mohli mať navyše v jednej premennej uložené, koľkými algoritmami je blokovaná. Na začiatku tu bude počet všetkých algoritmov, ktoré sú pre ňu potrebné. Pri akciách budeme toto číslo znižovať, keď budeme danú úlohu vyhadzovať zo zoznamov. Keď počet blokácií dosiahne hodnotu 0, znamená to, že sa úloha stala riešiteľnou a tak zvýšime naše globálne počítadlo riešiteľných úloh.

Poďme si teda riešenie zhrnúť. Máme jedno globálne počítadlo riešiteľných úloh a pre každý algoritmus máme zoznam úloh s úrovňami znalosti potrebnými na ich vyriešenie. Navyše si ešte v samostatných poliach pamätáme aktuálne úrovne znalostí algoritmov a počet blokácií každej úlohy.

Pozrime sa na to, čo sa stane v jednej akcii. Nech si Hodobox v tejto akcii zlepšil úroveň algoritmu \(i\) o \(u\).

• Pozrieme sa do poľa znalostí algoritmov a zvýšime aktuálnu znalosť algoritmu \(i\) o \(u\). Nech je táto nová hodnota \(y\).

• Ďalej sa chceme postupne pozrieť na všetky úlohy v zozname algoritmu \(i\). Postupne ich všetky prejdeme a budeme vyhadzovať tie, pre ktoré už vie Hodobox algoritmus dosť dobre (tie, ktoré vyžadujú znalosť nanajvýš \(y\)).

  • Popri vyhadzovaní chceme každej vyhodenej úlohe znižovať počet blokácii o jedna.

  • Keď zistíme, že úlohe klesol počet blokácií na 0, zvýšime počítadlo úloh, ktoré už vie Hodobox vyriešiť, o jedna.

• Po prejdení všetkých úloh v zozname vypíšeme počítadlo riešiteľných úloh.

Teraz by sme už mali vedieť naprogramovať toto riešenie.

Posledný krok k vzorovému riešeniu

Vyhadzovanie úloh sme chceli robiť tak, že prejdeme celý zoznam, a vždy, keď nájdeme úlohu, ktorá algoritmus \(i\) potrebuje na úroveň najviac \(y\), tak ju zo zoznamu odstránime.

Mohlo by sa nám ale stať, že by sme v každej akcii vyhadzovali len jednu úlohu z konca zoznamu, prípadne, ešte horšie, že naučením sa algoritmu by sme neodblokovali (neodstránili) žiadnu úlohu. V každej takejto akcii by sme prešli celý zoznam napriek tomu, že výsledok (počet riešiteľných úloh) sa vôbec nezmenil.

Chceli by sme teda v každom zozname prejsť len tie úlohy, ktoré mali šancu stať sa riešiteľnými, mali šancu na odblokovanie. Prvá úloha, ktorú by sme chceli zo zoznamu vyhodiť je tá, ktorá si vyžaduje najnižšiu znalosť algoritmu \(i\). Ak nevieme odstrániť tú, môžeme rovno skončiť, lebo žiadna iná úloha sa určite neodblokuje.

Stačí teda, ak si úlohy blokované algoritmom \(i\) usporiadame podľa potrebnej znalosti algoritmu. Na konci zoznamu bude úloha, ktorá vyžaduje najnižšiu znalosť. Keď sa Hodobox zlepší v algoritme \(i\), pozrieme sa na koniec zoznamu a ak už Hodobox vie algoritmus dostatočne, túto úlohu zo zoznamu vyhodíme a pokračujeme ďalšími úlohami – takými, ktoré potrebujú vyššiu znalosť algoritmu. Skracovanie zoznamu ukončíme, ak ďalšiu úlohu nevieme vyhodiť, teda ak Hodobox nevie algoritmus dostatočne pre žiadne ďalšie úlohy v zozname.

Hneď po načítaní vstupu si teda pre každý algoritmus usporiadame zoznam ním blokovaných úloh poľa potrebnej znalosti.⁴

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b) {
    return (a.second > b.second);
}

int main() {
    int n;
    scanf("%d", &n);
    // Počet aloritmov, potrebných na úlohy.
    vector< int > algs_count(n);

    // Pre každý algoritmus si budeme pamätať, ktoré úlohy ho potrebujú, a na akú úroveň.
    vector< vector< pair<int, int> > > problems;

    // V tejto premennej si budeme počítať, koľko algoritmov Hodobox zatiaľ vie.
    int uloh = 0;
    int max_alg = -1;
    for (int i = 0; i<n; ++i) {
        int a;
        scanf("%d", &a);
        algs_count[i] = a;
        for (int j = 0; j<a; ++j) {
            int x,y;
            scanf("%d %d", &x, &y);
            if (x > max_alg)) {
                max_alg = x;
                problems.resize(max_alg+1, vector< pair<int, int> >());
            }
            problems[x].push_back({i, y});
        }
        // Ak na úlohu nie sú potrebné žiadne algoritmy, tak ju Hodobox vie hneď zozačiatku.
        if (a == 0) uloh++;
    }
    // Pre každý algoritmus, si usporiadam úlohu, ktorého potrebujú, podľa úrovne. Od najväčšej po najmenšiu.
    for (unsigned i = 0; i<problems.size(); ++i) {
        sort(problems[i].begin(), problems[i].end(), compare);
    }
    vector<int> level(max_alg+1, 0);
    int p;
    scanf("%d", &p);
    for (int i = 0; i<p; ++i) {
        int c,u;
        scanf("%d %d", &c, &u);
        // Aloritmus nie je potrebný na žiadnu úlohu.
        if (c > max_alg) {
            printf("%d\n", uloh);
            continue;
        }
        level[c] += u;
        while (!problems[c].empty() && problems[c].back().second <= level[c]) {
            // Našli sme problém, ktorý potreboval algoritmus "c". 
            // Doteraz ale Hodobox nevedel tento algoritmus dostatočne.
            int problem = problems[c].back().first;
            problems[c].pop_back();
            algs_count[problem]--; 
            // Ak sa počet algoritmov potrebných na problém zmenší na nula, tak už túto úlohu vie Hodobox vyriešiť.
            if (algs_count[problem] == 0) uloh++;
        }
        printf("%d\n", uloh);
    }
    return 0;
}

Ideálna časová zložitosť

Znova si označme súčet počtov algoritmov ako \(A = \sum_{i=1}^{n} a_i\). Načítanie vstupu zvládneme určite v čase \(O(A + n)\) (keďže \(A\) môže byť menšie ako \(n\), treba v odhade uviesť aj \(n\)).

Potom si pre každý algoritmus musíme usporiadať zoznam jeho úloh. Potrebný čas bude \(O(\sum_{i=1}^{n} (b_i\log b_i))\) kde \(b_i\) je počet úloh, ktoré potrebujú algoritmus \(i\). Vieme, že platí \(A = \sum b_i\), a pre každé \(i\) platí \(b_i < A\), takže vieme predošlý súčet zjednodušiť: \[\sum_{i=1}^{n} (b_i \log b_i) \leq \sum_{i=1}^{n} (b_i \log A) = (\sum_{i=1}^{n} b_i) \cdot \log A = A \log A\] To znamená, že usporiadanie všetkých prvkov stíhame v \(O(A\log A)\).

Čo sa týka spracovávania Hodoboxových akcií, tak v jednej akcii sme mohli odstrániť \(0\) až \(n\) úloh. Ak by sme zložitosť jednej akcie odhadli ako \(O(n)\), v celkovej zložitosti by vystupoval člen \(O(pn)\), čo je ale príliš veľké číslo.

Na počítanie zložitosti akcií sa teda treba pozrieť z pohľadu každej úlohy samostatne. Predstavme si prípad, že na konci bude Hodobox vedieť vyriešiť každú úlohu. Vezmime si teda jednu úlohu \(i\), na ktorú treba \(a_i\) algoritmov. Ak ju Hodobox vie vyriešiť, tak sa niekedy musel naučiť každý z \(a_i\) algoritmov. Teda ak úloha \(i\) bola v \(a_i\) zoznamoch pre \(a_i\) rôznych algoritmov tak bola aj práve raz bola z každého z týchto zoznamov vyhodená (práve vtedy, keď sa naučil Hodobox daný algoritmus dostatočne). Môžeme teda povedať, že úloha \(i\) bola \(a_i\) krát “spracovaná”.

Každé spracovanie úlohy – vyhodenie zo zoznamu, znížene počtu blokácií, zvýšenie počítadla riešiteľných úloh – vieme robiť v čase \(O(1)\) (práve vďaka tomu, že úlohy vždy odstraňujeme z konca zoznamu). Sčítaním počtov spracovaní každej úlohy dostávame celkový počet spracovaní: \(\sum_{i=1}^{n} a_i = A\). V každej akcii tiež zvyšujeme úroveň naučeného algoritmu a vypisujeme výsledok, a preto musíme do zložitosti započítať aj člen \(O(p)\). Takže v najhoršom prípade, keď sa Hodobox naučí vyriešiť všetky úlohy, bude spracovanie akcií trvať \(O(A+p)\).

V súčte je teda časová zložitosť \(O(n + A\log A + p)\).

Naozajstná časová zložitosť

Možno ste si už všimli, že tu niečo nesedí. Veď naše veľké, dvojrozmerné pole má prvý rozmer \(max\_alg\), čo môže byť až \(10^6\) a toto pole predsa potrebujeme inicializovať. Každý z riadkov od \(0\) po \(max\_alg\) musí byť vytvorený, aj keď bude prázdny. Na načítanie prvej časti vstupu budeme potrebovať čas až \(O(A + n + max\_alg)\).

Možno sa pýtate, prečo sa vôbec nad \(max\_alg\) zamýšľame. Veď v najväčšom vstupe bude \(max\_alg\) najviac \(10^6\), rovnako ako aj \(A\) či \(n\). Pri malých vstupoch sa ale môže stať, že \(n\) bude 1, dokonca aj \(A\) bude 1, a predsa, ak na tú jednu úlohu potrebujeme vedieť práve jeden algoritmus s číslom \(10^6\), tak \(max_alg\) vyskočí na \(10^6\) a náš algoritmus bude potrebovať až rádovo \(10^6\) jednotiek pamäte a tiež rádovo \(10^6\) operácií na vytvorenie a vynulovanie daných polí. Ak by sme navyše mali algoritmy očíslované napríklad číslami \(1\) až \(10^9\), nemohli by sme si dovoliť používať takéto veľké pole.

Celková časová zložitosť bude teda \(O(n + max\_alg + A\log A + p)\), čo je v najhoršom prípade \(O(A\log A + n + p + 10^6)\).

Pamäťová zložitosť

Načítanie vstupu nám zaberie \(O(A)\) pamäte. Netreba ale zabudnúť aj na prázdne zoznamy pre čísla algoritmov, ktoré nikdy nepotrebujeme. Takže v skutočnosti to je \(O(A + max\_alg)\).

Okrem toho máme pole počtov blokácií jednotlivých úloh, ktoré je veľkosti \(n\), a pole, kde si udržiavame aktuálnu znalosť algoritmov veľké \(max\_alg\)+1.

Celková pamäťová zložitosť je teda \(O(A+n+max\_alg)\), v najhoršom prípade \(O(A+n+10^6)\).

Ako sa zbaviť závislosti na \(max\_alg\)

Určite vás zaujíma, ako teda dosiahnuť časovú a pamäťovú zložitosť naozaj \(O(A\log A + n)\) a \(O(A + n)\), teda nezávislú od \(max\_alg\).

Naším problémom sú dve polia. Pole problems kde si držíme pre každý algoritmus zoznam úloh a pole levels kde si pre každý algoritmus držíme jeho aktuálnu úroveň. Obe majú veľkosť závislú od \(max\_alg\).

Možno niektorí z vás poznajú pojem asociatívne pole, slovník či mapa. Asociatívne pole je pole, ktorého prvky nie sú indexované pomocou postupnosti celých čísel, ale pomocou kľúčov. Kľúčom môže byť číslo, textový reťazec a iné. Medzi operácie ktoré vieme s mapou robiť patrí: pozrieť sa na hodnotu pod kľúčom, zmeniť hodnotu pod kľúčom, vytvoriť nový kľúč, prejsť všetky kľúče atď.

V našom prípade by sme teda zvolili mapu, kde kľúče budú celé čísla – konkrétne čísla algoritmov. Ale iba tých, ktoré naozaj potrebuje nejaká úloha. Pod týmto kľúčom by bol zoznam dvojíc: úloha a úroveň. Vždy, keď prvýkrát narazíme na algoritmus \(x\), ktorý zatiaľ žiadna úloha nepotrebovala, tak vytvoríme v mape prázdny zoznam pod kľúčom \(x\) a pridáme tam aktuálnu úlohu. Ak sme už algoritmus predtým videli, tak len do jeho zoznamu pridáme úlohu.

To nám vyrieši problém s inicializáciou prázdnych zoznamov pre algoritmy, ktoré žiadna úloha nepotrebuje. Rovnako vieme aj prejsť iba všetky existujúce kľúče v mape, a tak sa vyhnúť usporiadavaniu prázdnych zoznamov pre tieto algoritmy. Podobne vieme mapu využiť aj na pole levels.

Okrem časovej zložitosti, použitie asociatívneho poľa zlepšuje aj pamäťovú zložitosť, keďže sme sa v prípade poľa levels zbavili núl pre nepotrebné algoritmy. Rovnako pre pole problems sme sa zbavili prázdnych zoznamov.

Obyčajná mapa so sebou prináša aj nevýhody, ktoré sa prejavia pri veľkom počte záznamov. Ak do nej chceme niečo vložiť, alebo sa pozrieť na nejakú hodnotu, tak to nie je v konštantnom čase, ale v \(O(\log s)\), kde \(s\) je aktuálna veľkosť mapy.

Preto je lepšie v tomto prípade namiesto mapy použiť hashmapu, s ktorou sa pracuje väčšinou podobne ako s mapou, ale operácie sú v konštantnom čase, rovnako ako pri práci s poľom. Teda využitím hasmapy dostaneme naozaj čas. zložitosť \(O(A\log A + n + p)\).

Porovnanie jednotlivých operácii môžeme vidieť v tabuľke, kde \(s\) predstavuje aktuálnu veľkosť mapy/hashmapy.

Mapu môžete nájsť implementovanú v rôznych jazykoch. V C++ sa mapa po anglicky nazýva map(dokumentácia) a hashmapa je unordered_map (dokumentácia). V Python-e máte hashmapu pod názvom dict(dokumentácia).