První série patnáctého ročníku KSP

Řešení úloh

• 15-1-1: Narozeninový dort
• 15-1-2: Vláčky
• 15-1-3: Kulový blesk
• 15-1-4: Soustavy
• 15-1-5: Haskell

15-1-1 Narozeninový dort (Zadání)

Úloha patřila mezi těžší, takže řešení přišlo opravdu poskrovnu. Většina z nich fungovala v čase O(N²), a byly tu nějaké (ne příliš úspěšné) pokusy o řešení v čase O(N log N). Ukážeme si vzorové řešení, které běhá v O(N²) a dá se (pravda trochu pracně) upravit na řešení běžící v O(N log N). Za správná kvadratická řešení se vším všudy bylo možno získat 11 bodů, ale této hranice nikdo z řešitelů nedosáhl kvůli nedostatkům v popisech, důkazech a programech. Za nesprávná řešení (pokud šlo jejich drobnou modifikací získat správné řešení) jste mohli dostat až 5 bodů.

Nejprve si trochu přeformulujeme zadání – snažíme se najít bod X v trojúhelníku ABC takový, že v trojúhelnících AXB, BXC i CXA je stejný počet svíček (N/3). Takovému bodu X budeme říkat řešení. Dále si nadefinujeme – pro zjednodušení následujícího textu – jeden pojem: úhlem bodu D trojhelníka ABC vzhledem k nějakému z jeho vrcholů budeme rozumnět úhel XAC v případě vrcholu A, XBA v případě vrcholu B a XCB v případě vrcholu C. Úhel budeme značit U(Vrchol, Bod). Dále je dobré si uvědomit, že trojúhelník lze rozdělit na oblasti, ve kterých jsou buď všechny body řešeními nebo není žádný bod řešením. Pokud totiž povedu přímky ze všech vrcholů trojúhelníku všemi svíčkami, budu mít trojúhelník rozdělen na několik konvexních mnohoúhelníků. Jestliže jeden bod vnitřku je řešením, pak jsou řešením všechny body vnitřku, protože mají stejnou polohu vůči přímkám z vrcholů trojúhelníku a svíčkám, a tedy jsou stejné počty svíček v oblastech, na které se řezem trojúhelník rozdělí. Pořád ale nevíme nic o okrajích těchto konvexních oblastí – o některých z nich můžeme říct, že na nich řešení nemůže ležet, protože by řezalo přes nějakou svíčku, ale mohou nám pořád zbýt nějaké, pro které řešení svíčku řezat nebude. Zbývá nám tedy otázka, co to pro nás znamená. Je však zřejmé, že takové řešení se dá velice nepatrně posunout, aby na takové přímce neleželo (formální důkaz tohoto tvrzení by byl docela zdlouhavý, a musel by se patrně dělat rozborem případů – podle počtu těchto „nežádoucích“ přímek, na kterých naše řešení leží – a následným výpočetním vyjádřením vektoru, o který můžeme řešení posunout, aby se nám rozdělení svíček nezměnilo, ale přitom nové řešení už neleželo na žádné „nežádoucí“ přímce). Naše úloha je tedy ekvivalentní s hledáním řešení v jednotlivých mnohoúhelnících (resp. otestování jednoho libovolného bodu z každého mnohoúhelníku).

Ideově nejjednodušší řešení by tedy mohlo pracovat tak, že si spočítá všechny tyto oblasti a pro každou otestuje např. její těžiště. Dá se dokázat, že oblastí je O(N²) (každá přímka je rozdělena na max. 2N místech, každé takové místo je vrcholem nějakého mnohoúhelníka, a je společné maximálně šesti mnohoúhelníkům, každý má alespoň jeden vrchol, odtud získáme, že počet mnohoúhelníků je maximálně 3N*2N*6 = 36N² = O(N²)). Teoreticky by tedy mohlo být možné vymyslet na základě této myšlenky kvadratický algoritmus, avšak jeho naprogramování by bylo patrně velice komplikované – takže my se raději uchýlíme ke komplikovanějšímu, ale zato na naprogramování ne příliš složitému kvadratickému algoritmu, který se dá zrychlit na časovou složitost O(N log N).

Nyní ještě něco k řešením. Všechna aspoň trochu správná řešení byla založena na docela podobném principu, ale mnohdy jste zapomínali na nějaké „drobnosti“ jako třeba že může být více svíček se stejným úhlem vzhledem k jednomu z vrcholů trojúhelníka apod. – což znamená, že vaše řešení v takovém provedení, jak jste napsali nebude vždy fungovat, i když by (v některých případech) nebylo těžké je upravit na funkční řešení, takže jste většinou nějaký bod dostali. Dále jste často zapomínali na to, že floaty se nedají přímo porovávat na rovnost – mělo by se zjišťovat, zda se neliší pouze o nějaké malé předem dané ε, které vám v zásadě pokrývá odchylky při výpočtech.

