První 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-1-1: Zlaté časy
- 19-1-2: Čokoláda
- 19-1-3: Tiskárna
- 19-1-4: Mafiánské rodiny
- 19-1-5: Zámek
- 19-1-6: Prolog
19-1-1 Zlaté časy (Zadání)
Přesprst by měl radost, jelikož poměrně hodně z vás přišlo na to, že úloha je řešitelná v lineárním čase. Jak tedy na to? Budeme se koukat, kde by začínalo zlaté období, pokud končí nějakým pevně zvoleným záznamem. Když projdeme všechny možné konce, tj. všechny záznamy, tak určitě na zlaté časy musíme jednou narazit.
Na nalezení začátku zlatých časů při pevně zvoleném konci existují tři postupy, které vedou ke třem různě efektivním programům:
1) Triviální postup je zkusit všechny možné začátky a vybrat z nich největší. To vede na kvadratické řešení.
2) Jak si někteří z vás uvědomili, tak součet podposloupnosti záznamů je možno rychle zjistit, pokud známe součet prvních x záznamů (označme ho Sx). Pak již součet posloupnosti mezi záznamy x a y je Sy - Sx-1 (pokud za S0 považujeme nulu). Pokud ale máme pevně zvolený konec y, tak začátek zlatých časů je zřejmě takové x < y, pro které je Sx-1 nejmenší.
Bohužel všechna řešení, která se postupnými součty zabývala, se v tomto bodě vrátila k výše uvedenému triviálnímu postupu a postupné součty používala jako pomůcku pro výpočet součtu intervalu záznamů. Nicméně v tomto místě lze postupovat i jinak. Nalezení minima - to se nejlépe udělá pomocí haldy. Budeme si tedy udržovat haldu, ve které budeme mít Sx-1 pro všechny x < y (y je opět konec).
Budeme-li teď chtít zjistit optimální začátek, zvládneme to v O(1). Při přechodu od y k y+1 budeme muset do haldy přidat záznam Sy, to jde v O(log N). Celkově tedy získáme řešení pracující v čase O(N · log N).
3) No a nyní slibované řešení pracující v lineárním čase. Pro jeden záznam je řešení triviální. Uvažujme tedy, že známe zlaté časy, které končí záznamem y (označme začátek Zy)a ptáme se, jak vypadají zlaté časy končící záznamem y+1.
Platí, že stačí buď pokračovat od minulého začátku Zy, nebo začít až aktuálně zpracovávaným záznamem y+1. Víme, že součet od Zy do y je největší možný součet končící záznamem y. Pokud je tento součet kladný, nemá cenu vzít kratší součet, který by byl menší. Naopak je-li tento součet záporný, neexistuje žádný kladný součet končící v y a je tedy vždy lepší začít od právě zpracovávaného prvku.
Algoritmus tedy funguje tak, že počítá postupně nejlepší součty končící záznamem y (na začátku nastaví na 0). Poté vždy načte další prvek a je-li aktuální součet kladný, přičte k němu načtený prvek. Byl-li aktuální součet záporný, přiřadí do něj načtený prvek. Poté vždy zkontroluje, zda není aktuální součet nejlepší možný.
Tento postup nám v každém kroku zabere O(1) času, tedy celková složitost algoritmu je O(N).
19-1-2 Čokoláda (Zadání)
Podle počtu došlých řešení vás úloha zřejmě zaujala. Otázka je, zda z důvodů ryze matematických, či spíše vidinou důkladného testování svých domněnek a teorií. Pravdou je, že jste se ke správnému výsledku dobrali téměř všichni. Bohužel, ne všichni jste správný výsledek i dokázali. Jaké je tedy řešení?
Mějme čokoládu o velikosti m×n, například oříškovou. Všimněme si, že na začátku je v jednom velkém lákavém kuse, zatímco po nalámání na kostičky je těchto kousků m·n, přestože jsou neméně lákavé. Jistě souhlasíte, že ať rozlomím libovolný kousek čokolády na dva, celkový počet kousků čokolády se zvětší právě o jedna. Žádný kousek se mi nemůže ztratit, pokud vydržím neujídat, a tak potřebuji právě m·n - 1 lámání, abych rozlámal čokoládu na kostičky, ať budu lámat v libovolném pořadí.
Program je opravdu jednoduchý. Stačí načíst vstup a vypsat výsledek násobení. Vše stihneme v konstantním čase i paměti.
19-1-3 Tiskárna (Zadání)
Sešel se nám velký počet řešení této úlohy a velký počet byl i použitých algoritmů. Nejčastějším postupem bylo nalézt dvě stejné bankovky, odstranit je a pokračovat, dokud nezbude jedna nespárovatelná. Tato řešení ale měla kvadratickou časovou složitost. Kdo se zamyslel nad tím, jak tiskárna funguje (tedy, že na vstupu jsou jednotlivá čísla v počtech 1,2,4,8,16 atd., jinými slovy, že počet navzájem různých čísel je pouze log2 (N+1)), odstranil všechny stejné bankovky najednou a zlepšil tím časovou složitost na O(N log N). Kdo spočítal počet výskytů jednotlivých bankovek a vypsal tu, která se vyskytla právě jednou, dosáhl sice stejné časové složitosti, ale paměťovou touto úpravou zlepšil na logaritmickou. Ten, kdo předchozí postup upravil tak, že si bankovky nepamatoval v poli, nýbrž v trii (neznalí a zvědaví najdou stručný popis trií v řešení úlohy 17-3-2), dosáhl časové složitosti lineární.
My si ale ukážeme řešení, které pracuje rovněž v lineárním čase, ale
na rozdíl od trií má paměťovou složitost konstantní. Začněme
jednoduchým pozorováním: prvním znakem sériového čísla hledané
bankovky je ten, který se mezi všemi prvními znaky všech bankovek jako
jediný vyskytuje „liše-krát“. Stejné pozorování můžeme uplatnit i
na zbylé znaky, a tak snadno najít hledané číslo. Jediný problém,
který nás může trochu potrápit je ten, že čísla bankovek nejsou stejně
dlouhá. Ten ale snadno vyřešíme tak, že kratší čísla dorovnáme nějakým
pevným znakem (třeba chr(0)) na délku nejdelšího z nich. Teď už
jenom stačí vytvořit pole 100×36 (100 je maximální délka bankovek a 36
je počet možných znaků) a jedním průchodem přes všechny bankovky
spočítáme počet výskytů jednotlivých znaků na daných pozicích. Nakonec
stačí vypsat řešení. Požadované časové i paměťové složitosti jsme už
sice dosáhli, ale problém jde řešit ještě jinak a elegantněji.
Na to, abychom našli jediný znak, který se vyskytuje „liše-krát“,
totiž nemusíme počítat počet výskytů všech znaků. Kdybychom dokázali
jednotlivé znaky jednoduše párovat, tak ten, na kterého nezbyl
partner, je náš hledaný. A párovat znaky jednoduše umíme – jediné, co
potřebujeme, je operace XOR. Tato operace se aplikuje na dvě
čísla o stejném počtu bitů. Výsledný i-tý bit dostaneme pomocí
i-tých bitů původních čísel pomocí následující tabulky:
| XOR | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 0 |
Z této tabulky plynou následující pravidla:
- a
XOR0 = a - a
XORa = 0 - (a
XORb)XORc = aXOR(bXORc) - a
XORb = bXORa
Z rovnic 1) a 2) vyplývá, že dva stejné znaky se navzájem zruší (spárují) a dál nepřekáží, a z rovnic 3) a 4) plyne, že nám nezáleží na vstupním pořadí znaků.
A to je vlastně celé. Stačí postupně seXORovat všechny znaky
a vypsat to, co nám zbylo. Časová složitost je O(N) a paměťová
O(1).
Poznámka na závěr: V odhadech složitostí jsem neuvažoval délku sériových čísel bankovek, neboť podle zadání je shora omezená 100 znaky, což je konstanta. Pokud by takové omezení neexistovalo, musela by se do odhadů jejich délka samozřejmě zahrnout.
19-1-4 Mafiánské rodiny (Zadání)
Kriminalisté řešící tuto úlohu se až na pár výjimek rozdělili na čtyři tábory: Barviči, Třídiči, Prohledávači a Teoretici. A jaké byly jejich detektivní postupy?
Barviči si řekli, že na to půjdou přímočaře. Na počátku prohlásili, že každý mafián je samostatná rodina a také ho příslušně obarvili. Pak pročítali záznamy, a když zjistili, že záznam spojuje dvě rodiny, jednu z nich přebarvily na barvu té druhé. Barviči nepoužívali žádné jiné triky a tak jejich snažení zabralo O(N2) času.
Třídiči si všimli zajímavého faktu, že když se záznamy setřídí vzestupně podle prvního čísla, stačí si pamatovat u každého mafiána, zda jsme ho již viděli nebo ne. Při následném procházení záznamů inkrementujeme počet rodin pokaždé, když narazíme na dvojici, ze které jsme oba mafiány ještě neviděli. Málem zamotali hlavu i samotnému Přesprstovi, protože toto řešení sice funguje pro vzorový vstup, avšak již jednoduchá hříčka: 1-3, 2-4, 3-1, 3-4, 4-2, 4-3 zamotá Třídičům hlavu.
Prohledávači pochopili velice rychle, že záznamy lze převést na graf a že každá rodina bude v tomto grafu představovat jednu komponentu souvislosti. A tak vyzbrojeni znalostmi z programátorské kuchařky, počali Prohledávači prohledávat. Někteří to vzali zeširoka, jiní do hloubky, ale všichni se zdárně dopracovali k řešení v čase O(M+N), čili O(N).
Nejvypečenější skupinka řešitelů zapojila všechny své teoretické znalosti grafů a vyplodila nejlepší řešení. To si teď ukážeme podrobněji:
Představme si mafiány jako vrcholy grafu a hrany jako vztahy mezi nimi. Nevíme, které hrany představují nadřízenost a které podřízenost, takže necháme graf neorientovaný. Protože má každý mafián právě jednoho nadřízeného a zároveň existuje kmotr, který nadřízeného nemá, musí být tento graf stromem. V případě, že je rodin více, bude graf nesouvislý a tudíž bude lesem, kde každá rodina představuje samostatný strom.
Strom na N vrcholech má tu krásnou vlastnost, že obsahuje právě N-1 hran. Pokud jednu hranu ze stromu odebereme, rozpadne se na právě dva stromy (důkaz si dovolím vynechat - stačí si to trochu promyslet). Když odebereme ze stromu k hran, rozpadne se na k+1 stromů (důkaz indukcí z předchozího tvrzení). Takže pokud máme les na N vrcholech, který má dohromady M hran (M <= N-1), tak víme, že je složen právě z N-1 - M + 1 = N - M stromů. Pro zjištění počtu komponent lesa nám tedy stačí znalost počtu vrcholů a počtu hran.
Budeme tiše předpokládat, že mafiáni jsou číslováni souvisle (tzn. pokud máme N mafiánů, tak jsou číslováni od 1 do N). Bohužel ale nevíme, kolik mafiánů je. Při čtení záznamů tedy zjistíme dvě věci: jednak kolik záznamů (tzn. hran) vlastně máme a zároveň si budeme držet největší číslo dosud nalezeného mafiána (což bude zároveň počet mafiánů). Počet hran (záznamů) následně vydělíme dvěma, protože záznamy udržují informace o podřízených i nadřízených a každá hrana se tam vyskytne právě dvakrát - jako (u,v) a (v,u). Nyní máme potřebné údaje a po odečtení počtu záznamů od počtu mafiánů dostaneme, kolik rodin ve městě vlastně je.
Časová složitost algoritmu je lineární, musíme totiž všechny záznamy přečíst a nalézt v nich maximum. Paměťová složitost je konstantní, protože si nepotřebujeme ukládat všechny záznamy, ale vystačíme si pouze s jejich počtem a největším indexem mafiána. Všimněte si, že pokud bychom znali dopředu počet záznamů a počet mafiánů, tak jsme schopni určit počet rodin v konstantním čase O(1), aniž bychom museli záznamy číst.
Tímto vám Přesprst děkuje za příkladnou spolupráci s policií a přeje vám hezký den.
19-1-5 Zámek (Zadání)
Mnozí z vás zřejmě přehlédli, že životní styl Přesprsta mu nejspíš neumožní žít ještě stovky, tisíce, miliony…let, a tak vyprodukovali správná řešení, která však už pro kódy délky 20 poběží asi tři tisíce miliard let a je poměrně pravděpodobné, že tohoto výsledku se nedočkáme ani my. Jak jistě správně tušíte, mluvím o řešeních, která zkoušela všechny možnosti procházením do hloubky, což jistě výsledku vede vždy. A tak jen maličkou poznámku. Každé volání procedury spotřebovává jisté množství paměti (lokální proměnné, kam se má vrátit po skončení procedury atd.). Z toho plyne, že tyto programy, krom jiného, potřebují paměť úměrnou hloubce rekurze a je třeba ji v odhadech paměťové složitosti uvažovat. Protentokrát jsem za to body nestrhával, protože mi to nepřipadá jako úplně intuitivní věc, ale příště už tak milosrdný (laskavý, hodný…seznam můžete libovolně a vhodně prodloužit :-)) nebudu.
Vzorové řešení se opírá o myšlenky dynamického programování. Pokud si nyní myslíte, že vám nadávám, přečtěte si, prosím, kuchařku v 17. ročníku série první a potom pokračujte. Základní chybou vašeho výše uvedeného řešení bylo, že opravdu generovalo všechna řešení, ale to po nás nikdo nechtěl, protože jenom vypsat všechna možná řešení trvá do skonání světa. Nám ale stačí počet možných řešení. To nás přivádí na velmi zajímavou myšlenku. Pokud totiž bude aktuální kombinace končit (třeba) na trojku, tak číslice, které mohu připojit, jistě nejsou ovlivněny tím, co té trojce předcházelo. Toto jednoduché pozorování, které přímo plyne ze zadání, nám umožňuje pohlédnout na věc dynamicky. Vezměme si nějakou kombinaci délky n, která končí na číslici c. Z té lze vytvořit kombinace délky n+1 končící na c1,c2,… , ck, kde c1 až ck jsou možní následníci c. A díky našemu pozorování víme, že toto můžeme udělat se všemi kombinacemi délky n, které končí na c, protože nám je jedno, co tomu c předcházelo.
Stačí si tedy pro každou cifru pamatovat pouze počet kombinací končících na tuto cifru. A jak provedeme samotný výpočet? Vytvořme si tabulku, kde v n-tém sloupci a c-tém řádku je uložen počet kombinací délky n končící na cifru c. V prvním sloupci jsou samé jedničky (kombinace délky jedna „končící“ na určitou cifru je vždy právě jedna). Když teď budeme chtít spočítat (n+1)-ní sloupec, tak jednoduše pro každou cifru c do políček c1 až ck přičteme počet kombinací končících na c. V (n+1)-ním sloupci tak bude po dokončení výpočtu pro každou cifru uložen počet kombinací, ke kterým může být cifra připojena a to je přesně to, co jsme chtěli. Na konci výpočtu jen počty kombinací končících na jednotlivé cifry sečteme a tím získáme výsledek. Pokud si navíc všimneme, že celou dobu používáme jen poslední sloupeček tabulky, paměťová složitost kvadratická ku počtu cifer (na uložení následníků) nás nemine. Odhady složitostí tedy jsou O(KL2) a O(L2), kde L je počet cifer (byť ze zadání plynulo, že je to konstanta. Moje chyba.) a K je délka kombinace.
19-1-6 Prolog (Zadání)
1. Tchyně
Co dodat… úloha byla opravdu jednoduchá. Ukázalo se, že pro většinu programátorů byl největší problém vyznat se v rodinných vztazích.
Ale přesto nebyla úložka až tak lehká, jak by se mohlo zdát. Problém
nastal u predikátu manzelstvi(X,Y). Můžeme se totiž dohodnout, že
první bude vždy muž a predikát tedy bude vypadat jako
manzelstvi(Manzel, Manzelka)(nebo naopak, to je jedno). Pak samozřejmě musíme
v predikátu tchyne(Tch,X) otestovat, zda X je muž nebo žena,
abychom ho dosadili na správné místo v predikátu manželství. Pokud se
nechceme rozhodovat, v jakém pořadí budeme manžele a manželku do
predikátu manzelstvi zadávat, nebo to nevíme, musíme vyzkoušet
zavolat predikát manzelstvi dvakrát, pokaždé s prohozenými
argumenty, aby se chytil a uspěl ten správný zápis pořadí partnerů.
2. Oprava
Úložka za 3 body, ale zdání klame, čeká nás divoký rekurzivní hon. Držte si klobouky, pojedeme z kopce!
Snad každý ihned odhalil, co je na zadaném programu špatně. Predikát
predek nemá, jak kdosi poznamenal, „šanci dostat se
z rekurze“. Prolog neustále vyhodnocuje predikát predek a ten
donekonečna volá sám sebe. Predikát rodic za ním se nikdy
nevyhodnotí, nikdy nedojdeme na dno rekurze.
Nu dobrá, ale jak z toho ven? Možné byly dva postupy:
První postup: Snažím se dno rekurze dostat dopředu, aby se vyhodnocovalo jako první, tedy přehodím řádky a program vypadá následovně:
Kdo si tento program alespoň jednou spustil, hned pochopil, že
takovéto prohození řádku na opravu ještě není dostatečné. Pokud zadáme
existující dvojici Pred a Pot, predikát funguje. Stačí ale, aby
nějaký zlomyslník zadal dvojici, která není navzájem ve vztahu předka
a potomka a program se zacyklí. Správně by ale jako slušně vychovaný
prologovský program měl odpovědět No.
Na toto se nachytalo hodně řešitelů, a proto vysvětlíme, co se děje
špatně: Zadáme-li neexistující dvojici Pred a Pot, první řádek
programu se nepovede. Prolog skočí na další řádek a snaží se jej
naplnit. Ale tam se zacyklí v marném hledání uspokojivé dvojice pro
predikát predek a k vyhodnocení predikátu rodic nikdy nedojdeme.
Musíme tedy ještě prohodit predikáty predek a rodic na druhém řádku a dostaneme:
Druhý postup: Nechám řádky tak, jak jsou a jednoduše prohodím predikáty. Dostanu:
Tohle překvapivě také funguje, pouze vydává výsledky při odmítání středníkem v jiném pořadí.
3. Evoluce
Ani tato úložka nebyla záludná pro toho, kdo si přečetl a správně
pochopil predikát predek a rozmyslel si správně rekurzi.
Plán řešení bude následující: Pro obě rostliny z predikátu
stejny_druh(X,Y) najdeme jejich nejpůvodnější předky a porovnáme je.
Napišme si tedy predikát prarost(PraX,X), který pro rostlinu X
najde jejího nejpůvodnějšího předchůdce. Můžeme k tomu použít třeba nám
dobře známý predikát predek, ale nejdřív si ho trošku upravíme. Tak,
jak máme predikát předek napsán teď, je pro nás nevýhodný. Podívejme
se na jeho rekurzivní část:
Takto napsaný predikát vezme daného předka, najde k němu mladšího předka, k němu ještě mladšího předka, až dojde k hledanému potomkovi. Postupujeme tedy ve stromě shora dolů a můžeme se dostat do všech možných potomků daného předka. Tento dotaz se hodí, pokud bychom chtěli opravdu vyhledávat všechny potomky, ale nás by toto zdržovalo, a tak napíšeme predikát opačně, půjdeme ve stromě zdola nahoru:
Vidíte ten rozdíl? K danému potomkovi najdeme jeho rodiče a postupujeme stromem rekurzivně přímo nahoru, nezabýváme se nějakými vedlejšími větvemi.
Ještě potřebujeme dopsat dno rekurze. Kdy skončíme prohledávání? Tady byl kámen úrazu většiny řešitelů. Většina totiž napsala:
Pokud zadáme do takto napsaného predikátu rostlinu, která je již původní, samozřejmě neuspěje. Nesmíme tedy rekurzi zastavit příliš brzy, musíme ji nechat doběhnout až k původnímu druhu:
Pozor také na konstrukci Pr=Pot. Správně bychom měli psát:
Jak víme, X se správně zunifikuje, pokud se splní predikát je_puvodni_druh(X)..
Důvod, proč tyto „triviality“ tak podrobně rozebírám je ten, že víc jak polovina řešitelů udělala jednu nebo druhou chybu.
A když teď máme predikát predek hotový, zbytek je hračka:
Existuje ještě jedno pěkné řešení, které vůbec nepoužívá predikáty
predek ani je_puvodni_druh. Obě řešení najdete ve zdrojovém
programu.