Pátá série osmnáctého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 18-5-1: Účetní
- 18-5-2: Permutovat se musí legálně!
- 18-5-3: Číňanské volby
- 18-5-4: Detektýv
- 18-5-5: Do vysokých kruhů
- 18-5-6: Profilování
18-5-1 Účetní (Zadání)
Řešení došlo opravdu hodně a většina jich byla i správně. Finančnímu úřadu tedy nezbývá než doufat, že se z vás stanou programátoři, a ne třeba … účetní. Pro ty z vás, kterým se úlohu náhodou vyřešit nepodařilo, posíláme řešení vzorové, abyste měli v kriminále o čem přemýšlet :)
Vězte, že k získání maxima bodů nestačil pouze správný popis řešení. Nezbytnou součástí musel být i důkaz, aby vám účetní věřili, že je nechcete podfouknout.
Situace pro dva účetní je velice jednoduchá. První rozdělí majetek na dvě poloviny podle svého mínění. Druhý si vybere polovinu, která se mu zdá větší. První je spokojený, protože dostal přesně polovinu majetku. Druhý je taktéž spokojený, protože si vybral větší díl ze dvou, takže má alespoň polovinu majetku (podle jeho mínění).
Ve třech je situace o trochu komplikovanější, protože musíme rozebrat několik případů. Dokonce existuje několik řešení, jak účetní spravedlivě podělit. Nyní si ukážeme jedno z nich: První rozdělí majetek na tři díly, o kterých tvrdí, že jsou to přesně třetiny (označím je A, B a C). Nyní druhý a třetí ukáží na hromádku, která se jim zdá největší. Zde mohou nastat dva případy. Buď oba ukázali na různé hromádky (řekněme, že 2. ukázal na B a 3. ukázal na C). Pak si tyto hromádky nechají a prvnímu zbude poslední hromádka (tj. A). Všichni budou spokojeni, protože 2. a 3. si myslí, že mají největší hromádku ze tří (což je určitě víc než 1/3 a 1. dostane právě třetinu (sám si to tak rozdělil). Komplikace nastane, pokud 2. a 3. ukáží na stejnou hromádku (řekněme na A). V takovém případě si tuto hromádku rozdělí půl na půl (předchozím algoritmem) a znovu ukážou na hromádku, která se jim zdá největší (ze zbývajících dvou - B a C). I zde mohou nastat dva případy. Pokud oba ukáží na stejnou hromádku (řekněme B), tak si ji rozdělí „fifty-fifty“ a poslední hromádku C nechají prvnímu. První bude spokojen určitě, protože je mu jedno, kterou hromádku dostane. Druhý a třetí budou spokojeni rovněž, neboť si mezi sebe spravedlivě rozdělili dvě „největší“ hromádky (lze jednoduše nahlédnout, že tyto hromádky obsahují alespoň 2/3 majetku). Druhá možnost je, že při druhém výběru si každý vybere jinou hromádku (řekněme 2. vybere B a 3. vybere C). V takovém případě se oba podělí o zvolenou hromádku s prvním účetním (algoritmem dělení pro dva). Opět budou všichni spokojeni. První dostal dvakrát alespoň 1/2 z 1/3, takže má nejméně 2 · 1/2 · 1/3 = 1/3. Druhý a třetí dostali každý alespoň polovinu z dvou (podle nich) největších hromádek, takže mají každý alespoň 1/3.
Abychom si ukázali i jiný algoritmus na dělení, budeme řešit úlohu N účetních trochu jinak. Řešení i důkaz bude založené na rekurzi a matematické indukci. Předpokládejme, že umíme vyřešit úlohu pro N-1 účetních a chceme ji rozšířit na N účetních. Vezmeme prvního účetního a na chvíli jej postavíme stranou. Teď necháme zbývajících N-1 účetních, aby si rozdělili spravedlivě všechen majetek mezi sebe. Každý účetní kromě prvního má tedy svoji hromádku (označme je H2, H3 ... HN) o které si myslí, že obsahuje alespoň 1/(N-1) majetku. Nyní poprosíme jednotlivé účetní, aby každý rozdělil svoji hromádku na N stejných podhromádek. První účetní pak obejde všechny své kolegy a od každého si vezme jednu podhromádku. Všichni by měli být spokojeni. První dostal z každé hromádky alespoň 1/N-tinu. O jednotlivých hromádkách toho z pohledu prvního účetního moc tvrdit nemůžeme, ale víme, že jejich součet je 1 (dohromady tvoří celý majetek):
První má tedy alespoň 1/N-tinu majetku. Ostatní by měli být také spokojeni. Při počátečním dělení dostal každý hromádku, na které bylo (podle jeho mínění) alespoň 1/(N-1) majetku. Následně jej první obral přesně o 1/N-tinu této hromádky, takže každému zbyla přesně (N-1)/N-tina toho, co už dostal. Ve výsledku každému zbylo 1/(N-1) · (N-1)/N = 1/N majetku.
Všichni jsou spokojeni (snad až na finanční policii) a tak hurá na Seychely…
18-5-2 Permutovat se musí legálně! (Zadání)
Pro „výzkumné“ účely si úlohu pozměňme: Chceme vypsat všechny permutace dané množiny lexikograficky setříděné. Jak na to? Zafixujeme nejmenší prvek z množiny na začátku a za něj postupně připojíme všechny lexikograficky setříděné permutace zbývajících prvků. Poté zafixujeme druhý nejmenší prvek a postup zopakujeme, atd. Takto by bylo možné napsat rekurzivní funkci, která by vždy fixovala prvky od nejnižšího k nejvyššímu (zafixovaný prvek označme jako prvek přilehlý) a pomocí sama sebe by vygenerovala všechny permutace zbylých prvků (jejich množinu označme jako zbytek).
Jak nyní vyřešíme původní úlohu? Stačí najít zbytek, který v zadané permutaci právě dopermutoval, a k němu přilehlý prvek. Nyní můžeme permutovat zbytek opět od začátku, s tím rozdílem, že pouze vyměníme přilehlý prvek s nejbližším vyšším prvkem z nalezeného zbytku (tedy to samé, co v modifikované úloze).
A implementace? Prvním úkolem je najít zbytek, který v zadané permutaci právě dopermutoval. To je ale snadné, neboť víme, že se nachází na konci permutace a ona dopermutovanost znamená, že zbytková posloupnost je sestupná a nejdelší možná. Začít permutovat zbytek od začátku je také jednoduché. Stačí si uvědomit, že jediné co je třeba udělat, je setřídit ji vzestupně. To bylo ale kamenem úrazu některých řešení, neboť posloupnost třídili některým z třídících algoritmů místo aby si všimli, že ze sestupné posloupnosti vytvoříme vzestupnou tak, že obrátíme pořadí jejích prvků.
Záměna přilehlého prvku je již triviální. Problém může nastat pouze tehdy, když žádný přilehlý prvek neexistuje. To se ale stane jenom tehdy, když jsme na vstupu dostali lexikograficky nejvyšší možnou permutaci.
Paměťová i časová složitost je O(N).
18-5-3 Číňanské volby (Zadání)
Představme si následující „paralelní“ algoritmus na vyhodnocení voleb: každý Číňan si najde do dvojice nějakého Číňana, který chce volit někoho jiného. Pokud má některý kandidát nadpoloviční většinu hlasů, někteří z jeho příznivců zůstanou nespárovaní; u takto nalezeného potenciálního vítěze si ještě ověříme, zda skutečně vyhrál (spočítáme si počet jeho hlasů).
Druhou část tohoto algoritmu jistě zvládneme v lineárním čase a s konstantní pamětí, zbývá si rozmyslet, jak realizovat tu první. Zjevně nás nezajímá, jak jsou Číňané spárováni, stačí nám vědět, kolik jich zůstane nespárovaných a pro koho nespárovaní hlasují. Budeme si tedy udržovat dvě čísla – K (číslo kandidáta, pro nějž hlasují nespárovaní Číňané), a C (počet nespárovaných Číňanů). Postupně procházíme všechny Číňany. Pokud aktuální Číňan hlasuje pro kandidáta K, nejde ho spárovat, a proto zvýšíme C o jedna. Pokud hlasuje pro někoho jiného (kandidáta X), rozlišíme dva případy: jestliže je C>0, pak tohoto voliče spárujeme s jedním z voličů kandidáta K, tedy snížíme C o jedna. Jestliže je C=0, nelze aktuálního Číňana spárovat, a proto dosadíme K=X a C=1.
Tento algoritmus používá konstantní množství paměti a seznam hlasů projde dvakrát, časová složitost je tedy O(N). Pokud bychom chtěli být přesnější, je třeba vzít do úvahy to, že na uložení čísel potřebujeme O(log N) bitů, což pro velká N nelze zanedbat tedy paměťová složitost je O(log N) a časová O(N log N).
18-5-4 Detektýv (Zadání)
S důkladností takřka šerlokovskou prozkoumáme několik možných řešení, až usvědčíme to nejrychlejší. Označme si (věrni písmenkům ze zadání) N délku stopovaného řetězce, k počet podezřelých sekvencí, p1,… ,pk délky těchto sekvencí a P=p1+… +pk jejich celkovou délku.
0. pokus (jak by ho vymyslel strážník Vopička): Budeme hledat každou sekvenci zvlášť, a to tak, že si po vstupu „pojedeme okénkem“ délky pi a vždy porovnáme, jestli se okénko rovná i-té sekvenci. Kdybychom si okénko ukládali jako cyklické pole, zvládli bychom ho posunout v konstantním čase, ale stejně nás nemine čas O(pi) na porovnání. Celkově trvá O(Np1+… +Npk)=O(NP) a navíc potřebujeme k-krát volat rewind.
1. pokus (inspektor Neverley): Damned, na hledání výskytů jednoho řetězce přeci můžeme použít algoritmus KMP z té vaší cookbook, takže jeden průchod zvládneme v timu O(N+pi), celkově tedy O(Nk+P) s k rewindy. That's it.
2. pokus (policejní rada Žák): V kuchařce je přeci i algoritmus A-McC na hledání výskytů více slov najednou. Stačí, když hlášení výskytu nahradíme připočtením jedničky k počítadlu. (Na to praktikant Hlaváček:) Dobrý plán, pane rado, ale má jedno háčisko jak na sumce: jelikož se sekvence mohou překrývat, může jich v jednom místě končit až k, takže jsme opět na O(Nk+P), i když tentokrát bez rewindů.
3. pokus (Šérlok osobně): Postavíme si vyhledávací automat jako v minulém pokusu, ale místo abychom počítali rovnou výskyty, budeme si pamatovat jen to, kolikrát jsme prošli kterým stavem, a pak z toho výskyty dopočítáme. Well, ale jak?
Pokud máme nějaký stav α (o kterém víme, že je prefixem některého z vyhledávaných slov, takže mimo jiné mezi stavy najdeme všechny sekvence stop, které počítáme) a chceme zjistit, kolikrát se slovo α v textu vyskytlo, stačí sečíst počet průchodů tímto stavem a všemi dalšími stavy, které končí na α, což jsou přesně ty, ze kterých se do α lze dostat pomocí zpětné funkce (případně zavolané vícekrát).
Stačí tedy projít automat v opačném pořadí, než ve kterém jsme vytvářeli zpětnou funkci (nejlepší bude si během konstrukce automatu toto pořadí zapamatovat, třeba v poli, v němž jsme měli uloženu frontu). Pro každý stav α pak přičteme počítadlo odpovídající tomuto stavu k počítadlu stavu, do nějž vede z α zpětná funkce. (To se pak přičte podle další zpětné funkce atd., takže počítadlo stavu α se opravdu postupně popřičítá ke všem rozšířením stavu α.)
To vše zvládneme v čase O(P+N+P) (konstrukce automatu + průchod textem + dopočítání), čili O(P+N), a v paměti O(P+N), bez jediného zavolání rewindu.
Program obnáší připsání cca čtyř řádků ke zdrojáku z kuchařky. Abychom z toho nevybruslili tak snadno, ukážeme si trochu jinou implementaci v Céčku.
It's a lemon tree, my dear Watson!
P.S.: V kuchařce si, nečekán, nezván, opět zařádil šotek a trochu pomíchal vypisování nalezených slov. Opravenou verzi naleznete na webu, rdícího se kuchaře opodál.
18-5-5 Do vysokých kruhů (Zadání)
Nejprve bylo potřeba oblasti převést na objekty, se kterými umíme manipulovat rozumněji než s obecnými množinami bodů v rovině. Velmi užitečné je představit si protínající se kružnice jako graf s průsečíky a dotyky kružnic jako vrcholy. Hrany budou oblouky mezi sousedními vrcholy. Tento graf je vlastně multigraf, což je graf, ve kterém může mezi dvěma vrcholy vést více než jedna hrana a z jednoho vrcholu do toho samého může vést více než jedna smyčka. Takový graf je určitě jednoznačně zadán polohami a poloměry kružnic a je rovinný (původní rozmístění kružnic je jeho rovinné nakreslení). Bohužel se nám do něj nijak nepromítnou izolované kružnice, ty je třeba ošetřit jinak.
Nyní se nám z na první pohled neuchopitelného problému stal problém mnohem jednodušší – spočítat stěny rovinného grafu. K tomu se ideálně hodí Eulerova věta:
Toto je vztah mezi počtem vrcholů (V), stěn (včetně té vnější) (F), komponent souvislosti (K) a hran (E). Tato věta platí pro rovinné grafy a platí i pro multigrafy, pokud si zvolím, že mezi „rovnoběžnými“ násobnými hranami jsou také stěny a že smyčka přidává jednu stěnu. Toto rozšíření přesně odpovídá naší představě toho, jak kružnice dělí rovinu na oblasti.
Věta se dokazuje indukcí podle složitosti grafu. Pro prázdný graf určitě platí (0+1=0+0+1). Přidáme-li nový vrchol, stoupnou V i K o jedna a rovnost zůstane zachována. Přidáme-li hranu a zvýšíme tak E o jedna, pak jsme buď spojili dvě komponenty souvislosti a snížili K o jedna, nebo přidali jednu stěnu rozdělením nějaké existující na právě dvě. V obou případech zůstane rovnost zachována a druhý případ navíc zahrnuje přidávání násobných hran a smyček. Každý rovinný (multi)graf lze postavit z prázdného přidáváním vrcholů a hran, takže pro něj věta musí platit.
Stačilo by tedy spočítat počet komponent, hran a průsečíků. Víme, že na každé kružnici je stejně vrcholů a hran. Vrchol je ale sdílen mezi dvěma kružnicemi, zatímco hrana patří právě jedné. Jinak řečeno je stupeň každého vrcholu 4. Z toho plyne, že E=2V. Tedy:
Tento vzorec nám navíc zahrne i izolované kružnice, počítáme-li je jako jednu komponentu bez průsečíků. To nám trochu zjednoduší algoritmus.
Stačí tedy spočítat počet komponent a průsečíků, obojí zvládneme
v čase O(N2) průchodem do hloubky (s hledáním sousedů vyzkoušením
všech) a vyzkoušením všech dvojic. Zkoušení dvojic navíc zahrneme do
toho průchodu. V programu je průchod do hloubky realizován rekurzivní
funkcí navstiv(). Ta bude pro každý vrchol spuštěna určitě právě
jednou, určitě projde celou komponentu a zároveň správně napočítá
počet průsečíků. Jen je si třeba dát pozor, abychom nezapočítávali
průsečíky dvakrát (za páry kružnic (ki,kj) a (kj,ki)).
Toto řešení má časovou složitost O(N2), paměťovou O(N). Existuje ještě jiné o dost složitější řešení používající zametací čáru k dosažení složitosti O((N+V) log N), což je lepší než naše O(N2), pokud je počet průsečíků V<N2/ log N, tedy pro dost „řídké“ konfigurace kružnic. Pro V=O(N2) má ale časovou složitost až O(N2 log N). Paměťová složitost tohoto algoritmu je O(N). Jeho popis by ale byl dost komplikovaný a proto ho neuvádím.
18-5-6 Profilování (Zadání)
Úloha 1: Buď G graf, který vznikne z CFG tak, že zapomeneme na orientaci hran, přidáme hranu mezi vstupním a výstupním blokem CFG, a zahodíme hrany, na které nedáme čítač. Graf G nemůže obsahovat cyklus – počty provedení hran na odpovídajícím cyklu (nebo cestě) v CFG by bylo možné zvyšovat a snižovat bez toho, že bychom ovlivnili libovolný čítač, tedy by nebylo možné pouze z čítačů určit profil. G je tedy les, a má nejvýše N-1 hran, kde N je počet bloků v programu. Proto v původním CFG můžeme vynechat čítač na nejvýše N-2 hranách.
Naopak, pokud vynecháme čítač na libovolných N-2 hranách takových, aby G byl strom, dokážeme počty provedení zbývajících hran dopočítat: protože G je strom, má vrchol stupně jedna (vede do něj jen jedna hrana e). To odpovídá bloku, u nějž neznáme počty provedení pouze jedné z hran, které do něj vstupují nebo z něj vystupují. Součet počtů provedení hran vstupujících do bloku je roven součtu počtů provedení hran, které z něj vystupují, tedy dokážeme dopočítat počet provedení hrany e. Hranu e vyhodíme z G a tento postup opakujeme, dokud neurčíme počty provedení všech hran. Časová i paměťová složitost tohoto algoritmu je lineární.
Úloha 2: Zjevně stačí spočítat počty provedení bloků – pokud hrana vychází z bloku, který se provede n-krát, a provedeme ji s pravděpodobností p, pak výpočet touto hranou projde pn-krát. Mějme blok b, do nějž vstupují hrany e1, e2, … , ek, které vycházejí z bloků b1, b2, … , bk s pravděpodobnostmi p1, p2, … , pk. Počet provedení bloku b je zjevně součtem počtu provedení hran, které do něj vstupují, tedy jestliže je blok b proveden n-krát a bloky bi jsou provedeny ni-krát, pak platí
| k |
| i=1 |
Pokud navíc položíme počet provedení vstupního bloku roven 1,
dostáváme soustavu lineárních rovnic, jejímž řešením je hledaný profil
(samozřejmě, kdybychom chtěli být zcela přesní, je třeba ještě
dokázat, že tato soustava má jednoznačné řešení). Časová složitost
závisí na tom, jak tuto soustavu budeme řešit. Pokud použijeme
Gaussovu eliminaci, dostáváme kubickou časovou složitost, což je
v praxi příliš mnoho. Proto se většinou používají algoritmy, které
využívají toho, že CFG má speciální strukturu – pokud se nepoužije
příkaz skoku goto, každý cyklus má právě jeden vstup.
V případě, že goto použijeme a tuto podmínku porušíme, tyto
algoritmy vrátí pouze přibližné řešení, zato však fungují v lineárním
čase.