Program

Marek Sulovský

15-1-2 Vláčky (Zadání)

„Ejhle, grafová úloha!“ vykřikl železniční černokněžník pan Zababa a vyklepal to samou radostí do drážního telegrafu tak mocně, až vrabci na telegrafních drátech nadskakovali. A hned začal kout pikle, že celý problém šikovně převede na hledání maximálního toku v síti, a to je přeci standardní úloha, kterou ho kdysi dávno na vysoké škole pro dopravní černokněžníky učili. My si z něj ovšem příklad brát nebudeme a necháme už beztak vystrašené opeřence být, nestřílejíce po nich kanónem. A toky v sítích si sice v literatuře najdeme a prostudujeme (určitě se někdy budou hodit), ale raději si zvolíme prostředky poněkud přízemnější, i když teorii toků neupíráme jistou dávku inspirace.

Kontrolním bodům budeme říkat nádraží, jednotlivým kolejím v kontrolních bodech nástupiště a kolejím mezi kontrolními body trati. Celé kolejiště tedy můžeme popsat orientovaným grafem, jehož vrcholy budou odpovídat nástupištím, budou seskupeny do vrstev odpovídajícím nádražím a podle tratí mezi nimi povedou hrany, a to z každé vrstvy jen do té bezprostředně následující (tento směr nazveme zleva doprava). Zkrátka jako na obrázku v zadání. První vrstvě budeme říkat počáteční (do té nevedou žádné hrany), poslední vrstvě koncová (naopak nevedou žádné ven), ostatním vrstvám vnitřní.

Naším cílem tedy bude v tomto grafu najít co nejvíce vrcholově disjunktních cest, tj. cest, které vždy vedou z nějakého vrcholu počáteční vrstvy do nějakého vrcholu koncové vrstvy a žádné dvě cesty nemají společný vrchol. Lépe se nám ovšem budou hledat cesty hranově disjunktní, tak si pomůžeme prostým trikem: každý vrchol v nahradíme dvěma vrcholy v₁ a v₂, přičemž do v₁ povedou všechny hrany, které vedly do v, z v₂ povedou ty, co vedly z v, a navíc přidáme hranu v₁→v₂. Počet vrstev se tím zdvojnásobí. Když nalezneme největší množinu hranově disjunktních cest v tomto novém grafu a vrcholy „stáhneme zpět“, dostaneme největší možnou množinu vrcholově disjunktních cest v původním grafu (rozmyslete si, proč to funguje).

Ještě si všimněme, že nám stačí místo cest nalézt takovou množinu M hran, která je vyvážená, tj. s každým vrcholem ve vnitřních vrstvách sousedí stejný počet hran z M zleva jako zprava. Snadno ověříme, že tehdy je počet hran z M mezi každými dvěma sousedními vrstvami stejný. Pak už M můžeme snadno rozložit na disjunktní cesty hladovým algoritmem: vyjdeme z počáteční vrstvy po libovolné hraně z M, přijdeme do nějakého vrcholu, vydáme se libovolnou další hranou z M doprava (ta musí vždy existovat, neboť M je vyvážená), až dospějeme do koncové vrstvy. Nalezenou cestu z grafu odstraníme, čímž vyváženost neporušíme, a tak mužeme stejný postup opakovat, dokud M nevyprázdníme. A jelikož všechny cesty jsou stejně dlouhé, největší množině disj. cest odpovídá největší vyvážená množina a opačně.

[Odbočka k tokům v sítích: Nyní bychom mohli přidat zdroj z připojený hranami ke všem vrcholům v počáteční vrstvě a spotřebič s, do nějž povedou hrany z vrcholů koncové vrstvy, všem hranám nastavit jednotkovou kapacitu a nalézt (třeba metodou Tří Indů v čase O(n³)) maximální celočíselný tok ze z do s v této síti. Množina hran sítě, po kterých teče nenulové (tj. jedničkové) množství, je právě největší vyvážená.]

A jak na to půjdeme my? Začneme s libovolnou vyváženou množinou hran M (třeba prázdnou, ta je po ruce vždycky) a budeme ji zlepšovat tak dlouho, dokud to půjde, a až to nepůjde, prohlásíme ji za největší možnou. A vymyslíme si ono zlepšování tak šikovně, aby opravdu největší byla.

Definička: Hrany grafu si obarvíme dvěma barvami: Červené budou hrany ležící v M, modré všechny ostatní.

