5. Kopa neumytého riadu vzorové riešenie

7
PRIDAJ 30
NAJSPINAVSI
PRIDAJ 20
PRIDAJ 10
NAJSPINAVSI
UMY
NAJSPINAVSI

30
10
20

6
NAJSPINAVSI
PRIDAJ 8
PRIDAJ 10
NAJSPINAVSI
UMY
UMY

-1
8

Pri programoch, ktoré majú niečo simulovať, je vždy dobré si vyskúšať zopár príkladov vstupu a pochopiť, ako má daný program fungovať. To vedie k riešeniu, ktoré síce nie je rýchle, ale zato je určite správne. Objavený postup totiž stačí prepísať pomocou programovacieho jazyka.

Úvod do zásobnika

Pokiaľ viete čo je dátová štruktúra zásobník, môžete túto časť spokojne preskočiť.

Kopa tanierov, ktorú simulujeme sa v mnohom správa ako abstraktná dátová štruktúra s názvom zásobník. Nenechajte sa vystrašiť. Slovné spojenie abstraktná dátová štruktúra iba vyjadruje, že napriek tomu, že na uloženie informácií, napríklad čísel, používame pole a pamäť počítača, dáta máme uložené v špeciálnej, nami zvolenej forme.

Inak povedané, počítaču pripadá uloženie dát náhodné, pre nás má však hlbší zmysel. Práve to vyjadruje slovo abstrakcia. Zásobník má ako aj iné dátové štruktúry dve hlavné funkcie – vieme doň prvky (napr. čísla) pridávať a vieme z neho prvku odoberať. Obe tieto operácie však majú svoje obmedzenia. V prípade zásobníku platí, že pridávať a odoberať prvky vieme iba z vrchu zásobníka.

Predstavte si, že máte kopu tanierov. Keď nejaký špinavý pridávate, položíte ho na vrch kopy. A keď nejaký idete umyť, je asi prirodzené začať tým najvrchnejším, čím ho z vrchu kopy odoberiete. Takto funguje aj dátová štruktúra zásobník. Obmedzenie toho, ako vieme vkladať a vyberať nám dáva určitú silu. Môžete si všimnúť, že keď do zásobníka vložíme niekoľko čísel tak platí, že posledné vložené je na vrchu zásobníka. Predposledné vložené čislo je zas priamo pod vrchom zásobníka atď.

Zásobník vieme ľahko simulovať pomocou poľa. Vytvoríme si dostatočne veľké pole a jednu premennú, v ktorej si pamätáme index na miesto v zásobníku. Tento index nám ukazuje, kam si poznačiť vkladané číslo. Po jeho pridaní do poľa index zväčšíme. Pri odstraňovaní stačí naopak index iba zmenšiť.

Príklady implementácie zásobníka v jazykoch C++ a Python si môžete pozrieť tu:

Ak si chcete o zásobníku a niektorých ďalších jednoduchých dátových štruktúrach prečítať o kúsok viac, odporúčame zájsť do KSP kuchárky.

Pomalšia simulácia kopy

Ak už vieme čo zásobník je, môžeme sa pustiť do prvého riešenia. Vidíme, že naša kopa tanierov sa správa presne ako zásobník. Navyše však musíme vedieť zistiť aj to, aká je najmenšia hodnota čísel v zásobníku.

Pokiaľ máme zásobník uložený tak ako sme si spomínali vyššie, teda v poli či liste, je jednoduché pri každom príkaze typu NAJSPINAVSI prejsť týmto poľom a zistiť, aké najmenšie číslo sa v ňom nachádza. Toto riešenie nám prinesie zaslúžených 5 bodov, ale na väčšie vstupy nebude dostatočne rýchle. Dôvodom je, že pri každom takomto príkaze hľadáme minimum spomedzi všetkých čísel v zásobníku, ktorých tam môže byť časom naozaj veľmi veľa.

Rýchlejšia simulácia kopy

Tento odstavec je venovaný druhej sade, kde sú čísla, ktoré sa nachádzajú v kope resp. v zásobníku z malého rozsahu. Ako vieme tento fakt využiť pri riešení? Použijeme techniku, ktorá sa v takýchto prípadoch používa pomerne často.

Technika spočíva v tom, že si v pomocnom poli budeme na index \(i\) značiť počet čísel \(i\) v zásobníku. Zásobník bude aj naďalej fungovať rovnako, toto pomocné pole nám pomôže iba pri hľadaní najmenšieho čísla.

