První série třicátého čtvrtého ročníku KSP

Řešení úloh


Praktická opendata úloha34-1-1 Běžkař (Zadání)


Úlohu budeme řešit pomocí prohledávání stavového prostoru. Všimněme si, že stavů, ve kterých se Kevin může nacházet, není příliš mnoho. Stavy se mohou lišit pouze tím, v jakém vrcholu se Kevin nachází a zda má nasazené běžky.

Sestrojíme si graf, kde vrcholy budou možné stavy a hrana povede mezi dvěma vrcholy právě tehdy, když se dá mezi danými stavy přímo přejít. Ohodnocení hrany bude čas, za jaký je Kevin schopen se mezi stavy přesunout.

Speciálně to znamená:

Nyní uvažme, jak velký je náš graf. Počet vrcholů odpovídá počtu stavů, což je 2n, tedy O(n). Počet hran je n + 2m, tedy O(n + m).

V tomto grafu nyní hledáme nejrychlejší způsob, jak se dostat ze startu do cíle. Jinými slovy hledáme nejkratší cestu v ohodnoceném grafu (s nezápornými ohodnoceními). Tu můžeme nalézt pomocí Dijkstrova algoritmu s haldou, který nám seběhne v čase O((n + m) log n). To lze teoreticky ještě zrychlit použitím Fibonacciho haldy, v praxi to ale není kvůli konstantě témeř žádný rozdíl a pro vyřešení úlohy to nebylo potřeba.

Úlohu připravili: Filip Hejsek, Ondra Sladký

Teoretická úloha34-1-2 Líný student (Zadání)


Pojďme se zaměřit na první přednášku, kterou bude mít Vašek ve svém rozvrhu. Aby si nemohl přidat žádnou přednášku ještě před ni, tak jeho první přednáška musí začínat dříve, než nějaká jiná končí. Možností pro výběr první přednášky je ovšem více, kterou si má vybrat?

Když si nějakou vybere, tak si ze seznamu přednášek může odmyslet všechny, které s ní mají nějaký překryv. Už totiž nemůže žádnou z nich přidat do rozvrhu a tedy mu ani žádná z nich nemůže být vnucena. V uvažovaných přednáškách tak zůstanou jenom přednášky začínající po konci té vybrané. Všimněme si, že zbývající přednášky zase tvoří zadání naší úlohy. Chceme z nich totiž vybrat co nejméně nepřekrývajících se přednášek tak, aby žádnou další do výběru již nešlo přidat.

Všimneme si, že když si setřídíme přednášky podle času jejich začátku, tak si při každém výběru první přednášky odmyslíme nějaký začátek tohoto seznamu. Zbudou nám jenom přednášky, které začínají po konci vybrané přednášky.

Uvažujme i nadále setříděný seznam přednášek podle času jejich začátku. Částem seznamu od nějaké přednášky dále budeme říkat sufixy přednášek. V případě, že už budeme mít vyřešenou naši úlohu pro všechny sufixy přednášek (kromě toho obsahující všechny přednášky), tak již není problém vyřešit i celý seznam přednášek. Podíváme se na všechny možnosti, jakou přednášku vybrat jako první. Pro každou z nich zjistíme, kolik dalších přednášek bychom museli vybrat, a vybereme si optimální možnost.

Při rozhodování, kterou přednášku vybrat, tedy potřebujume mít zpracované všechny sufixy od této přednášky dále. Můžeme tedy začít tak, že si nejprve vyřešíme úlohu pouze pro poslední přednášku, a pak postupně řešíme delší a delší sufixy přednášek. Tomuto postupu se říká dynamické programování.

Popsaným algoritmem zjistíme, kolik předmětů si bude Vašek muset zapsat, ovšem zatím nevíme, které to jsou. Pro každý sufix přednášek si ještě kromě minimálního počtu zapamatujeme, na kterou přednášku má Vašek v daném sufixu jít jako první. Pomocí toho pak zvládneme postavit celé řešení. Vždy se podíváme, na kterou přednášku má zajít, a dále se podíváme na sufix přednášek po jejím konci. Toto opakujeme, dokud nezmizí všechny přednášky.