Pro lepší představu: s vrcholy ve vnitřních vrstvách sousedí buďto samé modré hrany nebo dvě červené (jedna zleva a jedna zprava) a všechny ostatní jsou modré (jinak nelze, neboť každý vrchol má z alespoň jedné strany stupeň 1, totiž tam, kde vede hrana přidaná při dělení vrcholů, a cesty v M jsou hranově disjunktní). Analogicky pro hrany v počáteční a koncové vrstvě, až na to, že červená hrana může být jen jedna.

Definice: Zlepšující cestou budeme nazývat takovou cestu, která povede z vrstvy počáteční do koncové, přičemž může používat buďto modré hrany zleva doprava nebo červené hrany zprava doleva. (Není to tedy poctivá orientovaná cesta, ale to nám nebude vadit.)

Pokud existuje nějaká zlepšující cesta, můžeme množinu M určitě vylepšit: stačí, když všechny červené hrany ležící na zlepšující cestě z M odebereme a ty modré naopak přidáme. M tak zůstane vyvážená a její velikost vzroste. Zajímavější ale je opačná implikace:

Věta: Pokud žádná zlepšující cesta neexistuje, M je největší vyvážená množina.

Pokud tato věta platí (to za chvilku dokážeme), již máme hotový algoritmus:

1. Rozdělíme vrcholy
2. M ←∅
3. Nalezneme prohledáváním grafu do šířky (červené hrany v protisměru) zlepšující cestu C. Dokud existuje, M podle ní vylepšíme a hledáme další zlepšující cestu.
4. Pokud už žádná zlepšující cesta neexistuje, M je největší možná, takže ji hladovým algoritmem převedeme na hranově disjunktní cesty.
5. Vrcholy opět sloučíme a získáme tak hledané vrcholově disjunktní cesty v původním grafu.

Program bude fungovat přesně podle tohoto algoritmu. Graf si budeme pamatovat pomocí seznamů hran incidentních s každým vrcholem, každou hranu budeme mít uloženu v obou směrech a budeme si u ní pamatovat její aktuální barvu. Drobný trik: kroky 4 a 5 lze provádět najednou, abychom si zbytečně nemuseli pamatovat mezivýsledek.

Jak je to s časovou složitostí? Kroky 1, 2, 4 a 5 a každá iterace kroku 3 zaberou čas O(m+n). Zlepšujících cest můžeme nalézt maximálně k (to je velikost nejmenší vrstvy – každé zlepšení nám totiž zvýší počet využitých vrcholů v každé vrstvě), takže celkový čas je O(k·(m+n)). Paměti spotřebujeme O(m+n).

A to už je všechno. Aha, ještě slíbený

Důkaz: Povedeme sporem. Nechť M je vyvážená množina, pro kterou neexistuje žádná zlepšující cesta a N je nějaká větší vyvážená množina. Uvažme P=(M\N)∪(N\M), tedy symetrickou diferenci (xor) těchto dvou množin: hrana e je v P právě tehdy, když e leží v M nebo v N, ale ne v obou současně. Jak množina P vypadá? Jak už víme, s každým vrcholem v z vnitřních vrstev sousedí buďto 0 nebo 2 hrany z M (každá z jedné strany) a totéž platí pro N. Takže mohou nastat následující případy:

1. v nesousedí ani s hranami z M, ani z N ⇒ ani z P
2. v sousedí pouze s hranami z M ⇒ sousedí z každé strany s jednou hranou z P
3. v sousedí pouze s hranami z N ⇒ analogicky
4. v sousedí jak s hranami z M, tak i z N ⇒ jedna z těchto hran musí být společná M i N (v má přeci z jedné strany stupeň 1), takže opět sousedí s právě dvěma hranami z P, ovšem tentokráte vedou obě z jedné strany.

Tedy víme, že graf určený hranami z P má všechny vrcholy stupně 0, 1 nebo 2. Takže to musí být disjunktní (vrcholově) sjednocení cest a kružnic. A jelikož v první vrstvě existuje alespoň jeden vrchol typu c), vede z něj nějaká cesta začínající hranou z N\M (tedy vzhledem k M modrou). Následujme ji: buďto půjdeme stále po modrých hranách nebo narazíme na případ d) a začneme se vracet po červené, v dalším vrcholu typu d) můžeme opět změnit směr atd., až dorazíme do dalšího vrcholu stupně 1, kde cesta skončí. Vrcholy stupně 1 jsou ovšem pouze v počáteční a koncové vrstvě. Jenže pokud jsme se vrátili zpět do počáteční, určitě existuje další, dosud nepoužitý vrchol typu c) a v něm znovu začneme, takže jednou v koncové vrstvě skončit musíme. Pozorný čtenář však dávno ví, že taková cesta je přímo učebnicovým příkladem cesty zlepšující, o které jsme předpokládali, že neexistuje, což je kýžený spor. EPA.

Program

Martin Mareš

15-1-3 Kulový blesk (Zadání)

