Úloha 1 (Šéf agentů): Podařilo se vám sehnat schéma sítě tajných agentů. Má podobu orientovaného grafu, jehož vrcholy jsou agenti a hrana popisuje, že jeden agent velí druhému. Kdykoliv agent obdrží rozkaz, předá ho všem agentům, kterým velí. Šéfem sítě je libovolný agent, který vydá-li rozkaz, dostanou ho časem všichni ostatní agenti. Vymyslete algoritmus, jež najde šéfa sítě. Umíte najít všechny šéfy? [Průvodce 5.11]

Úloha 2 (Mafiáni*): Mapa městečka ve tvaru stromu, v některých vrcholech bydlí mafiáni. Chceme do vrcholů rozestavět co nejméně strážníků tak, aby se mafiáni nemohli nepozorovaně domlouvat, tedy aby mezi každými dvěma mafiány stál aspoň jeden strážník. Postavíme-li strážníka do vrcholu s mafiánem, zabráníme mu v kontaktu se všemi ostatními mafiány. [Průvodce 5.11]

Úloha 3 (Mýto): Silnice v mapě máme ohodnocené dvěma čísly: délkou a mýtem (poplatkem za projetí). Jak najít nejlevnější z nejkratších cest? [Průvodce 6.6]

Úloha 4 (Bežkař*): Pomalu roztává sníh a Kevin se potřebuje dostat ze Šumavy na autobus. Mapu Šumavy si můžeme představit jako neorientovaný graf, kde pro každou hranu známe počet minut, jak dlouho ji trvá přejít pěšky a jak dlouho přejet na běžkách. Nandat nebo sundat běžky lze jen ve vrcholu a trvá to $K$ minut. Kevin nyní stojí ve vrcholu $s$ a chtěl by se dostat do autobusové zastávky ve vrcholu $c$. Jak dlouho mu to bude trvat? [KSP 34-1-1]

Úloha 5 (Okénkový medián): Na vstupu postupně přicházejí čísla. Kdykoliv přijde další, vypište medián z posledních $k$ čísel (to je číslo, které by bylo prostřední, kdybychom $k$-tici setřídili). Dosáhněte časové složitosti $\O(\log k)$ na operaci. [Průvodce 8.5]

Úloha 6 (Množiny*): Vybudujte datovou strukturu udržující skupinu množin podporující následující operace:

• Přidání jednoprvkové množiny
• Zjištění, zdali je prvek ve množině
• Sjednocení dvou množin (s původními množinami už se dále nebude pracovat)

Kolik času potřebujete pro zpracování $Q$ operací?

Úloha 7 (Medián): Mějme dvě (ne nutně stejně dlouhé) vzestupně seřazené posloupnosti. Najděte medián jejich sjednocení v sublineárním čase. [Průvodce 10.8]

Úloha 8 (Šrouby a matičky*): Na stole leží $n$ různých šroubků a $n$ matiček. Každá matička pasuje na právě jeden šroub a my chceme zjistit, která na který. Umíme ale pouze porovnávat šroub s matičkou – tím získáme jeden ze tří možných výsledků: matička je příliš velká, příliš malá, nebo správně velká. Jak to udělat efektivně? [Průvodce 10.9]

Úloha 9 (Hra**): Alice a Bob hrají hru na orientovaném acyklickém grafu. Na začátku se položí žeton do vrcholu $s$. Poté se Alice a Bob střídají v posouvání žetonu po hranách grafu. Bob vyhraje, když se žeton dostane do červeného vrcholu. Alice vyhraje, když z aktuálního vrcholu nevedou hrany. Na začátku jsou všechny vrcholy modré. Zpracovávejte dva druhy dotazů: - Obarvi vrchol $v$ červeně. - Kdo vyhraje, pokud hra začne ve vrcholu $s$? [Codeforces 2137G]