V tomto vzoráku si ukážeme viacero všeobecných techník na riešenie úloh a optimalizovanie programov. Ak sa ich naučíte, pomôžu vám vyriešiť veľa rôznych problémov.

Najprv si ukážeme bruteforce riešenie. Ďalej bruteforce zoptimalizujeme pomocou memoizácie, prevedieme rekurziu na dynamické programovanie a ukážeme si, kedy použiť binárne vyhľadávanie. Takto získame riešenie so zložitosťou $$O(n^2 \log n)$$ hodné $$5/8$$ bodov s veľmi malou námahou.

Na záver ešte trošku porozmýšľame a dopracujeme sa k $$O(n \log n)$$ riešeniu, v ktorom zoptimalizujeme dynamické programovanie pomocou deque.

Riešenie hrubou silou

Ak neviete, kde začať alebo ak ste už unavení z úvodného uvažovania, vždy je dobré začať s naprogramovaním riešenia hrubou silou – najjednoduchšie naprogramovateľné, funkčné riešenie, čo nám napadne – väčšinou pomerne neefektívne. V našej úlohe takéto riešenie vyskúša pre každý lístok, či sa s ním dá cieľ dosiahnuť s čakaním menším ako $$t$$ a z vyhovujúcich lístkov vyberie ten najlacnejší.

Kostra programu by mohla vyzerať nasledovne:

n, t = map(int, input().split())
# Na začiatok polí pridáme nuly, aby sme mali zastávky očíslované od 1
cena  = [0, ]  + list(map(int, input().split()))
cakaj = [0, 0] + list(map(int, input().split()))

# Nejak spočítame, čí sa dá dostať z 1 na n s k-lístkom
def dasa(k):
   ...

odpoved = cena[-1]

for k in range(1, n):
    if cena[k] < odpoved and dasa(k):
        odpoved = cena[k]

print(odpoved)

Uvedomíme si, že zo zastávky s číslom $$x$$ sa nám nikdy neoplatí vrátiť späť (ísť na zastávku s menším číslom) a teda sa budeme hýbať len na zastávky $$x+1, x+2, \dots, x+k$$.

To, či s $$k$$-lístkom vieme dosiahnuť cieľ, vieme zistiť jednoduchou rekurziou. Ak sme na nejakej zastávke, to či sa dá odtiaľto dostať do cieľa zistíme tak, že sa skúsime pohnúť na ďalšiu a spýtame sa, či sa odtiaľto vieme dostať do cieľa v časovom limite. Musíme ale vyskúšať všetky susedné zastávky.

Funkcia $$f$$ ako parameter dostane číslo zastávky $$x$$, odkiaľ sa chceme dostať do cieľa a zvyšný čas, ktorý máme na čakanie $$t$$. Vyskúša všetkých $$k$$ pohybov na zastávky $$x+1, \dots, x+k$$ – zavolá $$f(x+1, t-t_x), \dots, f(x+k, t-t_x)$$ a vráti True ak sa dá do cieľa dostať z niektorej zo zastávok $$x+1, \dots, x+k$$. Inak fukcia vráti False.

def dasa(k):
    def f(x, t):
        if t < 0:
            return False
        if x >= n:
            return True
        for dalsi in range(x+1, x+k+1):
            if f(dalsi, t-cakaj[x]):
                return True
        return False

    # Z 1 na n sa dá dostať k-lístkom práve vtedy, ak
    return f(1, t) == True

Rekurzia vyskúša každú cestu zo zastávky 1 do $$n$$ najviac raz a ciest je najviac toľko, koľko je všetkých podmnožín čísel $$1, 2, \dots, n$$. Časovú zložitosť tohto riešenia vieme zhora odhadnúť ako $$O(n^3 \cdot 2^n)$$: Pre jeden z $$n$$ lístkov over $$2^n$$ ciest. Každá cesta má najviac $$n$$ zastávok (je potrebných najviac $$n$$ volaní) a každé volanie zbehne v čase $$O(k)$$.

Nepočítajme nič dvakrát 1 - Memoizácia