Tento príklad pekně demonstruje nevýhodnost pažravého (hladového) prístupu k niektorým problémom. Tí, ktorí v prvej fáze chceli umiestniť čo najviac rodín do správnych bytov, nedokázali dokončiť sťahovanie na menej ako ⌈log₂N⌉ fáz. Trik spočíva v tom, že v prvej fázi si rodiny rozmiestnime po bytoch tak, aby po prvom sťahovaní sa rodina v byte i mala sťahovať do bytu j a podobne rodina v byte j do bytu i. Toto dosiahneme napríklad otočením prvých n-1 rodín. Po prvej fáze síce nikto nie je v správnom byte, ale po opätovnom otočení (tentoraz všetkých n rodín) sú v všetky tam, kam sme ich chceli dať.

(1,2,… ,n-2,n-1,n) →(n-1,n-2,… ,2,1,n)→(n,1,2,… ,n-1,n-2)

Počet fáz je teda 2 (okrem prípadu N=2, v ktorom neprebehne prvá fáza) a časová zložitosť je O(N) (v oboch fázach robíme spolu ⌊(n-1)/2⌋+ ⌊n/2⌋ výmen).

Program

Miroslav "Miero" Rudišin

15-1-4 Soustavy (Zadání)

Stínovou stranou moderních hraček je, že lidé zapomněli sčítat pomocí obstarožní tužky a papíru, což se ku příkladu projevuje drobnými krádežemi ze strany obsluhujícího presonálu v restauračních zařízeních nebo též překvapivě velkým množstvím řešitelů, jež nepostřehli jednoduchou zákonitost při sčítání. Nezbývalo pak jináče, nežli postupně zkoušet všechny možné soustavy na korektnost a nebýt horního omezení počtu možných číslic, sčítáme patrně po dnes. Toho si všiml houf řešitelů a počal vymýšlet vylepšování stran výběru možných základů – nutno dodat, že kreativitou v skutku Nešetřil; řešení byla doplňována sadou pozoru hodných výsledků v teorii dělitelnosti, žel bohu ve stylu důkaz či protipříklad si nalezni sám, což nejednoho opravovatele (ú)pějícího v brzkých ranních hodinách nad rozžatou svící nepotěší.

Podívejme na součet číslic A+B=C uvnitř součtu čísel a+b=c na našem pergamenu. Platí-li A≤ C ∧ B≤ C (*) pro všechny řády, může být základ soustavy libovolná číslice x ≥ max_{A∈a,B ∈b, C ∈c}(A,B,C). Stran případu, kdy výše uvedená podmínka * neplatí: abychom se zbavili diskutování o přenosech jedničky z nižšího řádu, budiž naše trojice první takovou (sčítáme zprava), kde podmínka * neplatí. Zde předáme jedničku o řád výše a klíčový postřeh pro hodnotu pod čarou: C=A+B-základ. Ježto A,B,C jsou známé číslice, máme tím pádem i hledaný základ.

Lze snadno nahlédnout lineární časová a paměťová složitost vzhledem k počtu cifer na vstupu. V případě, že by se nám podařilo přesvědčit zkostnatělé zadavatele vstupu o vhodnosti paralelního zadávání čísel od konce, šla by paměťová vylepšit na konstatní.

Poměrně velké množství z vás mělo odhad paměťové složitosti za konstantní, čehož bych se rád dotkl několika slovy – jestliže je vstupem jednotlivé číslo typu počet měst v grafu, které nacpeme do integeru, považujeme složitost za konstantní, zatímco pokud máme za vstup řetězec, se kterým budeme v tomto případě operovat, složitost je úměrná počtu znaků, tedy lineární.

Program

Pavel Šanda

15-1-5 Haskell (Zadání)

Dvouprůchodové řešení této úlohy je tak jednoduché, že ho snad ani nemá smysl komentovat (program si můžete přečíst na konci vzorových řešení).

Nyní jednoprůchodové řešení. Na první pohled se zdá, že to snad nemůže jít – jak mám hodnoty nečím nahradit, když to neznám, dokud neprojdu celý strom? Na druhý pohled si ovšem uvědomíme, že hodnota toho, čím prvky nahrazujeme, vůbec není důležitá. To, co nám umožní tuto myšlenku využít, je fakt, že Haskell je líně vyhodnocovaný – nepokusí se tedy tuto hodnotu zjistit, dokud ji nebude potřebovat. Program bude vyhodnocován tak, že si naalokuje místo pro hodnotu minima, vybuduje strom, jekož prvky budou odkazovat na toto místo a na závěr do tohoto místa uloží spočítanou hodnotu (ve skutečnosti jsou věci ještě o něco složitější, ale pro hrubou představu tohle stačí).

Dvouprůchodové řešení

Jednoprůchodové řešení

Zdeněk Dvořák