Zadanie
Hodobox je už vysokoškolák, a preto bol tento rok prvýkrát na školskom kole súťaže ACM. A čo sa stalo-nestalo, predbehla ho stredoškoláčka a ešte aj chlapec so zápalom pľúc! Teraz sa Hodobox snaží prejsť si všetky úlohy odznova a skúsiť si ich preriešiť. Má však malý problém. Niečo sa stalo a zabudol všetky algoritmy. Nevie už nakódiť ani len binárne vyhľadávanie, ktoré sa naučil na letnej škole.
Rozhodol sa teda, že sa všetky potrebné algoritmy znova naučí. Každá úloha sa dá definovať ako množina algoritmov, ktoré sú potrebné na jej vyriešenie. Pre jednoduchosť si algoritmy očíslujeme od \(1\) po \(1\,000\,000\) (napríklad \(47\) je binárne vyhľadávanie).
Nie je to však až také jednoduché. Rôzne úlohy vyžadujú znalosť rôznych algoritmov do rôznej hĺbky. Napríklad taký merge-sort – v jednej úlohe ním len usporiadame prvky, v inej však spočítame počet inverzií. Úloha má teda ku každému algoritmu, ktorý je potrebný na jej vyriešenie priradenú ešte aj potrebnú úroveň znalosti tohto algoritmu.
Hodobox má so sebou Paulínkinu príručku ‘How to win IOI for dummies’. V nej si Paulínka spísala všetky algoritmy od výmyslu sveta. Hodobox sa nimi teraz prehrýza a veľmi by ho zaujímalo, kedy už bude konečne schopný naprogramovať všetky úlohy zo školského kola ACM.
Úloha
Na vstupe dostanete popis školského kola, ktoré sa skladá z \(n\) úloh. Pre každú úlohu dostanete zoznam algoritmov potrebných na jej vyriešenie (číslo algoritmu a úroveň potrebnú na vyriešenie tejto úlohy).
Potom nasleduje \(p\) Hodoboxových akcií, kde si vždy zlepší chápanie nejakého algoritmu o istú úroveň. Na začiatku Hodobox nevie nič (jeho úroveň znalosti každého algoritmu je \(0\)).
Vašou úlohou je po každej akcii vypísať, koľko úloh zo školského kola je už Hodobox schopný vyriešiť.
Formát vstupu
Na prvom riadku vstupu je počet úloh \(n ~ (1 \leq n \leq 10^6)\).
Nasleduje \(n\) popisov úloh. Popis \(i\)-tej úlohy začína číslom \(a_i\) na samostatnom riadku – počet algoritmov nutných na vyriešenie \(i\)-tej úlohy (\(0 \leq a_i < 10^6\)). Potom nasleduje \(a_i\) riadkov s popismi jednotlivých algoritmov potrebných pre túto úlohu. Každý z nich obsahuje dve čísla \(x ~ (1 \leq x \leq 10^6)\) – číslo daného algoritmu a \(y ~ (1 \leq y \leq 10^9)\) – potrebná úroveň znalosti tohto algoritmu.
Zároveň platí, že \(\sum a_i \leq 10^6\).
Potom nasleduje jeden riadok s číslom \(p\) – počet akcií, kedy sa Hodobox učí nejaký algoritmus. Platí, že \(p \leq 10^6\). Nasleduje \(p\) riadkov. V každom sú dve čísla \(c_j\) a \(u_j\), kde \(c_j\) je číslo algoritmu a \(u_j\) znamená, o koľko sa Hodoboxovi zlepšila úroveň znalosti algoritmu \(c_j\). Platí že \(1 \leq c_j \leq 10^6\) a \(1 \leq u_j \leq 10^9\).
Vstupy v tejto úlohe budú veľmi veľké. V C++ preto odporúčame použiť miesto knižnice <iostream>
knižnicu <cstdio>
. Ak chcete použvívať <iostream>
, vložte si na začiatok programu nasledovné príkazy, ktoré urýchlia vstup a výstup: ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
Na vypisovanie nového riadku tiež nepoužívajte endl
, ale znak nového riadku '\n'
.
V pomalších jazykoch sa nemusí dať získať plný počet bodov na testovacích vstupoch. Za optimálne riešenie však stále viete získať plný počet za popis riešenia.
Formát výstupu
Na výstupe bude \(p\) riadkov. Na \(j\)-tom riadku bude jedno číslo – počet úloh ktoré vie Hodobox vyriešiť, keď sa už zlepšil v algoritmoch \(c_1\) až \(c_j\) o príslušné úrovne.
Príklad
Input:
3
1
14 1
0
2
13 3
14 1
2
13 3
14 1
Output:
1
3
Už na začiatku vie Hodobox vyriešiť druhú úlohu, pretože na ňu netreba vedieť nič. Po prvej akcii si zlepší chápanie algoritmu 13 z 0 na 3, čo mu nepomôže k ďalšej úlohe, takže výstup je 1. Druhou akciou si zlepší chápanie algoritmu 14 z 0 na 1, čo mu pomôže vyriešiť prvú aj tretiu úlohu.
Input:
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
Output:
0
1
1
1
2
Hodobox nevie pred prvou akciou vyriešiť ani jednu úlohu. Po prvej akcii sa binárne vyhľadávanie (algoritmus 47) naučí na úroveň 1. To mu ale nepomôže k žiadnej úlohe, takže výstup je 0.
Ďalšou akciou si zlepší znalosť vyhľadávania na 4. Preto vie vyriešiť tretiu úlohu, ale nič viac. Potom sa naučí algoritmus 42 na úroveň 12, čo mu stále nepomôže k ďalším úlohám. Potom si zlepší algoritmus 13 z nuly na 5, takisto mu to nepomôže. Na prvú úlohu ma slabú znalosť algoritmu. č. 47 a na druhú zas algoritmu 7.
Poslednou akciou sa naučí algoritmus 47 na úroveň 16 (\(4 + 12\)), takže už bude vedieť vyriešiť prvú úlohu.
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íc1. \(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\).2
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.3
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.4
#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.
Mapa | HashMapa | |
---|---|---|
Vytvoriť kľúč | \(O(\log s)\) | \(O(1)\) |
Vrátiť hodnotu pod kľúčom | \(O(\log s)\) | \(O(1)\) |
Zmeniť hodnotu pod kľúčom | \(O(\log s)\) | \(O(1)\) |
Prejsť všetky kľúče | \(O(s)\) | \(O(s)\) |
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).
Dvojica je implementovaná v
C++
akopair
. Prípadne by ste si mohli spraviť vlastnýstruct
. VPython
-e viete využiť \(k\)-ticu pod názvomtuple
.↩Keďže polia sú indexované od 0, v poli veľkosti \(10^6\) by algoritmus s číslom \(10^6\) už nemal svoj zoznam úloh. Preto pridávame \(+1\).↩
Nech si Hodobox zlepšil znalosť algoritmu \(i\) z \(x\) na \(y\). Odstránime úlohy, ktoré algoritmus \(i\) potrebovali na úroveň \(a\), takú že platí \(x < a \leq y\).↩
Ak využívate
sort
vC++
alebo vPython
-e, tak si dajte pozor na to, že zoznam dvojíc sa primárne usporiadava podľa prvého prvku z dvojice. Oplatí sa teda mať v dvojiciach uloženú najprv potrebnú úroveň znalosti algoritmu a až potom číslo úlohy, alebo si napísať vlastnú porovnávaciu funkciu.↩
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ť.