Popsané řešení je ovšem vcelku pomalé. Pro každou část seznamu totiž prochází všechny přednášky, kterými může začít, a pro každou z nich hledáme odpovídající zbylý sufix. Celková časová složitost je tedy O(N3). Pojďme ho zrychlit!

K přednáškám si poznačíme, jaký sufix přednášek po jejich vybrání zbude, abychom jej nemuseli pokaždé hledat. To můžeme pro každou přednášku zjistit pomocí jednoho binárního vyhledávání – najdeme první přednášku začínající po jejím konci.

V průběhu počítání sufixů si můžeme pamatovat, kdy nejdříve končí některá z přednášek v sufixu. Při rozšíření sufixu tuto hodnotu zvládneme jednoduše přepočítat.

Nyní zbývá pouze výběr optimální přednášky. Víme, že přednášky, které můžeme pro daný sufix vybrat jako první, tvoří v setříděném seznamu nějaký souvislý interval – musí ležet v uvažovaném sufixu a musí začínat před prvním koncem přednášky ze sufixu. Nabízí se tedy použít intervalový strom na hledání minima postavený nad posloupností přednášek. Hodnota přednášky bude říkat, jakého počtu přednášek umíme dosáhnout jejím vybráním.

Ovšem musíme si rozmyslet, jak onen intervalový strom vzniká. Na začátku totiž ještě neznáme hodnoty v něm, ty zjišťujeme až průběžně. Naštěstí hodnoty do intervalového stromu přidáme před tím, než je budeme potřebovat. Chceme-li přidat přednášku, podíváme se na sufix začínající po jejím konci. Ten už máme zpracovaný, položíme tedy intervalový dotaz a tím zjistíme hodnotu přidávané přednášky.

Celková časová složitost bude díky použití binárního vyhledávání a intervalového stromu O(N log N). Paměťová složitost bude O(N).


Praktická opendata úloha34-1-3 Pilný student (Zadání)


Na začátek si ujasněme, že Filip je doopravdy pilný student, a protože se snaží maximalizovat počet bodů za splněné úkoly, udělá úkol vždy, když může – tedy nemá mezi plněním úkolů zbytečné mezery.

Teď se pojďme zamyslet nad tím, co nám o možnosti splnění úkolu prozradí jeho deadline. K tomu se nám bude hodit informace o celkovém počtu úkolů. Kdykoliv máme úkol, jehož deadline je větší než celkový počet úkolů N, víme, že tento úkol určitě stihne vypracovat. I kdyby totiž splnil všechny úkoly kromě tohoto úkolu, zabere mu jejich plnění maximálně N - 1 dní. Na tento úkol mu tedy vždy alespoň jeden volný den zůstane.

Dále si pojďme rozmyslet, jaké úkoly může Filip v jeden konkrétní den D splnit. Vždy se jedná o úkoly s deadlinem, který je větší nebo roven D. Na počátku si můžeme k vypracování vybrat libovolný úkol, ale postupem času se počet nesplněných úkolů zmenšuje (protože postupně propadají). Uvědomme si, že je nám u každého úkolu v podstatě jedno, kdy ho Filip splní, pouze nás zajímá, zda ho splní. Tudíž úkoly s delším deadlinem chceme plnit co nejpozději, abychom měli případně čas dělat úkoly s kratším deadlinem. Z toho vyplývá, že chceme při rozvrhování postupovat od konce.

Jako poslední chceme plnit úkoly s deadlinem větším než N. Všimněme si, že nám nevadí plnit ostatní úkoly dříve, neboť dní na to máme dost (jak jsme zmínili ve druhém odstavci). Následně budeme rozvrhovat odzadu – vždy se podíváme na úkoly s deadlinem daný den a nerozvržené úkoly s pozdějším deadlinem, protože to jsou ty, které může Filip ještě splnit. Z nich vybereme úkol s nejvyšším bodovým ziskem a rozvrhneme ho. Pro výběr úkolu s nejvyšším bodovým ziskem můžeme použít maximovou haldu. Následně se podíváme na předchozí den a opakujeme postup (do haldy přidáme nové úkoly a vybereme z ní maximum).

