Třetí série dvacátého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 20-3-1: Platba koně
- 20-3-2: Dva lupiči
- 20-3-3: Cesta z kopce
- 20-3-4: Orientace na mapě
- 20-3-5: Asfaltování
- 20-3-6: Hrady, hrádky, hradla
20-3-1 Platba koně (Zadání)
Napřed provedeme malý trik. Každá hodnota je s přesností na 2 desetinná místa. Když všechny hodnoty vynásobíme 100 (tedy, převedeme z Korun na Haléře), dostaneme celá čísla, se kterými se mnohem lépe pracuje. Mimo to, ne každý handlíř umí pracovat s desetinnými čísly.
Nyní si na chvíli představme, že handlíř je naprosto chudý a nemá ani vindru (tedy, jeho hromádka na vracení je prázdná). Mimo to, je rozumné mít pouze kladné mince a kladnou cenu koně (i když, u některých koní…).
Jak by se dal řešit takový problém? Půjdeme na to od lesa. Rozdělíme to na fáze a chceme po k-té fázi vědět, které všechny obnosy lze zaplatit pomocí k prvních mincí.
Stav na začátku, tedy po nulté fázi, je jasný. Dokážeme zaplatit jedinou částku a to 0.
V každé fázi vezmeme minci o hodnotě h a vedle každé částky zaplatitelné pomocí k-1 prvních mincí přidáme do naší množiny ještě částku zvětšenou o h.
Z tohoto již lze snadno poznat, že daná částka jde zaplatit. Jednoduše se bude vyskytovat v množině. Jak ale poznat, kterými mincemi ji máme zaplatit? Při přidávání každé částky do množiny si k ní připíšeme také, ze které částky vznikla. Odečtením získáme poslední použitou minci a když se podíváme na onu předchozí částku, tak můžeme obdobným způsobem zrekonstruovat předchozí minci, až se dostaneme na začátek.
Musíme vyřešit, jak budeme reprezentovat tuto množinu. Všimneme si, že veškeré hodnoty jsou celá čísla a proto i jejich součty budou celá čísla. Navíc, nikdy nebude menší než 0 a větší, než součet všech Vildových mincí sv. Můžeme použít pole, jehož indexy budou čísla 0… sv, v každé fázi toto pole projít a poznamenat do něj hodnoty nové.
Dále je třeba zajistit, aby námi vybraná možnost byla ta, která má nejméně použitých mincí. Inu, zavedeme tuto podmínku do každé fáze, tedy na konci k-té fáze budeme mít všechny zaplatitelné obnosy a každý na nejmenší počet mincí. Když budeme chtít poznamenat, že lze zaplatit nějaká hodnota a tato hodnota již zaplatit jde, tak ji přepíšeme na novou jen v případě, že je tato nová na méně mincí. Zřejmě to funguje, neboť ta s nejmenším počtem možností buď používá k-tou minci a nebo nepoužívá, což je přesně to, co ověřuje tato podmínka.
Poslední problém, který je třeba vyřešit, jsou handlířovy mince. Jednoduchým trikem je sesypeme do stejného pytle jako mince Vildovy, jen je všechny vynásobíme číslem -1. Tento trik vypadá jednoduše, ale je třeba vyřešit několik detailů. Hlavním z nich je rozsah pole. Již není pravda, že by součet některých mincí nemohl být záporný. Avšak, když vyzkoušíme napřed všechny kladné mince a potom nám už zbudou jen záporné, tak zaznamenávat, že umíme zápornou částku k ničemu není, neboť ji již nikdy nad nulu nedostaneme.
Stejně tak si rozmyslíme horní hranici. Určitě se nikdy nedostaneme nad součet všech Vildových mincí. Ale také nemá nikdy cenu ukládat částky, které přesahují cenu koně a součet handlířových mincí dohromady, takové částky již nedokážeme dostatečně snížit, i kdyby handlíř vrátil vše, co měl. Stačí tedy vzít minimum z těchto dvou hodnot.
Označme toto minimum jako μ. Potom paměťová složitost je očividně O(μ+M+N), kde N a M jsou počty mincí na jednotlivých hromádkách. Časová složitost je O(μ·(N+M)), neboť pro každou minci proběhne jedna fáze a v každé fázi projdeme celé pole.
20-3-2 Dva lupiči (Zadání)
Máme čtyři výroky lupičů, a každý z nich nějakým způsobem omezuje možné dvojice čísel. Projdeme si tyto omezující podmínky jednu po druhé. Označme si velitelova čísla jako x, y; víme, že 2≤ x,y≤ 99.
První věta nám říká, že součin xy jde rozložit na součin dvou čísel více než jedním způsobem. To znamená, že xy je součin alespoň tří prvočísel, která nejsou všechna stejná. Označme A1 množinu všech těchto povolených součinů.
Druhá věta nám říká, že ať součet x+y rozložíme na součet dvou čísel jakkoliv (čímž získáme řekněme čísla α,β∈<2,99>, kde α+β=x+y), vždycky bude součin αβ ležet v množině A1. Množinu všech součtů, které toto splňují, označme B1.
Z třetí věty víme, že součin xy jde rozložit na součin dvou čísel α,β tak, aby α+β∈B1, právě jedním způsobem. Množinu všech součinů, které tuhle podmínku splňují, označíme A2.
A poslední věta nám říká, že součet x+y jde rozložit na součet dvou čísel α,β tak, aby αβ∈A2, právě jedním způsobem. Množinu všech součtů, které to splňují, označíme B2.
Chceme teď najít všechna čísla x,y taková, že xy∈A1∪A2 a x+y∈B1∪B2. Tím jsme úspěšně formulovali problém matematicky, ale jak ho vyřešit? Inu, pomocí čtyřech uvedených podmínek vyškrtáme zakázané součiny a součty a uvidíme, co zbude.
Povolené součty jsou v intervalu <4,198>, a chceme z nich vyškrtat ty, které se dají zapsat jako součet dvou prvočísel, nebo jako součet prvočísla a jeho druhé mocniny.
Aby to vyškrtávání zabralo méně času, můžeme využít Goldbachovu hypotézu, která říká, že každé sudé číslo
(větší než dva) je možné zapsat jako součet dvou prvočísel. Sice jde pouze o hypotézu (a slavný otevřený problém), ale na počítači byla její platnost ověřena (alespoň) pro
čísla do 1018. Takže nám stačí škrtnout všechna sudá čísla, a z lichých ta, co jsou o 2 větší než nějaké prvočíslo. A součet prvočísla a jeho druhé mocniny je vždycky sudý.
Pozor, je tu jedna záludnost. Potřebujeme, aby ta dvě prvočísla byly přípustné hodnoty čísel x,y, tedy aby byla v intervalu <2,99>. Může se nám stát, že číslo sice rozložíme na součet dvou prvočísel, ale pokud jedno z těch prvočísel bude moc velké, stále se jedná o přípustný součet. Na druhou stranu součiny jako 99·99 přípustné nejsou, i když jde o součin alespoň tří prvočísel, která nejsou všechna stejná.
Teď projdeme všechny dvojice čísel z intervalu <2,99> (možné součiny). Rovnou škrtneme součin dvou prvočísel a třetí mocninu prvočísla. A nakonec projdeme všechny dělitele d možného součinu s a podíváme se, jestli existuje právě jeden dělitel d tak, že součet d+s/d je v množině B1 povolených součtů.
A zbývá aplikovat poslední podmínku. Projdeme si množiny povolených součtů a pro každý z nich si najdeme všechny jeho rozklady na součet dvou čísel α,β z intervalu <2,99>. Pokud mezi všemi rozklady existuje právě jeden, pro který je součin αβ povolený (nevyškrtnutý), našli jsme řešení.
Pro ruční procházení je těch možností docela hodně, a tak se vyplatilo napsat si program. Pro výpočetní sílu počítače je však jejich počet nepatrný, a proto dáme přednost jednoduššímu kódu před optimalizacemi pomocí prvočísel.
Nuže konečně uvedu dlouho očekávaný výsledek, úlohu řeší právě dvojice čísel {4,13}.
20-3-3 Cesta z kopce (Zadání)
Úloha jde nelépe vyřešit, jak si drtivá většina z vás všimla, v čase O(N). Budeme hledat nejdelší podposloupnost končící nějakým členem posloupnosti A, která splňuje zadání (v dalším textu podposloupnost znamená podposloupnost splňující zadání, tedy obsahující nejvýše k stoupání). Začneme s podposloupností obsahující jen zvolený prvek a její začátek postupně posunujeme směrem k počátku posloupnosti A. Dokud podposloupnost obsahuje méně než k stoupání, je všechno v pořádku. Jakmile ji ale rozšíříme tak, že už má právě k stoupání, musíme pokračovat opatrně, abysme nepřidali další stoupání. Skončíme tedy těsně za nějakým stoupáním (na druhém prvku z rostoucí dvojice), které by už překročilo limit, případně na začátku celé posloupnosti A. Pokud takto najdeme nejdelší podposloupnost pro každý prvek z A, bude mezi nimi určitě hledaná celkově nejdelší. Obdobnou úvahou při posunování konce podposloupnosti místo začátku zjistíme, že konec hledané podposloupnosti bude těsně před nějakým stoupáním, případně na konci celé posloupnosti.
Když obě úvahy spojíme dohromady, zjistíme, že není třeba hledat začátek a konec podposloupnosti jinde než u stoupání a na úplném začátku nebo konci. Najdeme si tedy všechna stoupání v posloupnosti A a pro každé z nich hledáme nejdelší podposloupnost, která končí těsně před ním. Pokud právě zkoumané stoupání, bude i-té, tak pro začátek podposloupnosti musíme přeskočit k stoupání a bude tedy ležet hned za (i-k-1)-tým. Hodnoty i ≤ k vůbec nemusíme uvažovat, protože u nich končící podposloupnosti budou začínat prvním prvkem A, stejně jako pro i = k+1, pro nějž bude délka větší než pro všechna menší i.
Z výše uvedeného vyplývá, že pro zjištění výsledku si vůbec nemusíme pamatovat hodnoty A, kromě dvou posledních k zjištění stoupání. Navíc stačí znát jen k+1 stoupání před aktuálním, jelikož stoupání k+1 míst před právě zkoumaným potřebujeme v tomto kroku a následující budeme potřebovat v dalších krocích. Hledání nejdelší posloupnosti pak může probíhat přímo při hledání stoupání. Nejdříve si zapamatujeme prvních k+1 stoupání a pak vždy když najdeme další, zkontolujeme délku podposloupnsti, která u něj končí a začíná u nejstaršího stoupání, které si pamatujeme, což je právě to k+1 míst před aktuálním. Toto nejstarší stoupání pak zapomeneme a zapamatujeme si právě nalezené. Taková datová struktura se nazývá fronta. Nakonec si ještě musíme dát pozor, pokud je počet stoupání nejvýše k, abychom za řešení přijali celou posloupnost.
Časová složitost je O(N), protože procházíme jedenkrát zadanou posloupnost a pro každý její prvek provádíme konstantně mnoho operací. Paměťová složitost je O(k), kvůli frontě délky k+1.
20-3-4 Orientace na mapě (Zadání)
Nejprve si nejspíš uvědomíme, že v acyklickém orientovaném grafu musí být alespoň jeden vrchol, do kterého nevede žádná hrana – zdroj. Z každého vrcholu (které není zdroj) můžeme cestou proti směru hran dojít do nějakého zdroje. Proto při hledání vrcholů, mezi nimiž vede nejvíce cest,můžeme předpokládat, že počáteční vrchol je zdroj – kdyby cesty vycházely z jiného vrcholu, můžeme všechny prodloužit až do nějakého zdroje. Tím se jejich počet určitě nezmenší. (Z podobného důvodu bychom také mohli hledat koncové vrcholy pouze ve stocích – vrcholech z nichž nevede žádná hrana.)
Vzápětí si uvědomíme, že zdrojů v grafu může být mnoho, takže nám tohle pozorování práci neušetří a algoritmus nezlepší, ale využít ho můžeme…Z každého zdroje tedy spočítáme cesty do jednotlivých vrcholů.
Máme-li pro nějaký vrchol v spočíst počet cest z určitého zdroje, lze to udělat tak, že sečteme počty cest do všech vrcholů, ze kterých vede hrana do v. K tomu ovšem musíme tyto počty cest znát. Proto je nutné počítat cesty do vrcholů ve správném pořadí – v topologickém pořadí (o němž se píše v kuchařce ke třetí sérii). Topologické pořadí určíme například tak, že projdeme graf ze zdroje do hloubky a pamatujeme se pořadí, ve kterém jsme naposled opouštěli jednotlivé vrcholy - tímto způsobem je dostaneme setříděné pozpátku – zdroj bude úplně poslední, takže musíme počítat počty cest do vrcholů od konce. Když máme spočítané cesty do všech vrcholů, zapamatujeme si maximální počet cest (a kam vedly) a prozkoumáme cesty z dalšího zdroje. Pak už stačí jenom vybrat zdroj, z něhož vede nejvíce cest.
Jak to všechno bude složité? Na jednotlivé průchody do hloubky potřebujeme O(N+M) času. Počet potřebných průchodů závisí na počtu zdrojů v grafu, může být až O(N). Celkem se dostáváme na časovou složitost O(N·(N+M)). Paměťová složitost vzorového řešení je O(N2), protože si seznamy sousedů pamatuje ve zbytečně dlouhých polích, při šikovnějším způsobu by stačilo O(N+M).
20-3-5 Asfaltování (Zadání)
Zdravím všechny řešitele upatlané od asfaltu. Mám pro vás dobrou zprávu: Nebojte, za pár měsíců se to oloupe. A nyní vám přinášíme exkluzivně algoritmus od samotného vrchního cestáře, který nám jej (samozřejmě pod pohrůžkou mučení) vyzradil.
Nejprve si naši úlohu převedeme do řeči grafů. Města představují vrcholy, cesty mezi nimi budou hrany, a protože lze cestovat po celé Hipopotámii, bude graf souvislý. Chceme najít párování hran takové, aby každá hrana byla spárovaná a dvě spárované hrany měly společný vrchol. Nedá mnoho přemýšlení, že zmíněné párování nemůže existovat, pokud je počet hran lichý. Od teď se tedy budeme zabývat pouze grafy, které mají sudý počet hran.
Klíčem k řešení našeho problému bude algoritmus prohledávání do hloubky, též známý jako DFS (Depth First Search). Podívejme se, jak bude vypadat situace vstoupíme-li při procházení do vrcholu u. Nejprve zpracujeme všechny dosud nenavštívené sousedy vrcholu u, jak nám káže algoritmus DFS. Následně se podíváme, s kolika nespárovanými hranami vrchol inciduje. Je-li jich sudý počet, můžeme spárovat hrany libovolně mezi sebou. Pokud jich je lichý počet, necháme hranu vedoucí k otci (k vrcholu, ze kterého jsme do u přišli při DFS) nespárovanou (taťka se nám o ni postará) a zbývající hrany, kterých už je sudě, opět libovolně spárujeme.
Zbývá ukázat, že u vrcholu s, ve kterém jsme prohledávání započali, budeme mít na konci algoritmu sudý počet nespárovaných hran. Kdyby tomu tak nebylo, měli bychom problém, protože s už nemá žádného „taťku“, který by mu pomohl vyřešit problémy s lichou hranou. Naštěstí ale víme, že na začátku máme sudý počet (nespárovaných) hran. Při párování nám ubývají nespárované hrany vždy po dvou, takže se zachovává jejich sudý počet. V okamžiku, kdy se vrátíme v DFS zpět do vrcholu s, můžou být nespárované pouze hrany incidující s s. A protože jich je celou dobu sudý počet, můžeme je vesele spárovat.
Budeme-li reprezentovat graf seznamem sousedů, je časová i paměťová složitost algoritmu O(N+M), kde N je počet vrcholů a M je počet hran.
Přeji vám pěkný den a pokud možno hladké asfaltové cesty.
20-3-6 Hrady, hrádky, hradla (Zadání)
V minulé části seriálu jste měli za úkol vymyslet obvod, který zjistí, zda-li je číslo na vstupu dělitelné třemi. Než začneme s vymýšlením obvodu, podíváme se na to, jaké zbytky po dělení třemi dávají číslice ve dvojkovém zápisu.
| pozice číslice | 0 | 1 | 2 | 3 | … |
| hodnota desítkově | 20 | 21 | 22 | 23 | … |
| modulo třemi | 1 | 2 | 1 | 2 | … |
| zapsáno dvojkově | 1 | 10 | 1 | 10 | … |
Vidíme, že se zbytek opakuje periodicky a pro liché pozice dostáváme zbytek 110 = 012 a pro sudé zbytek 210 = 102. Formálně lze toto pozorování dokázat indukcí, pro liché pozice dostáváme n0 = 20 = 1, nk = 2(2k+1), nk+1 = 2(2k+3), pak nk+1 = 4·2(2k+1) = 3·2(2k+1) + 2(2k+1) Vidíme tedy, že pro další číslici platí, že je součtem něčeho krát tři, což má jistě zbytek po dělení třemi nula, plus předchozí číslice, aplikováno "rekurzivně" dostáváme, že všechny číslice na lichých pozicích mají stejný zbytek modulo třemi. Pro sudé pozice je důkaz podobný. A teď už dost formalismu a pojďme se podívat dál.
Vidíme, že když si budeme brát vstup po dvojicích, ty sečteme, pak bude toto číslo dělitelné třemi právě tehdy když bylo dělitelné třemi číslo původní. Což odpovídá tomu, že sečteme zbytky na lichých pozicích plus zbytky na sudých pozicích krát dva a = a0 + 2·a1 + 4·a2 + …+ 2n-1·an-1 + 2n·an, pak součet zbytků po dělení třemi je S = a0 + 2·a1 + a2 + 2·a3 +…+ an-1 + an = a0,a1 + a2,a3 +…+ an-1,an, kde a,b znamená binární číslo poskládané z binárních číslic a a b, neboť ve dvojkovém zápisu je násobení dvěma posunutí doleva (obdobně jako násobení desíti v soustavě desítkové).
Teď nám už zbývá jenom vymyslet obvod, který sečte dvě dvoubitová čísla modulo třemi. Číslo 00 má stejný zbytek po dělení třemi jako 11. Sčítání je komutativní a proto nám nezáleží na pořadí sčítání, tato operace je tedy jednoznačně určena následující tabulkou. Značka „ ≡ “ zde znamená, že čísla mají stejný zbytek po dělení třemi.
| Vstup A | Vstup B | Výstup |
| 01 | 01 | 10 |
| 10 | 10 | 01 |
| 01 | 10 | 00 ≡ 11 |
| 01 | 00 ≡ 11 | 01 |
| 10 | 00 ≡ 11 | 10 |
| 00 ≡ 11 | 00 ≡ 11 | 00 ≡ 11 |
Když se na tuto operaci pozorně podíváme, zjistíme, že se nápadně podobá obyčejnému sčítání, až na to, že se přenos znovu přičte k výsledku.
Takže máme obvod, který má na vstupu čtyři bity, dvě dvoubitová čísla a na výstupu dva bity, jedno dvoubitové číslo. Nyní stačí tyto obvody poskládat tak, že na každé výpočetní hladině zmenšíme počet dvoubitových zbytků na polovinu. Vstup jako obvykle doplníme dostatečným počtem nul. Číslo pak bude dělitelné třemi, když nám na konci zbyde 11 nebo 00. Jelikož obvod na sčítání má konstantní hloubku má celé zapojení asymptoticky logaritmickou složitost stejně jako obvod na počítání parity z předchozího seriálu.
Rozmyslete si, že pro dělitelnost třemi v zápise BCD bude fungovat stejný postup.