5. LTT vzorové riešenie

6 one
1 2 4 1 2 1

3

Najjednoduchšie riešenie

Skúsme najprv vymyslieť a naprogramovať čo najjednoduchšie riešenie. No a čo je jednoduchšie, než vyskúšať všetky možnosti? Dôležité však je, aby aj implementácia bola jednoduchá – v tomto prípade sa nám preto hodí rekurzia.

Povedzme, že sa nachádzame na pozícii \(poz\) a máme obuté šľapky veľkosti \(vel\). Nechceme tu zostať trčať, takže sa pohneme. Pred tým nás ale čaká rozhodnutie (prezuť či neprezuť) a my vyskúšame obe možnosti. Toto vieme jednoducho vyjadriť rekurzívnym vzťahom:

n, way = input().split()
n = int(n)
velkosti = list(map(int, input().split()))

def kroky(poz, vel):
    if poz >= n:
        return 0
    return 1 + min(kroky(poz + vel, vel), kroky(poz + velkosti[poz], velkosti[poz]))

print(kroky(0, velkosti[0]))

Keďže sa vždy priblížime k cieľu o aspoň jeden meter, vykonáme najviac \(n\) krokov. Časová zložitosť tohto riešenia je \(O(2^n)\) a pamäťová \(O(n)\) (pamätáme si pole veľkostí, ale nezabudnime ani na rekurziu hĺbky \(n\)). Za takýto kód dostaneme 2 body a celkovo má iba 10 riadkov!

Akú časovú zložitosť by mala rekurzia, ktorá by sa vetvila iba ak je vel rôzne od velkosti[poz]? Odpoveď: ¹

Oveľa lepšie a pritom skoro rovnaké

Spomenuté riešenie má tri problémy na zvyšných sadách:

1. Dostávame EXC, pretože rekurzia je príliš hlboká.
2. Ak by sme aj nedostali EXC, tak by sme dostali TLE, pretože máme exponenciálnu zložitosť.
3. Ak by sme aj nedostali TLE, tak by sme dostali WA na poslednej sade, pretože nezohľadňujeme kroky smerom späť.

Čo s tým? Prvý problém opravíme jednoducho tak, že zvýšime limit rekurzie pomocou sys.setrecursionlimit.

Druhý problém opravíme tiež jednoducho, memoizáciou. Funkcia kroky pre rovnaké parametre vždy vráti rovnaký výsledok, takže si ho môžeme uložiť a pri ďalšom volaní ho vrátiť. Keďže máme dva parametre, oba v rozsahu od \(0\) do \(n\), existuje iba \(n^2\) možností. Časová zložitosť tohto riešenia bude potom iba \(O(n^2)\). V Pythone vieme memoizáciu jednoducho prilepiť na každú funkciu pomocou dekorátora functools.cache.

Tretí problém vieme tiež jednoducho opraviť tak, že do rekurzívneho vzťahu pridáme aj kroky smerom späť.

No aha, aké jednoduché!

Avšak trochu som klamal. Je pravda, že každý problém sme takto vyriešili, druhá a tretia oprava ale nie sú navzájom kompatibilné. Ak však upustíme od chodenia dozadu, dostávame riešenie s časovou a pamäťovou zložitosťou \(O(n^2)\), pridali sme iba 4 riadky a dostaneme až 6 bodov. Great success!

Memoizácia smerom dozadu

Čo je vlastne ten problém s chodením dozadu? V rekurzii vieme spraviť v šľapkách krok tam a späť čím sa dostaneme na rovnakú kombináciu parametrov funkcie. Keďže sme pre túto kombináciu ešte nič nevypočítali, začneme ju počítať znova a zacyklíme sa.

Keď zvyčajne robíme DFS na cyklickom grafe, pamätáme si o každom vrchole informáciu, či sme ho už navštívili, a značíme si ju, už keď do neho prichádzame, nie až keď z neho odchádzame (ako to vlastne robíme teraz).

def dfs(v):
    if navstiveny[v]: return
    navstiveny[v] = True
    ...

Možno nás teda napadne, že by sme si do memoizácie tiež mali niečo zapísať hneď, ako vstúpime do funkcie. Potom v prípade, že sa začneme cykliť (čo budeme vedieť detegovať), vrátime ako odpoveď nejakú veľkú hodnotu (nekonečno). Predsa sa nám neoplatí vrátiť do situácie kde sme už boli, takže je to to isté, ako keby sme sa tam ani nepokúsili dostať.