V predošlom riešení sa môže stať, že rekurzívnu funkciu voláme viackrát s tými istými parametrami. Počítame teda viackrát to isté. Tomuto sa môžeme vyhnúť, ak si budeme spočítané výsledky rekurzie pamätať. Ak potom zavoláme funkciu s tými istými parametrami, namiesto výpočtu sa len pozrieme do pamäte. Vypočítané výsledky si môžeme pamätať vo viacrozmernom poli (každý rozmer zodpovedá jednému parametru), alebo v mape, kde je kľúčom $$k$$-tica parametrov.

def dasa(k):
    memo = {}

    def f(x, t):
        if t < 0:
            return False
        if x >= n:
            return True
        if (x, t) in memo:
            return memo[(x, t)]

        for dalsi in range(x+1, x+k+1):
            if f(dalsi, t-cakaj[x]):
                memo[(x, t)] = True
                return True

        memo[(x, t)] = False
        return False

    return f(1, t) == True

Pre každý z $$n$$ lístkov je počet rôznych volaní funkcie (rôznych dvojíc parametrov (zastávka, čas)) najviac $$n \cdot t$$. Každé volanie trvá najviac $$O(k)$$ času. Pre jeden lístok zistíme $$dasa(k)$$ v čase $$O(n \cdot t \cdot k)$$ a teda celý náš program bude mať čas behu zhora ohraničený $$O(n^3 \cdot t)$$.

Použitie memoizácie si môžete pozrieť aj v riešení úlohy z minulej série Optimálna šifrovačka.

Nepočítajme nič dvakrát 2

Napriek tomu, že pre každú dvojicu parametrov voláme rekurziu len raz, ak máme spočítaný výsledok pre nejaké parametre, môžeme už vedieť výsledok pre iné: Ak vieme, že cestu stihneme so zvyšným časom $$47$$, cestu určite stihneme aj s hocijakým väčším zvyšným časom. Stačí nám teda zapamätať si ten najmenší čas, s ktorým sa vieme dostať do cieľa z $$x$$. Rôznych volaní funkcie $$f$$ tak už nebude $$n \cdot t$$ ale len $$n$$.

Namiesto toho, aby sme pre dvojicu (zastávka $$x$$, čas $$t$$) počítali, len či sa dá dosiahnuť cieľ (true/false), budeme pre zastávku $$x$$ počítať, aký je najmenší čas potrebný na dosiahnutie cieľa, keď začneme v $$x$$. Toto opäť vieme rátať podobnou rekurziou ako vyššie – pozrieme sa na najbližšie zastávky, pre ne rekurzívne spočítame hodnoty $$f(x+1), f(x+2), \dots, f(x+k)$$ a vyberieme si, kam sa chceme pohnúť – na zastávku, odkiaľ sa najskôr dostaneme do cieľa. Teda $$f(x) = \min{f(x+1), f(x+2), \dots, f(x+k)} + t_x$$ a $$f(n) = 0$$

def dasa(k):
    memo = {}

    def f(x):
        if x >= n:
            return 0
        if x in memo:
            return memo[x]
        memo[x] = min( f(dalsi) for dalsi in range(x+1, x+k+1) ) + cakaj[x]
        return memo[x]

    # Z 1 na n sa dá dostať k-lístkom práve vtedy, ak
    return f(1) <= t

Jedno volanie stále zbehne v čase $$O(k)$$, ale rôznych vstupov funkcie $$f$$ je len $$O(n)$$. Výpočet pre jedno $$k$$ teda trvá $$O(n \cdot k)$$, a vďaka tomu bude celková zložitosť programu $$O(n^3)$$.

Nepočítajme nič zbytočne - Binárne vyhľadávanie

Skúsme teraz zoptimalizovať inú časť programu – skúšanie všetkých lístkov. Pri tejto úlohe je dobré si uvedomiť, že rôzne ceny lístkov sú tu hlavne na zmätenie. To podstatné je zistiť minimálne $$k$$ také, že vieme trasu prejsť s čakaním menším ako $$t$$. Ak máme minimálne $$k$$, na výpočet výsledku stačí nájsť najmenšiu cenu z $$c_k, c_{k+1}, \dots, c_n$$.

Ak už totiž vieme, že sa dá trasa prejsť s $$k$$-lístkom, určite sa bude dať prejsť aj s $$k+1$$-lístkom a s hocijakým lístkom s väčším dosahom. Ak sa trasa nedá prejsť s $$k$$-lístkom, nebude sa dať prejsť so žiadnym lístkom s menším dosahom. Výsledky funkcie $$dasa(k)$$ budú teda s rastúcim $$k$$ najskôr len False a od istej hranice budú len True.

