7. Odolateľná reklama vzorové riešenie

6 9
1 42 9 2 54
5 6 5 4

2

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)\).