Čtvrtá série devatenáctého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 19-4-1: Finanční toky
- 19-4-2: Byrokratický aparát
- 19-4-3: Naskakování na vlak
- 19-4-4: Váhy
- 19-4-5: Hazardní hra
- 19-4-6: Prolog
19-4-1 Finanční toky (Zadání)
De facto všichni řešitelé dokázali najít stok, pokud v daném grafu byl, nicméně je třeba si přiznat, že při použití kvadratického řešení by Přesprst sotva unikl. Otázkou jen zůstává, jak to napsat rychleji.
Otestovat, zda-li je vrchol stok dokážeme zřejmě v O(N). Problém je, že při použití algoritmu, který se u každého vrcholu zeptá, zda-li je stok, bude celý program potřebovat O(N2) času. Celý problém v nalezení rychlejšího řešení bude tedy v nějakém šikovném výběru kandidáta na stok.
Podívejme se tedy na vlastnosti stoku. Zřejmě v grafu může existovat jen jeden (sporem: Pokud by byly alespoň 2 stoky i a j, tak dle definice musí vést do stoku i hrana z každého jiného vrcholu, tedy i z j. Nicméně pokud j je stok, tak z něj žádná hrana nemůže vést…).
A jak kandidáta na stok nalézt? V i-tém kroku budeme pamatovat jediného kandidáta na stok mezi vrcholy 1..i (začneme s 1). Označme ho k. Kandidáta pro (i+1)-ní krok zjistíme jednoduše. Když vede z k do i+1 hrana, tak zřejmě k nemůže být stok a jelikož mezi vrcholy 1..i byl jediným kandidátem, tak naději na to, stát se stokem, má jen vrchol i+1, což bude náš nový kandidát. V opačném případě hrana z k do i+1 nevede, takže vrchol i+1 nemůže být stok, jelikož do něj nevede hrana z každého jiného vrcholu a tedy kandidát zůstává.
Nakonec jen otestujeme, zda-li kandidát, kterého získáme n-tým krokem je stok, nebo ne.
Nalezení kandidáta i jeho otestování se zřejmě stihne v čase O(N) a paměťové nároky, pokud nepočítáme vstupní matici, jsou konstantní.
19-4-2 Byrokratický aparát (Zadání)
Měl jsem připraveny velmi vtipné hlášky, například že bude třeba zestátnit zemědělské podniky, aby nám pomalu se courající úřední šimlík nepošel na své dlouhotrvající cestě hlady, bohužel, nebo spíš bohudík si je musím odpustit, protože většina z vás vytvořila optimálně rychlé algoritmy. A tak vám mohu vytknout jen jedinou věc. Ale k tomu až později.
Řešení úlohy se dalo rozdělit na dvě části. V první části si stačilo povšimnout, že graf (vrcholy jsou úředníci, orientované hrany pak značí směr dokumentu) se skládá z oddělených cyklů. Tyto cykly se pak dají najít v lineárním čase. Jistě, mohli bychom na to použít DFU (viz kuchařka 16-3), ale my jsme řekli ne. Je sice fakt, že se DFU chová docela dobře, ale vaše implementace fungovaly většinou v čase O(N log N). Více už příslušná kuchařka. Správné řešení spočívalo v použití procházení do hloubky. Vždy si vezmu první nepoužitý vrchol, označím ho jako použitý, posunu se na jeho následníka a to opakuji tak dlouho, než dojdu do již použitého vrcholu. A protože na každý vrchol sáhnu nejvýše dvakrát, poprvé když zkoumám jestli už byl použit a podruhé ve chvíli, kdy je něčím následníkem a přesunu se na něj, tak mě lineární časová složitost nemine. Samozřejmě nebude problém si přitom délky jednotlivých cyklů počítat.
Druhá část je ta, u které se lámal chleba. Téměř každý z vás si uvědomil, že je třeba spočítat nejmenší společný násobek délek všech cyklů. To je celkem jasně vidět z toho, že hledáme takový počet kroků, pro který bude mít každý úředník svůj dokument, tzn. každý cyklus musel být ukončen. No ale tím pádem musí být počet kroků dělitelný každou délkou cyklu a zároveň musí být nejmenší. A to je právě nejmenší společný násobek (NSN). No a jelikož NSN(a,b)=a·b/NSD(a,b) (důkaz si jakožto jednoduché cvičení proveďte sami) a NSN(l1,l2,… ,lN)=NSN(NSN(l1,l2,… ,lN-1),lN), tak je postup nabíledni. Postupně budeme počítat NSN prvních k čísel, z něj pak k+1 čísel atd. až N. Zbývá jen pořešit získávání NSD. Na to slouží Euklidův algoritmus, který si najděte např. na http://cs.wikipedia.org/wiki/Euklidův_algoritmus.
O složitosti této složitosti vypovídala vaše řešení. Jen velmi málo z vás ji určilo opravdu správně, takže si dovolím být poněkud obšírnější. Složitost Euklidova algoritmu je O(log a), kde a je větší z čísel. Jenže po prvním kroku hledáme NSD(a mod b, b), takže se dá říct, že ta složitost je O(log b)+1=O(log b). Při výpočtu potom počítáme vždy NSN nějakého čísla a jedné z délek cyklů. Považujme délku za menší číslo (rozmyslete si, proč si tím mohu pouze uškodit) a tím pádem jeden takový krok trvá O(log(délka cyklu)). Nyní přijde jedno malé kouzlíčko: log(délka cyklu) ≤ délka cyklu a součet všech délek je N, a tak složitost bude nejvýše O(N). To nám ale bohatě jako odhad stačí, protože ani první část netrvala kratší dobu. Paměť je samozřejmě lineární.
Několikrát se vyskytl Euklidův algoritmus, který místo modula používal mínus. To sice funguje, ale složitost se nám vyšplhá až do exponenciálních výšin. Nejprve si prohlédneme chování algoritmu pro K a 1 a s hrůzou zjistíme, že udělá K kroků. Pak stvoříme vhodný vstup, třeba prvních √N délek bude mít velikost řádově √N (jejich součet je tedy N), takže jejich NSN bude asi √N√N, a vtipně je doplníme jedním cyklem délky 1 a složitost O(√N√N) je na světě. Nicméně to neberte jako důkaz, protože to ve skutečnosti nic nedokazuje, ale spíš jako náhled na to, kam až může záměna jedné operace vést.
Samozřejmě se vyskytly i jiné přístupy, například jste si zjistili prvočinitele každé délky a jejich pronásobením získali kýžený NSN. Zkuste si dorozmyslet detaily a zároveň si spočtěte, že je to skutečně lineární.
19-4-3 Naskakování na vlak (Zadání)
Hned na začátek si neodpustím jednu poznámku: ve všech algoritmech budeme zkoumat pouze složitost, se kterou algoritmus řešení nalezne. Časovou složitost na jeho vypsání v odhadech počítat nebudeme. Vyniknou tak lépe rozdíly mezi jednotlivými algoritmy. Pokud by to někomu připadalo nefér, tak si může ke všem složitostem přičíst O(v ·k), kde v je počet navzájem různých podřetězců délky k.
Nyní již k samotné úloze. Mnoho řešitelů využilo nápovědu v zadání úlohy, a tak drtivá většina řešení využívala hashování. Ale už jenom drobná hrstka objevila, že úplně přímočaré použití kuchařky k rychlému řešení nepovede.
Základní algoritmus, který se na první pohled nabízel, byl ten, že jsme postupně brali jednotlivé podřetězce délky k, ty jsme zahashovali, a pak jsme si v nějaké tabulce (po ošetření kolizí) ukládali počet výskytů jednotlivých podřetězců. Takové řešení má v průměrném případě časovou složitost O(n·k)
Předchozí metoda měla tu nevýhodu, že jsme pro každý podřetězec museli spočítat znovu celou hashovací funkci a to zabere čas O(k). Co kdybychom ale našli takovou funkci, která by dokázala využít toho, že její hodnotu známe již pro předchozí podřetězec?
| k-1 |
| j=0 |
Zápis Ai[j] je totéž co A[i+j], tedy j-tý znak od i-tého znaku v řetězci a P je nějaké číslo, které je řádově tak velké, jako velikost abecedy.
Pokud chceme přejít na následující podřetězec provedeme tyto operace: celou sumu vynásobíme P, škrtneme první písmeno z předchozího slova a přičteme poslední písmeno z následujícího. Matematicky zapsáno:
| k-1 |
| j=0 |
| k-1 |
| j=0 |
| k |
| j=1 |
| k-1 |
| j=0 |
Takže jsme použili konstantně mnoha kroků (nezávisle na k) a získali jsme hodnotu hashovací funkce pro řetězec, který začíná na pozici i+1, a to je přesně to, co jsme chtěli.
Zbývá dořešit několik technických detailů. V běžných programovacích jazycích máme proměnné omezeného rozsahu, takže pro velké k nemůžeme spočítat celou sumu. Ale můžeme si pomoci. Stačí všechny operace provádět modulo nějaké prvočíslo. A jako ono prvočíslo můžeme použít třeba rovnou velikost hashovací tabulky.
Za poznámku stojí, že ono prvočíslo musí být opravdu prvočíslo, jinak bychom se dostali do problému. Odpověď na otázku „Proč?“ by asi nebyla nejstručnější, zájemci si ale mohou přečíst nějaké povídání o konečných tělesech.
Jak ale takové prvočíslo najít? Dle teorie čísel je pravděpodobnost toho, že libovolné přirozené číslo n je prvočíslem, je zhruba 1/ ln n, a ověření toho, že n je prvočíslo lze základním algoritmem provést v čase O(√n). Takže prvočíslo větší než nějaké n lze najít v čase O(√n· ln n), což je méně než O(n). Takže problém s hledáním prvočísla mít nebudeme.
A jak to bude s paměťovou složitostí? Mnoho řešitelů si pro každou položku v hashovací tabulce pamatovalo celý podřetězec. To je ale zbytečné a paměťová složitost se tím zhorší. Stačí si přeci pamatovat pouze index, kde daný podřetězec ve vstupním řetězci začíná, což zlepší časovou složitost na O(n).
Takže jsme nalezli algoritmus, který v průměrném případě poběží v čase O(n+v·k), kde v je opět počet různých podřetězců. V nejhorším případě pak v čase O(n2·k).
Poznámka na úplný závěr: Pokud bychom chtěli dosáhnout času O(n+v·k) i v nejhorším případě, mohli bychom použít sufixové stromy. Povídání o této datové struktuře a i návod jak pomocí ní vyřešit tuto úlohu lze nalézt na adrese http://mj.ucw.cz/vyuka/ga/.
19-4-4 Váhy (Zadání)
Pošťák by asi koukal, kdyby jste se mu snažili vysvětlit, jak zvážit libovolnou celočíselnou váhu s optimální sadou závaží. Jak vypadá optimální sada závaží? Jsou to závaží 1, 3, 9, 27,… , tedy mocniny trojky. Kolik jich potřebujeme a jak jsme na to přišli? To si hned ukážeme.
| 3n - 1 |
| 2 |
| 3n - 1 |
| 2 |
- Pro n = 1 to určitě platí, protože
= 1.3n - 1 2 - Nechť tvrzení platí pro všechna k < n. Rozdělme vážené hmotnosti
do čtyřech intervalů.
- Hmotnosti 1, … ,
zvážíme dle indukčního předpokladu s prvními n-1 závažími.3n-1 -1 2 - Hmotnosti
+ 1 = 3n-1 -3n-1 - 1 2
, … , 3n-1 -1 zvážíme tak, že n-té závaží dáme naproti předmětu a pomocí prvních n-1 závaží, které přikládáme „obráceně“, odvážíme libovolnou hmotnost z tohoto intervalu.3n-1 - 1 2 - Hmotnost 3n-1 zvážíme pomocí n-tého závaží.
- Hmotnosti 3n-1 + 1, … ,
= 3n-1 +3n - 1 2
zvážíme tak, že n-té závaží dáme naproti předmětu a pomocí prvních n-1 závaží odvážíme zbytek hmotnosti.3n-1 -1 2
- Hmotnosti 1, … ,
| 3n - 1 |
| 2 |
| 3n - 1 |
| 2 |
19-4-5 Hazardní hra (Zadání)
Hazardní hry nejsou pro slabé povahy, kdo na to nemá nervy a není si jistý, že vyhraje, ať raději zkusí své štěstí v kuličkách. Většina z vás správně vymyslela algoritmus, který Přesprstovi pomůže vyhrát, protože používá nejmenší možný počet operací k vyskládání požadované částky. Pravda, byli řešitelé, v jejichž uvažování se vyskytla chyba či dodali pouze útržek zdrojáku beze slova vysvětlení, ale takových byla menšina. Jakkoli tedy většina vymyslela optimální postup, skutečně bezchybných důkazů, že je optimální, se sešlo jako šafránu. Pojďme se tedy společně zamyslet nad správným řešením tak, aby to pochopil i detektiv Přesprst.
Označme si částku k vyskládání jako M. Nejprve si uvědomíme, že pro asymptoticky optimální řešení, tj. používající asymptoticky nejmenší počet operací, bychom si vystačili pouze s operacemi +1 a ×10. Představme si číslo M zapsané v desítkové soustavě. Takový zápis bude mít O(log M) cifer. Podíváme na hodnotu první cifry c1 zleva a c1-krát přičteme jedničku. Pak se posuneme na druhou cifru c2 zleva, aktuální hodnotu vynásobíme deseti a c2-krát přičteme jedničku, a tak dále. Zjevně po O(log M) krocích dostaneme hledané číslo, a protože nad každou cifrou čísla musíme udělat alespoň jednu operaci (násobení 10), je náš postup asymptoticky optimální.
My bychom však chtěli přesně optimální řešení. K čemu nám v tom pomohou operace /10 a -1? Dělení desítkou nám v ničem nepomůže; dokážeme sporem. Mějme nějakou hodnotu h a uvažme nejkratší posloupnost operací, která vyskládá h a pro spor používá dělení. V okamžiku dělení má aktuální hodnota poslední cifru, na jejíž vyrobení jsme využili jistou posloupnost ostatních operací. Vydělíme-li nyní h deseti, přijdeme o hodnotu v poslední cifře, jinými slovy, operace vedoucí k jejímu vyrobení vůbec nebylo potřeba používat. Dostali bychom tedy kratší posloupnost operací vedoucí k vyskládání h, což je spor s tím, že jsme uvažovali nejkratší takovou posloupnost.
Ukážeme nyní lepší řešení úlohy a potom o něm dokážeme, že je optimální. Problém vyřešíme rekurzivně. Pro jednociferné M si rozmyslíme, že pro 0≤ M≤ 5 je výhodnější M-krát použít +1 a pro 6≤ M≤ 9 je lepší použít +1,×10 a potom (10-M)-krát -1.
Pro víceciferné M úlohu převedeme na úlohu s číslem o jednu cifru menším. Číslo M můžeme napsat ve tvaru M=10a+b, kde b je poslední cifra napravo. Nyní použijeme stejnou myšlenku jako u jednociferného čísla. Je-li 0≤ b≤ 5, vyřešíme úlohu pro číslo a, pak použijeme ×10 a následně b-krát +1. Je-li 6≤ b≤ 9, vyřešíme úlohu pro číslo a+1, potom použijeme ×10 a následně (10-b)-krát -1.
Je však potřeba si rozmyslet, že uvedený algoritmus skutečně používá minimální možný počet operací. Tuto skutečnost si dokážeme napůl neformálně matematickou indukcí podle počtu cifer čísla M.
Pro jednociferné M je to zjevně optimální postup, to lze nahlédnout rozborem možností. Uvažme nyní víceciferné M=10a+b, variantu 0≤ b≤ 5. Z indukčního předpokladu víme, že algoritmus použije pro vytvoření a minimální počet operací. Chceme-li za a přidat další cifru, nejúspornější je a vynásobit deseti a b-krát přičíst jedničku, zjevně se nevyplatí žádné odčítání ani vícenásobné násobení deseti.
Druhá varianta, 6≤ b≤ 9, je o něco záludnější. V nejhorším případě, pro b=6, se vykoná 6 operací (přičtení, násobení a odečítání). Potíž je však v tom, že se rekurzivně voláme na vytvoření čísla a+1, a není jasné, co to udělá s optimálním počtem operací na vytvoření takového čísla. Tuto skutečnost mnoho řešitelů opomnělo.
Uvědomíme si, že minimální počet operací potřebných k vyrobení a+1 je nejhůře o jedna větší než minimální počet operací na vyrobení a. Končilo-li a na cifru menší než 5, náš algoritmus zjevně vypíše jen o jednu operaci navíc. Byla-li poslední cifra a mezi 6 a 8, zvýšíme ji tedy o jedna, čímž díky odečítající metodě ve skutečnosti počet operací pro a+1 dokonce snížíme. Poslední možnost je, že poslední cifra a byla 9. Tehdy se zvýší o jedničku následující cifra, čímž stejným argumentem (pouze o cifru dále) dostaneme, že přibude maximálně jedna operace navíc.
Tím pádem v nejhorším případě b=6 se provede 7 operací, což je stejný počet, jako kdyby se místo odečítací metody použila přičítací metoda, pro b>6 už si však pomůžeme.
Algoritmus stráví nad každou cifrou konstantní počet kroků a rekurze se zanoří do takové hloubky, kolik je cifer, časová i paměťová složitost tedy vyjdou O(log M). Samotný program je napsán tak, že se vícenásobné přičítání a odčítání realizuje jako jedna úroveň rekurzivního volání hlavní procedury.
19-4-6 Prolog (Zadání)
1. Lednice
Výprava do hlubin lednice skončila úspěšně. V prográmku na pár řádek skoro nešlo udělat chybu. Bylo si jen třeba uvědomit, kam umístit řez, aby při opakováním volání nevznikaly nesmyslné počty potravin.
2. Myší spartakiáda
Myší spartakiáda byla také velmi populární. Někteří si ztížili zadání
tím, že nejprve generovali celý seznam kombinací a poté jej
vypisovali, ale protože úkolem je pouze vypsat všechny kombinace na
výstup, můžeme to udělat takhle jednoduše: vygenerujeme celý obrazec,
vypíšeme jej na obrazovku, zařízneme a přikážeme predikátu selhat
pomocí fail. Prolog tedy snaživě zkusí vygenerovat nový obrazec, ten
opět vypíšeme, selžeme, a takto nutíme Prolog hledat další obrazce,
dokud neodpoví no. Mezitím jsou už ale všechny vypsány na obrazovku.
3. Myš v bludišti
Běda! O myším bludišti se ještě dlouho budou zdát noční můry nejen nešťastným programátorům, ale také zoufalým opravujícím, kteří se museli proplést spletitým bludištěm kódu. A to ještě nemluvíme o tom, že všechny myši by zešedivěly a sešly věkem, než by většina programů vydala výsledek. Přitom na první pohled vypadá úloha jednoduše, až nevinně.
Následující text obsahuje slova jako „zásobník“, „fronta“,
„dfs“, „bfs“, „graf“ a podobné. Pokud nevíte, o čem je řeč,
znovu vás odkazujeme na příslušnou kuchařku
http://ksp.mff.cuni.cz/tasks/19/cook3.html.
Nejprve rozebereme chybu, kterou udělali skoro všichni. Nápadná poznámka „hledejte libovolně dlouhou cestu“ zcela oprávněně naváděla na to, k čemu je Prolog jako dělaný, k rekurzivnímu prohledávání. Správně jste si uvědomili, že si při prohledávání grafu musíte pamatovat již navštívené vrcholy. Ale málokoho napadlo, že při návratu z neúspěšné větve (tedy z takové, kde se nenašla cesta k cíli) se pilně nastřádaný seznam navštívených vrcholů opět odunifikovává a mizí. Naštěstí (pro vás) tato chyba neublíží funkčnosti, zato se ale stále dokola prochází vrcholy, ve kterých už jsme dávno byli a časová složitost roste až k exponenciální.
Jak z toho ven: Nesmíme implementovat průchod grafem až tak přímočaře,
jak nás k tom svádí Prolog. Shodli jsme se na tom, že pamatovat si
navštívené vrcholy je přímo životní nutnost, ale nesmíme o ně
přicházet při návratu z neúspěšných větví. Tedy musíme to udělat tak,
aby žádné neúspěšné větve nebyly, abychom nikdy „nefailovali“.
V predikátu cesta si budeme udržovat zásobník vrcholů a seznam navštívených vrcholů. V každém kroku vybereme vrchol z vrcholu zásobníku a najdeme všechny jeho nenavštívené sousedy. Tyto sousedy šoupneme na vrchol zásobníku a všechny označíme jako navštívené. Poté spustíme predikát cesta znovu s novým zásobníkem a novým seznamem navštívených vrcholů.
Tímto jsme se vlastně rozhodli nepoužít „vestavěnou“ prologovskou rekurzi, ale simulujeme si ji pomocí zásobníku. Proces skončí buď úspěšně, pokud se najednou na vrcholu zásobníku objeví cíl, nebo neúspěšně, pokud se zásobník vyprázdní, což by znamenalo, že jsme prozkoumali celý graf do hloubky a cestu k cíli jsme nenašli.
Navíc si stačí uvědomit, že pokud vyměníme použitý zásobník za frontu, změní se prohledávání z průchodu do hloubky na průchod do šířky a jako bonus dostaneme cestu nejkratší (za tu jsme ovšem žádné bonusové body neudělili, protože nejkratší cestu myši nepožadovaly).
Jenomže teď bychom potřebovali ještě určit, kudy cesta vede. Nemůžeme si ji budovat odzadu návratem z úspěšné větve, protože teď jsou všechny větve úspěšné a my nerozpoznáme, kdy se vracíme z úspěšné a kdy z neúspěšné větve a kdy si tedy máme cestu zapisovat. Můžeme si ale během výpočtu zapisovat pro každý vrchol jeho předchůdce a nakonec cestu odzadu zrekonstruovat.
4. Oprava
Chybu si uvědomíme, když dosadíme
Co se v predikátu děje, vidíme jasně: Nejprve se pokusíme zunifikovat první řádek, což se nepodaří, skočíme tedy na druhý a ten projde. Řešení je například takovéto:
Nedovolili jsme Prologu ihned zunifikovat poslední argument, ale
nejprve jsme mu zakázali použít další větev. Teprve potom smíme
zunifikovat X = Z.