Keď do zásobníka pridáme číslo \(i\), zväčšíme v pomocnom poli číslo na \(i\)-tom políčku o 1, pri vyberaní zo zásobníka ho zase zmenšíme. Pri hľadaní minima nám zjavne stačí prejsť toto pomocné pole a nájsť prvé políčko, ktoré obsahuje nenulové číslo. Uvedomme si, že napriek tomu, že zásobník môže byť obrovský, naše pomocné pole je, vďaka obmedzeniu na maximálnu veľkosť čísel na vstupe, malé. Toto riešenie nám prinesie tiež 5 bodov. Implementácia popísaného riešenia môže vyzerať napríklad takto:

Kombinácia riešení

V prípade, že ste prišli na obidve vyššie spomenuté riešenia, darí sa vám získať po 5 bodov na rôznych sadách vstupov. Môžeme ich preto šikovne spojiť do jedného. V tomto riešení si opäť vytvoríme pomocné pole, do ktorého si budeme značiť počet čísel \(i\) v zásobníku a toto pole budeme používať na hľadanie najmenšieho čísla. Ak sa ale stane, že na zásobník by sme mali pridať príliš veľké číslo, prepneme náš program do druhého módu, v ktorom bude pri hľadaní minima prechádzať celý zásobník. V druhej sade takúto zmenu riešenia nespravíme, lebo čísla budú malé a v prvej sade síce budeme prechádzať celý zásobník, ale ten nemôže byť príliš veľký. Výsledkom je riešenie za 10 bodov.

Vzorové riešenie

Predstavme si, že v zásobníku sú uložené nejaké čísla a poznáme najmenšie z nich, ktoré si označíme \(x\). V prípade, že na zásobník pridáme číslo väčšie ako \(x\), minimum sa nezmenilo a môžeme pokojne pokračovať ďalej. Problém nastane iba v prípade, že na zásobník sa pridá číslo \(y\), ktoré je menšie ako \(x\). V tom prípade sa novým minimom má stať číslo \(y\). Uvedomme si však dôležitú vec. Kým bude číslo \(y\) v zásobníku, je menšie ako \(x\) a preto \(x\) minimom nebude. Ak ale \(y\) zo zásobníka odstránime, zásobník bude vyzerať rovnako, ako tesne predtým, ako sme doň \(y\) vložili. Tým pádom sa \(x\) stane opäť minimom.

Z toho vyplýva, že pri zmene minima si jeho starú hodnotu môžeme poznačiť, pretože sa nám v budúcnosti môže ešte zísť. Situácia je však o niečo komplikovanejšia. Zoberme si totiž vyššie popísaný príklad, v ktorom \(y\) nahradilo minimum \(x\) a to sme si teda niekam poznačili. Skôr ako \(y\) zo zásobníka odstránime však doň pridáme číslo \(z\), ktoré je ešte menšie ako \(y\). V tomto prípade sme v podobnej situácii. Ak sa totiž v budúcnosti stane, že \(z\) zo zásobníka odstránime, \(y\) sa opäť stane minimom a my by sme si to mali zapamätať. K číslu \(x\) si teda poznačíme aj číslo \(y\). Keď potom \(z\) odíde zo zásobníka, za nové minimum označíme posledné poznačené číslo, teda \(y\). A keď bude odstránené aj to, opäť siahneme po poslednom poznačenom čísle, teda \(x\).

V skutočnosti sa nám tu formuje druhý zásobník, do ktorého si značíme akúsi “históriu miním”. Keď pridávame do zásobníka číslo, ktoré je väčšie ako doterajšie minimum, nič sa nedeje. Ak však pridávame číslo menšie, musíme zmeniť aktuálne minimum na novú hodnotu a tú starú si zapíšeme do zásobníka miním. Pri vyberaní čísel zo zásobníka sa nič nedeje, kým neodstránime aktuálne najmenší prvok. V takom prípade sa totiž minimum musí zmeniť a my siahneme po vrchu zásobníka miním, kde na nás čaká správna hodnota, ktorú z tohto zásobníka tiež odstránime.

Takéto riešenie je v skutočnosti veľmi rýchle. Pri každej zmene zásobníka totiž nové minimum vypočítame v konštantnom čase. Buď sa totiž nezmení, alebo je prepísané pridaným číslom, alebo sa nastaví na hodnotu najvyššieho čísla v zásobníku histórie miním. Celková časová zložitosť je preto \(O(n)\). Vo vzorovej implementácii navyše používame ešte jeden trik. Najmenšie číslo si do histórie miním vkladáme po každom pridaní prvku. Vďaka tomu nemusíme kontrolovať, či odstraňované číslo je aktuálnym minimom, po vrchu historického zásobníka siahneme zakaždým. Navyše nám to s ľahkosťou vyrieši prípady, keď sa v zásobníku nachádza viacero rovnakých čísel, čo sme predtým museli špeciálne ošetrovať.