Třetí série začátečnické kategorie třicátého osmého ročníku KSP
Celý leták v PDF.
Řešení úloh
- 38-Z3-1: Osobní pokladna
- 38-Z3-2: Největší dort
- 38-Z3-3: Polární express
- 38-Z3-4: Nákup v poslední chvíli
38-Z3-1 Osobní pokladna (Zadání)
Zadání po nás chce vyhodnotit výraz zapsaný v notaci, kde jsou operátory psány za operandy místo mezi operandy, jak bychom mohli být zvyklí. Této notaci se běžně říká postfixová notace nebo RPN (Reverse Polish notation), ale to pro vyřešení úlohy vědět nepotřebujeme, zadání totiž popisuje i to, jakým způsobem se operátory vlastně vyhodnocují; hladově zleva.
Jinými slovy: budeme procházet vstup a když narazíme na operand (tedy číslo), někam si ho uložíme. Pokud narazíme na operátor, potřebujeme znát poslední dvě čísla, s nimi operaci provést a výsledek (tedy opět číslo) si zase uložit. Máme slíbeno, že se po nás nebude chtít dělit nulou a že na konci nám zbyde právě jedno číslo, které je výsledkem a o takové chybové stavy se tedy nemusíme starat.
Zbývá vymyslet jak uložit čísla tak, abychom měli jednoduchý přístup k těm, která jsme
uložili jako poslední. K tomu se nabízí použít zásobník, který přesně toto splňuje – při odebrání
prvku dostaneme ten nejpozději přidaný. V Pythonu k tomu můžeme použít obyčejný seznam a metodu
.append() pro přidání prvku a .pop() pro odebrání prvku.
Na konec je ještě dobré rozmyslet si pořadí operandů. 2 3 - totiž znamená 2 - 3
v běžné notaci. Do zásobníku bychom tedy vložili postupně 2 a 3 a při odebrání
ze zásobníku bychom dostali nejdříve 3; první odebraný prvek ze zásobníku je tedy druhým
operandem a výsledek je -1 (a ne 1 při popleteném pořadí).
A jak to bude rychlé? Celý vstup projdeme jednou a na každém operátoru nebo operandu strávíme konstantně času, výsledná složitost je tedy O(n), kde n je délka vstupu.
38-Z3-2 Největší dort (Zadání)
Na vstupu máme K bodů a hledáme mezi nimi čtyři takové, že tvoří obdélník rovnoběžný s osami s co největším obsahem. Jinými slovy, hledáme čtveřici bodů tvaru (x1, y1), (x1, y2), (x2, y1), (x2, y2) a zajímá nás, jakou největší hodnotu výrazu |x1 - x2| ·|y1 - y2| můžeme dosáhnout.
Nejjednodušší řešení je pomocí čtyř vnořených for-cyklů vyzkoušet všechny možné čtveřice bodů. Pro každou čtveřici zjistíme, zda tvoří rohy obdélníka, a pokud ano, spočítáme jeho obsah. Během algoritmu si budeme udržovat obdélník s doposud největším obsahem. Takové řešení má složitost Θ(K4).
Můžeme přijít se zlepšovákem: rozmyslíme si, že když zkoušíme nějaké tři vrcholy obdélníka, tak umíme
jednoznačně určit, kde musí ležet čtvrtý vrchol – popřípadě, že naše tři body
jsou slepá ulička a obdélník z nich postavit nejde. Stačí nám tedy zkoušet
všechny trojice bodů, dopočítat čtvrtý bod, a otestovat, zda se nachází mezi
našimi K body. To umíme v konstantním čase, pokud použijeme hešování
(v Pythonu set nebo dict), případně v čase O(log K), pokud si
na začátku body seřadíme (například primárně podle x-ové souřadnice a
sekundárně podle y-ové) a pak použijeme binární vyhledávání. Celková časová
složitost je tedy O(K3), případně O(K3 log K).
Tento postup umíme ještě vylepšit, když si uvědomíme, že nám stačí zkoušet jen dva body: levý dolní a pravý horní roh obdélníka. Zbylé dva body z nich už umíme dopočítat: pokud je levý dolní roh na souřadnicích (x1, y1) a pravý horní na (x2, y2), pak levý horní roh je na (x1, y2) a pravý dolní na (x2, y1). Jejich existenci umíme opět ověřit buď hešováním, nebo binárním vyhledáváním. Tím se dostaneme na časovou složitost O(K2), resp. O(K2 log K).
Dobrým zvykem je ověřit, že náš algoritmus funguje, tedy, že vypíše platný obdélník a ten bude mít největší možný obsah. Na jednu stranu algoritmus určitě vypíše nějaký platný obdélník: dva rohové body jsou z naší množiny bodů a u obou dopočítaných bodů v algoritmu explicitně kontrolujeme, zda existují. Na druhou stranu, vezmeme-li obdélník O s největším obsahem, náš algoritmus ho najde, neboť zkouší všechny dvojice bodů, takže natrefí i dvojici (levý dolní roh O, pravý spodní roh O).
38-Z3-3 Polární express (Zadání)
Na vstupu dostaneme rozměry mřížky R a S, počáteční pozici lokomotivy
x, y a vagóny neboli body přejezdu N. Naším úkolem je vymyslet cestu,
která projde všechny vagóny. Cestu zapisujeme pomocí znaků >, <,
v a ^, které značí pohyb doprava, doleva, dolů a nahoru. Cesta
nemusí být nejkratší, ale musí mít méně než 106 kroků.
Triviální řešení je pustit vlak tak, aby prošel všechna políčka mřížky a vrátil se zpět na start. To zaručí, že posbíráme všechny vagóny bez nehody. Nevýhoda: cesta má délku R ·S, což může být více než 106.
Jak to ale vylepšit? Klíčem je projít body po řádcích tak, aby vlak nemohl vrazit do sebe. K tomu využijeme, že mřížka je toroidální: když se vlak dostane na pravý okraj, může pokračovat zleva, a když se vlak dostane na spodní okraj, může pokračovat shora. Díky tomu neexistuje okraj mapy a vlak se může pohybovat bez omezení.
Pro jednodušší práci se souřadnicemi posuneme lokomotivu na (0,0) a všechny vagóny posuneme o stejnou hodnotu jako lokomotivu. Tady využijeme toroidální vlastnost mřížky – když posuneme lokomotivu o x doprava, posuneme všechny vagóny také o x doprava. Tímto trikem získáme nejen jednodušší souřadnice, ale i informaci o tom, jak daleko jsou vagóny vpravo a dolů od lokomotivy.
Nyní seřadíme vagóny, lexikograficky podle řádků a sloupců. V každém řádku pak postupujeme takto: pokud jsme ve sloupci c, navštívíme všechny vagóny v daném řádku, které jsou v sloupcích větších než c, a pak se vrátíme přes torus až do posledního vagónu co může být c-1. V posledním bodě řádku se pak posuneme dolů a opakujeme tento postup pro další řádek. Tímto způsobem zajistíme, že se vlak nikdy nesrazí sám se sebou.
Pohyb mezi body je pak jednoduchý: mezi dvěma sousedními body spočítejme rozdíl v poloze a to nám řekne, kolik kroků musíme udělat doprava a dolů. Přitom využijeme toroidní vlastnost mřížky – když musíme jít záporně doprava, půjdeme místo toho doprava přes levý okraj, a podobně pro dolů.
Řešení má časovou složitost O((N log N ) + N ·max(R, S)). Třídění zabere O(N log N) plus čas na vypisování cesty, která může mít délku až 2 ·N ·max(R, S), protože v nejhorším případě můžeme projít všechny vagóny a mezi nimi ujít vzdálenost R nebo S.
38-Z3-4 Nákup v poslední chvíli (Zadání)
Na vstupu jsou časy příchodu každého zákazníka a1, … , an. Nejjednodušší způsob, jak přijít na optimální počet stanovišť K, je postupně si simulovat, jestli zákazníkům bude stačit k = 1, k = 2, k = 3, … , než na optimum narazíme. V celém řešení budeme předpokládat, že přesun zákazníků je instantní. Nejprve si setřídíme seznam časů příchodu a pak spustíme simulaci pro k stanovišť:
Pro tuto simulaci si vyrobíme pole S o k prvcích, kde si budeme pamatovat, v jaký čas bude každá stanice volná – na začátku jsou všechny volné v čase 0. Pak iterujeme seřazený seznam příchodů. Pro příchod ai najdeme minimum c v poli S, respektive čas kdy bude nějaká stanice nejdříve volná. Pokud je c ≥ ai + 15, tedy právě příchozí zákazník musí čekat déle než patnáct minut, víme, že k stanic nám nebude stačit a spustíme novou simulaci pro k + 1. Jinak můžeme zákazníka k této stanici umístit, ta pak dalšího zákazníka může obsloužit v čase max(c, ai) + 5; tedy v moment, kdy je stanoviště připraveno nebo kdy přijde zákazník (kterákoli ze situací nastane později) plus pět minut. Touto hodnotou nahradíme c v seznamu a můžeme se posunout k dalšímu zákazníkovi. Pokud takto úspěšně odsimulujeme i posledního zákazníka, našli jsme to nejlepší K, neboť všechny simulace předtím musely selhat.
Jak jsme na tom s časovou složitostí? V nejhorším případě, kdy všichni zákazníci přijdou nahuštění v jeden čas, budeme potřebovat K = n / 3 stanic (za patnáct minut u jedné stanice obsloužíme tři zákazníky). Simulací tedy provedeme O(n)-krát. Jedna simulace musí projít všech n zákazníků, zároveň pro každého zákazníka hledáme minimum v seznamu dlouhém k = n / 3. Společně s počátečním tříděním v čase O(n log n) vyjdeme s monstrózní složitostí O(n3). Zbytečně hodně času mrháme na opakovaném hledání minima a slepém zkoušení různých k. Jak to zvládnout lépe?
Začneme opět se setříděným seznamem příchodů zákazníků. Místo toho, abychom museli pokaždé minimální čas pracně hledat, pořídíme si datovou strukturu, která tu těžkou práci odvede za nás, tedy minimovou haldu – ta za cenu pomalejších přidávání nových prvků zvládne minimálním časem odpovědět konstantně rychle. Na začátku si do haldy umístíme pouze jeden čas 0. Pak v jedné smyčce pro každý čas návštěvy ai opakujeme:
Podíváme se na minimální prvek c v haldě. Pokud c ≤ ai + 15, stihne tato stanice obsloužit zákazníka včas. Odebereme c z haldy a zpět do ní přidáme max(c, ai) + 5. Jinak je c > ai + 15, tedy v haldě nemáme dost stanic. To jednoduše vyřešíme přidáním nového čísla ai + 5 (můžeme si to představit tak, že tam tato stanice čekala na tohoto zákazníka a dále ji pak mohou využít i ostatní). Odpovědí na otázku je pak počet čísel v haldě.
Toto bude fungovat, protože otvíráme novou stanici (přidáváme nové číslo do haldy) pouze v moment, kdy je to nutné. Jakmile otevřeme stanici K pro i-tého návštěvníka, všech ostatních K - 1 stanic je dostupných až po čase ai + 15, jinak řečeno k - 1 zákazníků používá v čase ai + 15 nějakou stanici a na chudáka příchozího v ai by se nedostalo.
Časově jsme na tom o hodně lépe. Cyklus máme pouze jeden přes všechny zákazníky. V každé iteraci můžeme z haldy jednu hodnotu odebrat a jednu přidat, obojí v čase O(log n). Kolik máme čísel (stanovišť) v haldě zjistíme průchodem v čase O(n). Celková časová složitost i s prvotním tříděním tedy vyjde O(n log n). V paměti si musíme uchovat časy příchodu a časy dostupnosti stanic, kterých ale nebude nikdy více než zákazníků samotných, tudíž je prostorová složitost O(n).