Alebo? To, že sa nám neoplatí vrátiť síce je pravda pre nejakú konkrétnu postupnosť krokov, avšak tento výsledok sa bude memoizovať a bude mať dopad aj na iné postupnosti krokov. Ak sa odmietneme vrátiť do situácie, kde sme už boli, je to ako keby sme z grafu po ktorom sa pohybujeme odstránili danú orientovanú hranu. Ak však optimálna cesta vedie cez túto hranu, tak ju už nikdy nenájdeme! Skúste si nájsť príklad, kde toto nastane.

Riešenie smerom späť

Samozrejme, kde je memoizácia, tam je aj dynamické programovanie. Predpokladáme, že viete, čo je to dynamika a ako ju implementovať, keď už sme si vysvetlili riešenie na memoizácii. Ak nie, tak toto je výborná príležitosť, aby ste sa to naučili. Nebudeme tu rozpisovať detailný princíp dynamiky, ten viete nájsť v kuchárke. Prečítajte si ju, vráťte sa sem a naprogramujte si túto úlohu.

Rovnako ako pri rekurzií s memoizáciou, aj tu máme časovú a pamäťovú zložitosť \(O(n^2)\) a nevieme sa vracať, lebo by sme sa zacyklili alebo dostali zlý výsledok.

No, keď už máme tú dynamiku, nemohli by sme ju nejako využiť aj na poslednú sadu? Pri jednom výpočte dynamiky vypočítame všetky optimálne hodnoty pre prípad, že sa vieme hýbať iba smerom dopredu. Spravme preto druhý výpočet dynamiky, spustený na výsledkoch prvého výpočtu, avšak opačným smerom. Pre každý stav si zapamätáme minimum z oboch výpočtov – dostávame hodnotu, ako sa do tohto stavu dostaneme najrýchlejšie, ak sa môžeme hýbať buď smerom dopredu, alebo najprv smerom dopredu a potom niekoľko krokov smerom dozadu. Potom môžeme spraviť ďalší výpočet dynamiky, tentoraz zasa smerom dopredu. Získame výsledky pre trasy, v ktorých môžeme nanajvýš dva krát zmeniť smer. Takto vieme pokračovať v striedaní smerov a počítaní dynamiky, až kým sa nám neprestanú zlepšovať výsledky.

Kedy sa nám prestane zlepšovať výsledok? Keďže optimálne kráčanie má nanajvýš \(n\) krokov, v najhoršom prípade môžeme zmeniť smer \(\frac{n}{2}\) krát. Takže celková časová zložitosť riešenia je \(O(n^3)\) (viete vymyslieť vstup, na ktorom tento najhorší prípad nastane?).

Túto techniku vieme uplatniť na takmer každý prístup, ktorý vie vypočítať optimálne hodnoty jedným smerom, čím sa nám lineárne zhorší časová zložitosť.

Úloha ako graf

Už sme to tu raz spomenuli a zadanie nám to aj celkom naznačuje – to, čo tu robíme, je vlastne hľadanie najkratšej cesty v grafe.

Reprezentujme si teda úlohu ako graf s ohodnotenými orientovanými hranami. Graf bude mať \(n\) vrcholov, jeden pre každú pozíciu, na ktorej môžeme stáť. Predstavme si, že sa vždy prezujeme, keď vojdeme do vrcholu. Z vrcholu \(i\) nepôjdu len blízke hrany predstavujúce jeden krok, ale aj drahšie hrany do všetkých vrcholov, kam vieme bez prezutia dokráčať v šľapkách z vrcholu \(i\). Čiže pre každý vrchol \(i\) a počet krokov \(k\) spravíme hranu \((i, i + k \cdot v_i)\) a \((i, i - k \cdot v_i)\) ktorých cena bude \(k\).

Takto sme sa zbavili rozhodovania o prezúvaní a môžeme použiť Dijkstrov algoritmus na hľadanie najkratšej cesty v grafe.

Z každého vrcholu vie ísť hrana do každého iného vrcholu (viete, na akom vstupe sa to stane?). Počet vrcholov je \(n\) a počet hrán \(O(n^2)\). Časová zložitosť bude \(O(n^2 \log n)\) a pamäťová \(O(n^2)\). Takto za program môžeme dostať až 8 bodov a stačilo naprogramovať Dijkstru. Pche, však to viem aj poslepiačky!

Ale vieme to spraviť aj lepšie. Samozrejme si nemusíme pamätať všetky hrany, vieme ich kedykoľvek ľahko vypočítať. Pamäťová zložitosť sa nám teda zmenší na \(O(n)\). Navyše, Dijkstrov algoritmus vieme upraviť tak, aby na hustých grafoch nepoužíval haldu, ale pole. Takto dostaneme časovú zložitosť \(O(n^2)\).

