První série začátečnické kategorie třicátého pátého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
35-Z1-1 Slovíčka (Zadání)
První a jasný krok je si slovíčka setřídit. Přímočaré (a pomalé) řešení pak při každém dotazu prochází všechna slovíčka, dokud nenajde první hledané slovo. Odtud si počítá, kolik slovíček najde v meziprostoru, než dorazí ke druhému hledanému slovu. Takový postup má časovou složitost O(N log N + QN), protože O(N log N) spotřebujeme na setřídění slovíček a O(N) na každý dotaz.
Už na první pohled se ale postup při dotazu nezdá optimální; tak přece nevyhledáváme slovíčka ani ručně ve fyzickém slovníku. Nabízí se využít binární vyhledávání, což je postup, jak rychle hledat v setříděných posloupnostech. Půjdeme na to takto: podíváme se doprostřed slovníku. Pokud jsme tam hledané slovo našli, skvělé. Pokud ne, tak musí být v abecedě před nebo po slovu uprostřed. Pokud je před ním, pak už nedává smysl ho hledat za prostředkem a můžeme stejný postup opakovat na první polovině naší posloupnosti. Pokud je po něm, tak můžeme postup opět opakovat v druhé polovině.
Jakou to má časovou složitost? V každém kroku se nám velikost prohledávané části slovníku zmenší o polovinu, takže po čase O(log N) najdeme pozici našeho hledaného prvku. V našem případě tedy najdeme dvě slova v čase O(log N) a pak jen vypíšeme rozdíl jejich pozic minus jedna. Celková složitost bude O(N log N + Q log N).
Pokud by vás binární vyhledávání zajímalo hlouběji, nahlédněte do kuchařky o binárním vyhledávání.
Úlohu lze řešit ještě jedním způsobem, který se v Pythonu snáz programuje. Celý slovník si setřídíme a přidáme do hešovací tabulky tak, aby klíče byla jednotlivá slova a hodnoty byly jejich pozice v setříděném pořadí. Při dotazu se jen zeptáme na pozice prvního a druhého slova a spočítáme rozdíl (a od rozdílu odečteme jedničku). Dotazy mají průměrnou časovou složitost O(1), strávíme na nich tedy celkově v průměru O(Q) místo O(Q log N).
35-Z1-2 Kanón na vrabce (Zadání)
Pro chvíli si představme, že bychom úlohu řešili jen v řádcích a sloupcích namísto v diagonálách. To bychom si nejdříve kanóny setřídili primárně podle první souřadnice a sekundárně podle druhé a pak jen procházeli řádky. Pokud bychom na řádku našli více než jeden kanón, první dvojici bychom vypsali a skončili bychom. Pro kontrolu ohrožení ve sloupcích bychom prohodili souřadnice a postup zopakovali.
Podobný postup bychom rádi použili; chtěli bychom pro každý kanón vědět, do jaké patří diagonály (jako analogie řádku) a kolikátý v pořadí tam je. Jakmile budeme mít kanóny takto seřazené, je hledání ohrožujících se dvojic stejně jednoduché jako v případě sloupců a řádků. Podle čeho je ale setřídit?
Kanóny primárně seřadíme podle rozdílu x - y (čímž rozdělíme kanóny mezi diagonály o rovnicích y = x + k, všimněte si, že vlastně řadíme podle -k), a sekundárně podle souřadnice y (ta nám určí pořadí v rámci jedné diagonály). Po seřazení kanóny postupně projdeme a pokud narazíme na více než jeden v diagonále, první dva sousedy vypíšeme a skončíme. Pokud jsme žádnou dvojici nenašli, tak kanóny seřadíme primárně podle x + y a sekundárně podle y. Tím naopak dostaneme diagonály o rovnici y = -x + k a postup zopakujeme, abychom dostali i kanóny ohrožující se ve druhém směru.
Jak dlouho nám to bude trvat? Tříděním podle souřadnic strávíme O(N log N) a průchodem všech kanónů O(N). Celkově nám to tedy bude trvat O(N log N). Prostorová složitost je lineární, jelikož si pamatujeme pouze souřadnice všech kanónů.
35-Z1-3 Plánování schůzky (Zadání)
Pomalé řešení úlohy můžeme získat snadno. Pro každý možný den projdeme všechny organizátory a spočteme, kolik z nich v daný den může. Jenže takové řešení na plný počet bodů nestačí, chtěli bychom nějaké, které nebude muset pro každý den procházet všechny organizátory.
Zamyslíme se nad tím, kolik organizátorů může v nějaký den x+1, pokud už jsme zjistili počet dostupných organizátorů pro den x. To je počet organizátorů, kteří mohli v den x mínus počet organizátorů, kteří v x přestanou moct, plus počet těch, kteří ode dne x+1 mohou.
Jenže každý organizátor začne moci jen jednou a přestane mít čas také jen jednou. Můžeme si tedy ze začátku vytvořit kalendář událostí – pro každého organizátora do kalendáře napíšeme dvě události: v tento den jeden organizátor začíná a v tento jiný den jeden organizátor končí a tento kalendář seřadit podle dnů.
Nyní stačí projít všechny dny, podívat se na události daného dne a přepočítat počet dostupných organizátorů. Tento přístup má stále jeden problém – stále procházíme všechny dny. Toho se ale lze snadno zbavit – pokud v daný den není žádná událost, pak se počet organizátorů nezmění. To ale znamená, že tento den nemusíme řešit – i pokud by daný den mohlo nejvíce organizátorů, stejně tomu bude i den předtím. My máme vypsat první z nejvhodnějších dnů, který určitě zpracujeme, neboť ten den alespoň jeden organizátor začíná.
Díky tomuto pozorování tak stačí skákat po událostech, udržovat si průběžný aktuální počet organizátorů a kdykoliv se mezi událostmi mění den, aktualizovat průběžné maximum.
Dá se využít ještě jeden trik – při průchodu vůbec nemusíme kontrolovat, zda se mění den, stačí nejprve pro daný den zpracovat příbytky (představme si, že mohou od rána) a poté až úbytky (mohou až do večera).
Nejpomalejší je třídění, průchody na začátku a na konci již trvají lineární čas. Celková časová složitost je tak O(N log N). Paměťová složitost je rovněž lineární, neboť událostí, které si pamatujeme, je jen 2N.
35-Z1-4 Šetření na hlídačích (Zadání)
Mohli bychom zkoušet horní limit hledat po jedné, nicméně to by trvalo dlouho. Zkoušeli bychom totiž každý možný počet hlídačů až do N, tedy časová složitost by byla O(N).
Když přičítání konstanty nepomůže, pojďme násobit. Na začátku nastavíme horní limit H na 1, a pokaždé, když zjistíme, že počet použitých hlídačů je moc malý, zdvojnásobíme H. Až zjistíme, že naše H je příliš velké, pro hledané číslo N bude platit H / 2 < N < H. Potom si pomůžeme známým binárním vyhledáváním.
A kolik takto uděláme dotazů? Představme si konkrétní N. Protože H vždy dvojnásobíme, tak se zastavíme na H nejvýše dvakrát větším než N. Počet dotazů bude takové d, pro které platí H = 2d. Z toho úpravou získáme, že d je log H ≤ log(2N) = 1+ log N ∈ O(log N). Binární vyhledávání půlí interval, takže též bude trvat O(log N). Celkem tedy O(log N).