Vieme sa teda pozrieť najskôr na $$dasa(n/2)$$, ak je to False, $$k > n/2$$, inak $$k \leq n/2$$. Vylúčili sme polovicu možností a pokračujeme pýtaním sa na $$dasa(n/4)$$ alebo $$dasa(3n/4)$$ … Po približne $$\log_2 n$$ krokoch nám zostane jediná možnosť.

Binárne vyhľadávanie sa dá využiť vždy, keď hľadáme hodnotu v monotónnej postupnosti (nerastúcej alebo neklesajúcej). Vieme hľadať najľavejší výskyt aj najpravejší výskyt hodnoty. Špeciálnym prípadom sú funkcie ako $$dasa()$$, kde sú hodnoty False/True, alebo 0/1.

def najmensie_k():
    l = 0      # este sa to neda stihnut
    r = n-1    # s takymto dosahom sa to stiha

    while r - l > 1:
        piv = (l + r) // 2    # prvok v strede intervalu (l, r>
        if not dasa(piv):
            l = piv
        else:
            r = piv
    return r

print(min(cena[k] for k in range(najmensie_k(), n)))

Chuťovka: Pre vyhnutie sa chybám v kóde binárneho vyhľadávania môže byť vhodné použiť binárne vyhľadávanie štandardnej knižnice jazyka. V pythone sa dá dokonca zneužiť aj pre náš účel.

from bisect import bisect_left

def najmensie_k():
    class vyhladavatko:
        def __getitem__(self, key):
            return dasa(key)

    return bisect_left(vyhladavatko(), True, 1, n)

V našej úlohe teda $$(\log n)$$-krát zavoláme funkciu $$dasa()$$ a dosiahneme čas $$O(n^2 \log n)$$.

Toto riešenie nám umožní dosiahnuť $$5/8$$ bodov (riešenie v C++ určite, s týmto pythonovským kódom 4) a ani sme nemuseli veľa rozmýšľať (pokiaľ poznáte tieto všeobecné techniky, všetky predošlé úvahy dokopy vám zaberú len niekoľko minút).

Dynamické programovanie

Vráťme sa naspäť k optimalizovaniu našej rekurzívnej funkcie $$f(x)$$ – najmenší potrebný čas na dosiahnutie cieľa zo zastávky $$x$$. Na vypočítanie $$f(x)$$ sme potrebovali mať spočítané hodnoty $$f(x+1), f(x+2), \dots, f(x+k)$$, a na ich spočítanie sme potrebovali mať vypočítané hodnoty až po $$f(x + k + k)$$, atď. Od začiatku ale vieme, že $$f(n) = 0$$. Na spočítanie $$f(n-1)$$ potrebujeme len $$f(n)$$, na spočítanie $$f(n-2)$$ len $$f(n-1), f(n)$$, atď.

Hodnoty $$f(x)$$ teda nemusíme počítať v rekurzívnej funkcii, ale stačí použiť jednoduché cykly. Vytvoríme si pole $$f[]$$, kde $$f[x]$$ označuje minimálny čas potrebný na dosiahnutie cieľa zo zastávky $$x$$. $$f[n] = 0$$ Pre znižujúce sa $$x$$ postupne spočítame $$f[x] = \min{f[x+1], f[x+2], \dots, f[x+k]} + t_x$$, teda presne to isté, čo počítala rekurzívna $$f$$.

Toto spôsobí len konštantné zrýchlenie programu, ale povedie nás to k optimálnemu riešeniu. V niektorých prípadoch dokážeme pomocou dynamického programovania aj znížiť pamäťovú zložitosť programu.

def dasa(k):
    # pole velkosti n+k je praktickejsie, nemusime specialne osetrovat pripad: dalsi > n
    f = [0] * (n+k)
    for x in range(n-1, 0, -1):
        f[x] = min( f[dalsi] for dalsi in range(x+1, x+k+1)) + cakaj[x]
    return f[1] <= t

Nepočítajme nič dvakrát, časť tretia

Ešte stále sa opakujeme? Áno: $$ f[x] = \min{f[x+1], f[x+2], f[x+3], \dots, f[x+k]} + t_x$$ $$ f[x+1] = \min{f[x+2], f[x+3], \dots, f[x+k], f[x+k+1]} + t_{x+1}$$