Riedky graf

Máme 8 bodov, päťka je triviálna, KSP ide dolu vodou. Ale čoby, poďme to vyriešiť ešte lepšie!

Pozrime sa na ten “graf”, ktorý sme používali pri memoizácii a dynamike. Tam je každý stav vrcholom a hrany sú prechodmi medzi týmito stavmi. V tomto prípade máme \(n^2\) vrcholov a každý z nich má nanajvýš tri hrany (krok dopredu, krok dozadu, prezuť šľapky). Moc sme si nepomohli.

Avšak! V tomto má bežná rekurzia s memoizáciou výhodu voči dynamike – navštívime iba vrcholy, ktoré sú relevantné pre riešenie. Ak na vstupe nie sú šľapky veľkosti \(17\) alebo šľapky veľkosti \(42\) sú iba na pozícii \(9\), tak napríklad stavy [poz=5, vel=17] alebo [poz=8, vel=42] nikdy nenavštívime. Koľko je teda takýchto “relevantných” vrcholov takých, ktoré v rekurzii navštívime?

Pri riešení Dijkstrou sme mali problém na vstupe s \(n\) jednotkami. Tam sme mali kompletný graf s \(n\) vrcholmi a \(O(n^2)\) hranami. V tomto riešení by však náš graf obsahoval iba \(n\) relevantných vrcholov (všetky vrcholy kde vel=1). Výborne!

Najhorší prípad

Čo je teda najhorší možný prípad? Ak máme na vstupe šľapky veľkosti \(k\) na pozícii \(p\), potom určite všetky vrcholy [poz=p+x*k, vel=k] (kde \(x\) je celé číslo a \(1 \leq p+x*k \leq n\)) budú relevantné.

Ľahko vidno, že pre najhorší prípad sa nám neoplatí mať viac ako \(k\) šľapiek veľkosti \(k\), pretože potom by určite niektoré dvoje šľapky generovali rovnakú množinu relevantných vrcholov. Konkrétne chceme šľapky veľkosti \(k\) rozmiestniť na pozície s rôznymi zvyškami po delení \(k\).

Ak toto spravíme, potom šľapky veľkosti \(k\) pridávajú približne \(\frac{n}{k}\) (\(\lfloor \frac{n}{k} \rfloor\) alebo \(\lceil \frac{n}{k} \rceil\)) relevantných vrcholov. Ak chceme maximalizovať počet relevantných vrcholov, mali by sme zvoliť čo najmenšie \(k\).

Najhorší vstup bude teda tvaru 1 2 2 3 3 3 4 4 4 4 5 .... Aké je posledné číslo v tomto vstupe? Chceme vedieť, pre aké najmenšie \(m\) je \(n \leq \sum_{k=1}^m k = \frac{m(m+1)}{2} < \frac{(m+1)^2}{2}\), čiže \(\sqrt{2n}-1 < m\).

Pre jednoduchosť predpokladajme, že pre každé \(1 \leq k \leq m\) máme na vstupe \(k\) šľapiek veľkosti \(k\). Keďže každé \(k\) pridáva približne \(\frac{n}{k}\) relevantných vrcholov, z každého \(k\) máme približne \(k \cdot \frac{n}{k} = n\) relevantných vrcholov. Takže celkový počet relevantných vrcholov je \(n \cdot m = n \cdot \sqrt{2n} = O(n^{1.5})\).

Prechod riedkeho grafu

Ukázali sme, že relevantný graf má iba \(O(n^{1.5})\) vrcholov a hrán. Uvedomme si, že keby sme vedeli spraviť memoizáciu pôvodnej rekurzie, dosiahli by sme takúto časovú zložitosť – to sa nám ale nepodarilo.

Pri prechode je totiž dôležité, aby sme sa necyklili, ale stále prešli po každej hrane (keďže vie byť potenciálne súčasťou optimálnej cesty). To sa dá jednoducho dosiahnuť, ak budeme vrcholy prechádzať v správnom poradí – s klesajúcou vzdialenosťou od cieľa (a teda s rastúcou vzdialenosťou od štartu).

Vieme znova použiť Dijkstru, ale spomeňme si, že v tomto prípade máme neohodnotené hrany, takže nám stačí použiť BFS.

Keďže relevantný graf je riedky, vzdialenosti si musíme tiež pamätať v riedkom formáte – použijeme hešovací slovník.

Dosiahli sme časovú a pamäťovú zložitosť \(O(n^{1.5})\).