V průběhu algoritmu do haldy každý úkol nejvýše jednou přidáme a nejvýše jednou ho z ní odebereme. Přidání/odebrání prvku z/do haldy umíme realizovat v čase O(log N). Celková časová složitost je tedy O(N log N). Paměťová složitost je lineární vzhledem k N.


Teoretická úloha34-1-4 Sjezdař (Zadání)


Omlouváme se, řešení ještě není hotové, ale bude vydané později na stránkách.


Teoretická úloha34-1-X1 Rostoucí strom (teoretická) (Zadání)


Pojďme se nejprve zamyslet nad statickou verzí úlohy. V ní nejdříve přijdou všechny požadavky na přidání vrcholu, a až po nich začnou přicházet dotazy na vzdálenost a požadavky na prodloužení. Tedy se na začátku postaví strom a až pak se s ním pracuje. Po dostavění stromu si můžeme vybudovat nějakou datovou strukturu a pak ji jenom updatovat a ptát se na vzdálenosti vrcholů od kořene. K tomu lze využít například heavy-light dekompozice ze seriálu o stromech.

My si zde ovšem ukážeme jiné řešení, které pak zobecníme i na strom, kde přibývají vrcholy. Na postaveném stromu si pustíme průchod do hloubky. Budeme tvořit posloupnost vrcholů. Když do vrcholu přijdeme nebo z něj odejdeme zpět ke kořeni, přidáme ho do posloupnosti. Na začátek a konec posloupnosti ještě přidáme kořen. Každý vrchol tedy bude v posloupnosti právě dvakrát. U každého vrcholu si budeme pamatovat dva indexy, kde v posloupnosti se vyskytuje.

Posloupnost vrcholů

K prvnímu výskytu vrcholu v posloupnosti připíšeme délku hrany, která do něj vede. K druhému výskytu pak připíšeme opačnou hodnotu. (Pro kořen můžeme uvést dvě nuly.) Pro zjištění vzdálenosti vrcholu od kořene pak stačí sečíst prefix posloupnosti po první výskyt požadovaného vrcholu. Všimneme si, že každá hrana na cestě mezi kořenem a vrcholem je do součtu přičtena. Ovšem každá jiná hrana je buď již přičtená a odečtená, anebo v prefixu vůbec není.

Můžeme si tedy postavit intervalový strom. Pro prodloužení hrany provedeme dva updaty intervaláče a pro dotazy na vzdálenost odpovíme součtem intervalu (prefixu).

Statickou verzi tedy zvládneme řešit v čase O(N log N), kde N je délka vstupu.

Pojďme nyní přejít na dynamickou verzi. Navíc tedy dovolíme mezi dotazy a prodlouženími hran zadávat požadavky na přidání nové hrany a vrcholu.

To v našem případě znamená přidat do posloupnosti dva nové odkazy na vrchol. Nahlédneme, že stačí přidat oba dva záznamy o novém vrcholu těsně za první výskyt jeho předka.

Ovšem do intervalového stromu nelze přidávat další prvky efektivně. Proto intervalový strom budeme muset nahradit za něco chytřejšího. Posloupnost vrcholů tedy budeme reprezentovat pomocí vyvažovaného stromu. Například pomocí treapu nebo třeba splay stromu. Do takto reprezentované posloupnosti umíme přidávat další prvky, updatovat jejich hodnoty a dokonce sčítat hodnoty na intervalu. To vše v čase lineárním k hloubce stromu. Pro vhodnou implementaci stromů tedy v logaritmickém čase k velikosti stromu.

Celková časová složitost je tedy O(N log N), kde N je délka vstupu.

Úlohu připravil: Jirka Kalvoda

Praktická opendata úloha34-1-X2 Rostoucí strom (praktická) (Zadání)


* * *

Vzorové řešení seriálu před koncem celého ročníku KSP obdrží jen ti, kdo už seriál odevzdali.