Ak už vieme minimum pre $$x+1, \dots, x+k$$, minimum pre $$x+2, \dots, x+k+1$$ by sme mohli vedieť spočítať rýchlejšie. Totiž, ak je minimom jedno z čísel $$f[x+2], f[x+3], \dots, f[x+k]$$, tak $$ \min{f[x+2], \dots, f[x+k+1]} = \min{\min{f[x+1],\dots, f[x+k]}, f[x+k+1]}$$ a teda na spočítanie nového minima by nám stačilo jedno porovnanie (s $$f[x+k+1]$$).

Jediný nepríjemný prípad je, ak je $$\min{f[x+1], \dots, f[x+k]} = f[x+1]$$. Vtedy by sme potrebovali vedieť, aký bol druhý najmenší prvok z $$f[x+1] \dots, f[x+k]$$

Budeme postupovať sprava doľava, tak ako doteraz a počítať hodnoty $$f[x]$$ – minimálny čas potrebný na presun z $$x$$ do cieľa aj s časom čakania $$t_x$$. Chceli by sme si pamätať niekoľko zastávok, ktoré sa môžu niekedy stať minimom a vedieť tieto hodnoty aktualizovať pre $$f[x-1]$$.

Budeme si udržovať pozície zastávok, na ktorých je závislá hodnota $$f[x]$$, teda niektoré z $$x+1, \dots, x+k$$ a pamätať si ich budeme usporiadané podľa ich hodnôt $$f$$ v štruktúre deque – obojsmerný spájaný zoznam. Vieme z neho vyberať a vkladať do neho prvky z oboch strán. Nech sú naľavo tie zastávky, ktoré majú najmenšie $$f$$, teda tie, z ktorých sa najrýchlejšie dostaneme do cieľa.

Na začiatku algoritmu sme na zastávke $$n-1$$, v deque si pamätáme zastávku $$n, f[n] = 0$$.

Novú hodnotu $$f[x]$$ spočítame vždy jednoducho, ako minimálny čas, potrebný na cestu do cieľa z jednej z k zastávok napravo od $$x$$ a čas čakania na $$x$$, čo je $$f[deque.left] + t_x$$.

Po výpočte $$f[x]$$ musíme deque aktualizovať. Chceme do nej niekam vložiť zastávku $$x$$ (lebo hodnota $$f[x]$$ bude potrebná pre zastávky naľavo od $$x$$). Keďže žiadnu zastávku, ktorú máme v deque nebudeme vo výpočtoch používať dlhšie ako $$x$$, môžeme z deque vyhodiť všetky zastávky, ktoré potrebujú väčší čas na dosiahnutie cieľa – žiadna z týchto zastávok by sa už totiž nemohla stať novým minimom. Takisto zastávky, ktoré sú ďalej ako $$k$$ od $$x$$ už nikdy nepoužijeme a potrebujeme ich odstrániť z konca aj zo začiatku deque.

Vyhodíme tak všetky nepotrebné zastávky z konca a zo začiatku a nakoniec vložíme $$x$$.

from collections import deque

def dasa(k):
    f = [0] * (n+1)
    mozne_mini = deque([n])

    for x in range(n-1, 0, -1):
        f[x] = f[mozne_mini[0]] + cakaj[x]

        # odstranime zastavky z konca, ktore nikdy nebudu minimom
        while len(mozne_mini) > 0 and (f[mozne_mini[-1]] > f[x] or mozne_mini[-1] - (x-1) > k):
            mozne_mini.pop()
        # odstranime zastavky zo zaciatku, ktore nikdy nebudu minimom
        while len(mozne_mini) > 0 and mozne_mini[0] - (x-1) > k:
            mozne_mini.popleft()
        # pridame nove potencialne minimum
        mozne_mini.append(x)

    return f[1] <= t

V tomto riešení každú zastávku najviac raz vložíme do deque a najviac raz ju vyberieme. Preto bude mať funkcia $$dasa(k)$$ časovú zložitosť $$O(n)$$. Ak použijeme binárne vyhľadávanie na nájdenie najmenšieho $$k$$, celý program potrebuje len čas $$O(n \log n)$$.