Všetko to spolu súvisí

Uvedomme si, čo všetko sme doteraz robili:

• BFS,
• Dijkstra,
• striedavé dynamické programovanie,
• jednosmerné dynamické programovanie,
• memoizácia,
• exponenciálna rekurzia.

Možno je to zjavné, keďže všetky riešia tú istú úlohu, ale principiálne naozaj všetky tieto algoritmy robia to isté – skúšajú každú cestu v grafe, aby z nich vybrali tú najkratšiu.

Odmyslime si, že majú tieto algoritmy rôzne názvy a časové zložitosti.

Exponenciálna rekurzia naozaj skúsi (aspoň) raz prejsť každú možnú cestu a zapamätá si tú najlepšiu. V tomto prípade je poradie, v akom to robí, poradím DFS prechodu. Ale rovnako by to mohlo byť ľubovoľné iné poradie, ktoré prejde každú cestu aspoň raz.

Ostatné spomenuté algoritmy robia všetky to isté – menia poradie skúšania ciest. Správnym zvolením poradia skúšania ciest potom vedia dosiahnuť zrýchlenie. Ak som už pre nejaký vrchol našiel optimálny prefix (BFS, Dijkstra, dynamika) /suffix (memoizácia)/, tak môžem zahodiť cesty, ktoré prechádzajú týmto vrcholom a majú iný prefix /suffix/. Každou takouto úvahou zahodím exponenciálne veľa ciest, čím nakoniec dosiahnem polynomiálnu zložitosť.

V každom z týchto algoritmov sme však museli v nejaký moment zohľadniť každú z tých exponenciálne veľa možných ciest. Ak by sme nejakú možnosť vynechali, mohli by sme prísť o optimálne riešenie. Pre každú neoptimálnu cestu existuje v priebehu daného algoritmu moment, kedy sme sa “pozreli” na jej prefix /suffix/ a povedali si “táto druhá cesta je aspoň taká dobrá, a preto túto prvú môžem zahodiť”.

Samozrejme, nemohli sme sa priamo individuálne pozrieť na každú z exponenciálne veľa možných ciest (inak by sme mali exponenciálnu zložitosť). Ale každá neoptimálna cesta patrila do nejakej triedy ciest, ktorú sme naraz “zahodili”.

Najlepší algoritmus je teda ten, ktorý pre danú úlohu aj v najhoršom prípade zvolí najlepšie poradie skúšania ciest.

Optimalizácie

No tak sme si teoreticky ukázali šesť algoritmov, ktoré všetky riešia tú istú úlohu. A to sa ešte každý z nich dá naprogramovať rôznymi spôsobmi.

Časové limity boli v tejto úlohe celkom voľné, takže ste mohli byť kreatívni v štýle implementácie. Ale to neznamená, že sa nedali napísať rýchle riešenia. Každé riešenie sa spoliehalo na nejakú štruktúru na prehľadávanie “grafu”. Pozrime sa konkrétne na BFS riešenie a v krátkosti spomeňme niektoré pamäťové optimalizácie, ktoré môžeme v tomto riešení použiť.

Všetok kód, ktorý tu budeme spomínať, je úplne identický, s rozdielom jednej štruktúry na pamätanie si navštívených vrcholov. Cieľom tejto štruktúry je pamätať si \(O(n^{1.5})\) stavov, ktoré sme už navštívili. Počas behu programu do tejto štruktúry pristupujeme veľa krát. Je preto dôležité, aby bola čo najrýchlejšia.

Je intuitívne na tento účel použiť množinu. Ak sme programovali v C++, v štandardnej knižnici máme na výber medzi std::set a std::unordered_set (mimo STL existujú lepšie možnosti). To, ktorú použiť, sa mení od prípadu k prípadu.

std::unordered_set funguje na princípe hešovania, čo znamená, že prístup do nej trvá v priemere \(O(1)\) času, avšak s veľkou konštantou, a štandardne nepodporuje ukladanie štruktúr ako std::pair.

Ak sa ale rozhodneme použiť std::unordered_set, určite sa oplatí použiť reserve, tak ako bolo spomenuté v zadaní. V týchto riešeniach nám to zrýchlilo programy od 1.6x (C vs D) až po 2.1x (F vs G). Je samozrejme dôležité zvoliť dostatočne veľkú rezervu, inak nebude mať táto optimalizácia žiaden efekt.

Ak sme sa rozhodli použiť std::set, boli sme veľmi smutní, pretože v tomto prípade to bolo vždy niekoľko krát pomalšie než rovnaké riešenie s pridaným slovom unordered_ (B vs C, A vs F).

Pozrime sa na dve možnosti, ako si pamätať dáta pre stavy, ktoré sú dvojice – množina dvojíc alebo dvojrozmerná štruktúra. Môžeme si to predstaviť tak, že sme namiesto hľadania [poz, vel] v množine obsahujúcej \(O(n^{1.5})\) prvkov veľmi rýchlo v poli na indexe poz našli množinu obsahujúcu \(O(\sqrt n)\) prvkov. V Pythone bolo pole množín 2.7x rýchlejšie než množina dvojíc. V C++ to je trochu komplikovanejšie. V prípade použitia std::set bolo pole množín tiež 3x rýchlejšie (A vs B). Keďže std::unordered_set nepodporuje ukladanie dvojíc, musíme si napísať vlastnú hešovaciu funkciu. Použitím zlej hešovacej funkcie sme dostali program, ktorý bežal stovky krát pomalšie (C vs E), ale použitím dobrej program, ktorý bol 1.6x rýchlejší než pole množín (C vs F). Ak sme zároveň použili reserve na veľkosť \(4*n^{1.5}\), slovník dvojíc bol dokonca 2.2x rýchlejší než pole množín (D vs G)!

Toto vieme posunúť ešte o krok ďalej. Prístup do std::vector aj do std::unordered_set je v čase \(O(1)\), ale líšia sa v konštantách. Chceli by sme teda, aby sme sa čo najčastejšie dostali k dátam cez prístup do poľa. Rozdelíme si dáta na malé a veľké šľapky do dvoch štruktúr. Jedna bude dvojrozmerné pole a druhá pole množín/množina dvojíc. Dáta pre malé šľapky, teda tie, ktoré sú veľkosťou menšie ako \(\sqrt{cn}\), vieme ukladať do poľa s rozmermi \(N \times \sqrt{cn}\). Dáta pre veľké šľapky (\(\sqrt{cn} < \text{veľkosť} \leq n\)) budeme ukladať do poľa množín/množiny dvojíc. Konštantu \(c\) si môžeme zvoliť tak, aby sme sa zmestili do pamäťového limitu, strávili primerane veľa času vytváraním štruktúr a zároveň sme mali čo najviac prístupov k dátam cez prístup do poľa. Podobným argumentom ako pri počítaní veľkosti relevantného grafu vieme ukázať, že takáto optimalizácia v najhoršom prípade zrýchli program o konštantný faktor. A naozaj nám to program zrýchli 3.4x (G vs H)!

Vstupy v tejto úlohe sú také malé, že môžeme použiť \(O(n^2)\) pamäťové riešenie a vôbec sa neobťažovať s množinami. Je ale dobre vedieť, že takéto optimalizácie existujú, lebo sa nám môžu hodiť na iných súťažiach. Keďže máme priestor na \(O(n^2)\) pamäte, môžeme si dovoliť pole booleanov alebo takzvanú bitovú množinu (std::bitset v C++). Kód bude nakoniec veľmi rýchly a veľmi jednoduchý.

Všimnime si, že std::bitset je 2x rýchlejší než std::vector<bool>, ten je 3x rýchlejšie než std::vector<char> a ten je zase približne 5x rýchlejší než std::vector<int>. Nie je to náhoda. Čím menej dát potrebujeme ukladať, tým viac sa nám ich zmestí do CPU Cache. Avšak pozor! Často sa stáva, že naopak std::vector<bool> je pomalší než std::vector<char> (detaily si vygooglite). Podobne sa viete hrať s nahrádzaním int za short/unsigned short, keďže \(n < 2^{16}\). Ak sa vám vhodne podarí zmestiť do CPU Cache, ucítite vietor vo vlasoch. Program H vieme tiež vylepšiť použitím std::bitset.

Bol by som zvedavý, aký najrýchlejší kód sa dá napísať. Ak si myslíte, že máte výbornú implementáciu, môžete sa mi pochváliť.

Možno ste si všimli, že som veľa krát spomenul, ako to môže byť v iných prípadoch s optimalizáciami celkom inak. Toto je skutočnosť, ktorú pozná každý kto sa kedy pokúšal žmýkať z programu všetku jeho rýchlosť. Slepá optimalizácia s veľkou pravdepodobnosťou nepovedie k 10x zrýchleniu. Ak chcete niečo optimalizovať, vygenerujte si reprezentatívny ťažký vstup a zmeny v kóde testujte na ňom.

Tabuľka pre vstupy veľkosti \(n=50\,000\):