Třetí série desátého ročníku KSP

Řešení úloh

10-3-1 Domečkologie (Zadání)

Jelikož se jedná o problém z teorie grafů, nebude od věci, když nejdříve zadefinujeme pár užitečných pojmů a dokážeme dvě více méně triviální tvrzení. Je pravda, že by bylo možno náš algoritmus odvodit i bez tohoto "teoretického abrakadabra", ale pokusme se pro jednou ukázat, jak se věci dělají pořádně. Vše budeme zavádět pro multigrafy, což jsou grafy, v nichž může mezi dvěma vrcholy vést libovolný počet hran.

[Záměrně ukazujeme několik postupně se zlepšujících algoritmů – počínaje algoritmem nefunkčním přes algoritmus složitý až k finálnímu vzorovému programu – abychom ukázali nejen, jak řešení úlohy vypadá, ale také jak se k němu dojde, což ve většině učebnic, ať již programování či matematiky, chybí.]

Definice:

Věta (První eulerova)

V grafu existuje uzavřený eulerovský tah ⇔ graf je souvislý a všechny vrcholy mají sudé stupně.

Důkaz

⇒: Kdyby graf nebyl souvislý nebo v něm existoval vrchol lichého stupně, je zjevné, že v něm nemůže být eulerovský tah. Zbývá tedy dokázat implikaci opačným směrem…

≤: Vezměme nejdelší možný tah v našem grafu. Pokud není uzavřený, jistě má nějaký koncový vrchol, tohoto vrcholu se ovšem tento tah dotýká lichý-počet-krát (jednou na začátku a pak vždy vejde a vyjde a skončí jinde), ale tento vrchol má sudý stupeň, takže existuje nepoužitá hrana z tohoto vrcholu vedoucí a o tu můžeme tah prodloužit ⇒ nebyl nejdelší a jsme ve při. Kdyby nebyl eulerovský, existuje hrana e, která v tahu není obsažena a přitom jeden z jejích vrcholů v v tahu obsažen je (graf je souvislý – pokud existuje jediná hrana e′ mimo tah, vezmeme cestu z jejího libovolného krajního vrcholu do nějakého vrcholu v′ tahu a za e prohlásíme první hranu na této cestě [ve směru od v′], jež v tahu není). A ve vrcholu v můžeme náš uzavřený tah rozpojit a k libovolnému z jeho konců hranu e přidat, čímž jsme jej opět prodloužili. Spor.

Věta (Druhá eulerova)

V grafu existuje otevřený eulerovský tah ⇔ graf je souvislý a existují v něm právě dva vrcholy lichého stupně.

Důkaz

Směr ⇒ je opět zřejmý. Zpět: Pokud existují dva vrcholy v1, v2 lichého stupně, můžeme mezi ně doplnit hranu e' (jelikož pracujeme s multigrafy, nevadí, že už tam jedna taková může být), čímž vznikne graf vyhovující podmínkám předchozí věty, tudíž v něm existuje uzavřený eulerovský tah a odstraníme-li z něj přidanou hranu e', dostaneme otevřený eulerovský tah v původním grafu.

Nyní je zřejmé, že zadání úlohy po nás vlastně chce nalézt v daném (multi)grafu jakýkoliv eulerovský tah a že souřadnice vrcholů jsou naprosto zbytečné. Z předchozích vět je jasné, jak vypadají nutné a postačující podmínky jeho existence. Zkusíme úlohu vyřešit a použijeme k tomu…

Hladový algoritmus

Vybereme si, kde začneme (pokud existují vrcholy lichého stupně, tak v některém takovém, jinak na tom nezáleží, jelikož tah bude uzavřený) a poté budeme tah rozšiřovat o další hrany, dokud to půjde. Na konci nutně dojdeme do druhého vrcholu lichého stupně nebo tam, kde jsme začali (kdybychom došli někam jinam, mohli bychom ještě pokračovat někam dál, protože bychom končili ve vrcholu sudého stupně, v němž jsme nezačali, a tak by musela existovat ještě další nepoužitá hrana pryč).

Vyvrácení

Ačli tento algoritmus najde uzavřený tah, respektive tah se správným začátkem a koncem, nemusí tento tah být eulerovský, protože nemusí obsahovat všechny hrany grafu.

Oprava

Stalo se tedy, že v grafu zbyly ještě nějaké hrany v nalezeném tahu T neobsažené. Ale jak vypadá graf složený z těchto hran? Uvědomte si, že jistě jsou všechny stupně vrcholů sudé (odečetli jsme od všech stupňů vrcholů sudá čísla mimo vrcholů lichého stupně, od nichž jsme odečetli čísla lichá), takže v každé komponentě c tohoto grafu existuje uzavřený eulerovský tah Tc, který má s tahem T alespoň jeden společný vrchol vc, v němž můžeme oba tahy rozpojit a vsunout Tc do T. Jenže tahy Tc můžeme nalézt rekurzivní aplikací téhož algoritmu…

Tento algoritmus úlohu řeší, ba dokonce při vhodné implementaci v čase O(M) (počet hran budeme značit M, počet vrcholů N), nicméně je značně komplikovaný (rekurzivní dekompozice grafu, udržování a slepování seznamů apod.). Pokusíme se jej ještě trochu zjednodušit… Zkonstruujeme hladovým algoritmem nějaký základní tah T0 a nalezneme první vrchol v, z nějž vede nepoužitá hrana e (z důkazu Eulerovy věty víme, že buďto taková hrana neexistuje, nebo je graf eulerovský a nebo nesouvislý – to, který případ nastal, vyřešíme snadno počítadlem zbývajících hran), načež zkonstruujeme uzavřený tah Te ze zbylých hran, který v e začíná i končí, připojíme jej do T0 a takto pokračujeme, dokud existují nepoužité hrany s tahem sousedící. Povšimněte si, že při přidávání takovýchto "podtahů" nemůže nikdy vzniknout nepoužitá hrana dotýkající se vrcholu, který by na našem tahu byl před vrcholem v, takže lze vše vyřešit frontou na dosud nezpracované vrcholy v čase O(M) a paměti O(M) takto:

Algoritmus F (Frontální útok)

  1. Spočítáme vrcholy lichého stupně, pokud jich je >2, úloha nemá řešení, jinak zvolíme počáteční vrchol v0 jako jeden z lichých, případně libovolný, pokud jsou všechny sudé.
  2. Mějme frontu Q, z počátku obsahující počáteční vrchol v0.
  3. Vezměme vrchol v z fronty Q a ten vypišme (víme, že je zaručeně ve finálním tahu T – viz předchozí odstavec).
  4. Pokud existuje dosud nepoužitá hrana e vedoucí z v, vydáme se touto hranou a pokračujeme dalšími nepoužitými hranami, dokud to jde. Všechny navštívené vrcholy přidáváme na konec fronty.
  5. Opakujeme 3–4, dokud se fronta nevyprázdní.
  6. Zbyla-li v grafu jakákoliv hrana, graf byl nesouvislý. Jinak jsme vypsali eulerovský tah (správnost zřejmá z tvrzení dokázaných výše).

Do třetice

Celý algoritmus ještě můžeme zjednodušit tím, že využijeme prohledávání grafu do hloubky jednoduchým rekurzivním algoritmem. Místo fronty tak použijeme zásobník (tím se pouze tah otočí, což není na závadu), který nám rekurze zajistí sama bez nutnosti implementovat si jej ručně. Časová ani paměťová složitost se nezmění. Vzorový program vychází z této varianty a jeho činnost by měla být zřejmá z komentářů v programu, jedině jest snad záhodno upozornit na trik s funkcí XOR, jímž se páruje hrana "tam" s hranou "zpátky".

Program

Martin Mareš

10-3-2 Sirky jsou vrženy (Zadání)

Bohužel zadání nebylo příliš šťastně zformulováno i stalo se, že přicházela různá řešení (to je obvyklé) různých úloh, všechna ovšem označená jako KSP-10-3-2 (to už je méně obvyklé). Někteří z Vás považovali ono magické k ze zadání úlohy za maximální počet sirek, které lze v jednom tahu odebrat, jiní za jediný možný počet sirek, který lze odebrat a další za blíže neurčenou proměnnou. Protože většina z Vás považovala k za konstantu určující, kolik sirek lze odebrat z jedné, druhé nebo z obou hromádek v jednom kole, rozebereme zde řešení takto zadané úlohy. Maximální počet bodů udělovaných za správné a úplné řešení se pohyboval dle obtížnosti vyřešené varianty od 10 do 13 bodů.

Nechť na hromádkách je n a m sirek. Protože lze odebírat pouze k sirek, záleží výsledek pouze na velikosti celých částí podílů n/k a m/k. Stačí tedy vytvořit algoritmus za předpokladu, že k=1; řešení původní úlohy získáme aplikací tohoto algoritmu na případ, kdy počty sirek na hromádkách jsou celé části podílů n/k a m/k, a odebíraný počet sirek potom vynásobit k.

Stav, kdy na jedné hromádce je a a na druhé b sirek budu pro stručnost označovat jako [a,b]. Stav [x,y] nazvu kritický, jestliže neexistuje (dovolený) tah do stavu [u,v] takového, že [u,v] je kritický, nebo platí-li, že x=y=0. Stav [x,y] nazvu vyhrávající, jestliže není kritický. Takto zavedené označení stavů je korektní, neboť mohu stavy [x,y] roztřiďovat na kritické a vyhrávající v neklesajícím pořadí dle součtu x+y — postup je stejný jako v důkazu následujícího tvrzení: Pro stav [x,y] existuje tah, který mi zaručí výhru, právě tehdy, pokud stav [x,y] je vyhrávající. Pro stav [x,y] takový tah neexistuje právě tehdy, pokud je tento stav kritický. Navíc stav [x,y] je kritický, pokud x i y jsou obě sudá čísla.

Důkaz provedeme matematickou indukcí podle velikosti součtu x+y. Pro x+y=0 tvrzení platí – jsou-li obě hromádky prázdné, tak jsem prohrál a nula je sudé číslo.

Nechť tvrzení platí pro všechny stavy [u,v], kde u+v<x+y. Je-li stav [x,y] kritický, potom všechny stavy [u,v], do kterých lze přejít, jsou vyhrávající, a tedy z nich existuje tah, který zaručí soupeři výhru. Proto po mém libovolném tahu, může udělat soupeř tah, který mu zaručí výhru a tedy žádný tah z tohoto stavu nemůže zaručit výhru mně. Ze stavu [x,y] lze přejít do stavů [x-1,y], [x,y-1] a [x-1,y-1]. Potom ale (dle indukčního předpokladu) jsou obě čísla x a y sudá, neboť jinak by jeden z těchto tří stavů byl kritický, což by byl spor s tím, že stav [x,y] je kritický.

Je-li stav [x,y] vyhrávající, potom existuje tah do stavu [u,v], který je kritický. Tento tah je tím tahem, který mi zaručí výhru, neboť ať soupeř ze stavu [u,v] přejde do libovolného stavu [s,t], ten bude určitě vyhrávající, neboť [u,v] je kritický, existuje z tohoto stavu tah, který mi zaručuje výhru. Důkaz, že alespoň jedno z čísel x a y je liché se provede stejně jako v předchozím případě.

Vyhrávající strategie tedy vypadá tak, že se snažíme, aby soupeř vždy táhl ze stavu [x,y], kde x i y jsou sudá čísla. To se nám povede právě tehdy, pokud alespoň jedno z těchto čísel je liché, což lze udělat s konstantní časovou i paměťovou složitostí.

Program

Daniel Kráľ

10-3-3 Lloydova devítka (Zadání)

Počet možných konfigurací herního plánu je vlastně počet všech permutací 8 kostiček plus jedné díry, tedy 9!=362880. Nejkratší posloupnost tahů vedoucí k požadovanému stavu lze při tomto počtu efektivně spočítat prohledáváním do šířky. Budeme předpokládat, že pracujeme na 32-bitovém kompilátoru a nemusíme se starat o velikost pole.

Herní plán si představíme jako graf. Vrcholy budou možné permutace kostiček a hrany budou spojovat ty permutace, které se liší pouze jedním tahem, tedy posunutím díry o 1 políčko libovolným směrem. V tomto grafu hledáme nejkratší cestu z jednoho vrcholu do druhého. Prohledávání grafu do šířky funguje následujícím způsobem:

  1. Označíme všechny vrcholy grafu jako neprobádané, pouze počáteční vrchol označíme jako nalezený nicméně ještě nezpracovaný.
  2. Vezmeme všechny nalezené nezpracované vrcholy a pro každý z nich prohledáme všechny jeho sousedy. Pokud některý z nich byl dosud neznámý, označíme ho k zpracování v dalším tahu a zapíšeme do něj směr, odkud jsme k němu došli.
  3. Krok 2 opakujeme tak dlouho, dokud nalézáme nové vrcholy.

Po ukončení práce algoritmu je v každém dosažitelném vrcholu uložen směr, kterým se máme vydat, abychom došli nejkratší možnou cestou k cíli. Vrcholy, které nebyly tímto algoritmem zpracovány, jsou nedosažitelné. U Lloydovy devítky se nám množina všech permutací rozdělí na dvě poloviny: na sudé a liché permutace. To znamená, že celá jedna polovina všech konfigurací je nedosažitelná a úloha pro ní nemá řešení.

V programu používám funkce perm2int a int2perm pro vzájemně jednoznačný převod permutací na přirozená čísla, který je diskutován v úloze 10-3-5. Permutace jsou označeny čísly 0,1,…,9!-1, permutace číslo 0 je základní pozice. V celém programu je použita tato konvence zápisu permutací: pi znamená pozici ve čtverci, na níž je uloženo číslo i. Pozice ve čtvreci jsou očíslovány čísly 0,1,…,8 po řádcích.

Při prohledávání do šířky funkcí search ukládám do pole informaci o příchozím směru tímto způsobem:

0 označuje nezpracovanou permutaci,
1–4 označují plně zpracovanou permutaci, do níž jsme přišli z příslušného směru (1 → shora, 2 → zdola, 3 → zleva, 4 → zprava),
5–8 označují permutaci určenou pro zpracování v tomto tahu,
9–12 označují právě nalezené permutace, které se budou zpracovávat až v příštím tahu.

Toto označení je zvoleno, protože vyhledávání do šířky probíhá po hladinách s rostoucí vzdáleností od počátku. Abychom nemuseli konstruovat frontu, do které by se ukládaly vrcholy čekající na zpracování, označujeme si nezpracované permutace přímo v poli. Tedy kromě příchozího směru označujeme také stadium zpracování, aby se nám nepletly hladiny. Po každém průchodu označíme zpracované permutace jako stabilní a nově nalezené určíme pro zpracování v dalším kole.

Při hledání cesty i při zpětném průchodu se využívá funkce move, která zjistí, zda je vůbec daný tah proveditelný, a pokud ano, pak jej provede. Právě tato funkce je jediná v programu, která určuje pravidla hry. Pokud bychom ji nahradili čímkoliv jiným, dostali bychom program pro hledání strategie v libovolné jiné hře tohoto typu.

Zpětný průchod funkcí animate již pouze rekonstruuje cestu. Při hledání úmyslně začínáme ve startovním vrcholu, neboť při rekonstrukci postupu, jak danou konfiguraci poskládat, stačí v 1 průchodu jít podle šipek a vypisovat tahy, ale hlavně proto, že s jedním předpočítaným polem umíme najít nejkratší cesty ze všech dosažitelných konfigurací. Při výpisu mezistavů musíme vypočítat inverzní permutaci, neboť na rozdíl od konvence použité ve zbytku programu potřebujeme zjistit, jaké číslo je na pozici i.

Paměťová složitost programu je O(n!), kde n=9 je obecně počet políček ve čtverci. Časová složitost je O(kn!), kde k je délka nejdelší z nejkratších cest (neboť tolikrát musíme projet celé pole). Obecnou závislost k na n nebude pravděpodobně snadné zjistit.

Možná vylepšení algoritmu:

  1. Kdybychom chtěli algoritmus vylepšit např. tím, že by se zastavil v průběhu výpočtu ve chvíli, kdy nalezne cílovou konfiguraci, nepomohlo by nám to, protože ačkoliv je pro n=9 její vzdálenost maximálně 31 (viz. výpisy programu v průběhu výpočtu), musíme projít při prohledávání do šířky také plno jiných pozic.
  2. Paměťová náročnost lze výrazně zmenšit, pokud nepoužijeme v poli permutací pro každou z nich 1 bajt, ale pouze 3 bity: 2 bity pro směr, odkud jsme přišli, a 1 bit jako flag zpracování. To ale algoritmus značně zkomplikuje, s polem znaků se pracuje přeci jenom lépe než s bitovým polem.
  3. Časovou náročnost lze zlepšit z O(kn!) na O(n!), pokud permutace určené ke zpracování nebudeme označovat flagem v poli, ale vytvoříme si frontu. Pak ušetříme 1 bit v poli, ale musíme vyhradit 3 bajty ve frontě, maximální délka fronty je pro n=9 experimentálně zjištěná <25000. Nejvýrazněji ušetříme čas, neboť každá permutace se ve frontě objeví maximálně jednou. Bohužel pro obecné n není zřejmé, jak velká fronta bude potřeba.

Program

Robert Špalek

10-3-4 Hic sunt leones (Zadání)

Nejednoho z vás asi překvapí, že optimální algoritmus pro tuto úlohu pracuje s konstatní časovou složitostí. Jak toho lze dosáhnout? Představte si, že mnohoúhelník svislými řezy nařežeme na tenké plátky, dost tenké na to, aby v každém z nich ležely nejvýše dva body mnohoúhelníka. Pokud budeme mít plátky všechny stejné tloušťky t, pak snadno určíme, zda v některém z nich leží daný bod (bude mít index (x-xmin)/t v poli plátků). A každý plátek je vlastně nejvýše šestiúhelník, takže na rozhodnutí, zda bod leží uvnitř, stačí zjistit polohu vůči jeho šesti stranám. Realizace v C++ následuje.

Co se týče analytické geometrie zde použité: rovnice přímky má tvar: a·x+b·y+c=0. Pokud do této rovnice dosadíme souřadnice dvou bodů, které přímku určují, dostaneme a=y1-y2, b=x2-x1 a c=-(a·x1+b·y1), pokud pak do této rovnice dosadíme souřadnice nějakého bodu X, dostaneme 0, pokud X na přímce leží, jinak q>0 resp. q<0 pro jednu resp. druhou polorovinu přímkou určenou.

Trochu černá můra je paměťová složitost, ta může být hodně vysoká, ale tady nebyla rozhodující. Je nepřímo úměrná nejmenšímu rozdílu x-ových souřadnic vrcholů. A to může být hodně málo. Třeba už pro mnohoúhelník (0,0), (0.001,1), (1,1), (1,0) bude tloušťka plátku rovna 0.001, tedy vznikne 1000 plátků.

Celý program by šlo dále optimalizovat jak na přehlednost, tak na rychlost, ale asi bych si za něj 10 bodů dal, i když bych si při tom nejspíše dost nadával.

Program

Ví(tek) No(vák)

10-3-5 Terucempa (Zadání)

Jen málokdo si nepovšiml, že trpaslíci jsou dlouhověcí, a procházel po řadě všechny možné permutace; takové řešení závisí na pořadí dne lineárně, na počtu trpaslíků tedy zhruba exponenciálně a ani pro osm či dvanáct trpaslíků (zadání si v přesném počtu poněkud odporovalo, za což se poněkud omlouváme) není rychlost výpočtu rozumná.

Pokusme se seřadit trpaslíky přímo z čísla dne. Očividně, na prvním místě se každý trpaslík vystřídá 11! krát (11! znamená 11·10·9·… ·2·1), na druhém každý kromě toho, co už stojí na prvním místě, 10! krát a tak dále. Kolikátý volný trpaslík má stát na n-tém místě od konce, tedy určíme tak, že pořadí dne vydělíme n! a necháme si jen zbytek po dělení. Tím jsme odhlédli od změn na předcházejících pozicích a stačí nám tento zbytek vydělit (n-1)!, čímž se dozvíme, kolikátý trpaslík z těch, co dosud nebyli umístěni, bude umístěn na tomto místě.

Je nutno si udržovat seznam zbývajících trpaslíků a každého umístěného trpaslíka z něj vyškrtnout (posunout část seznamu), takže výsledná časová složitost je O(N2), kde N je počet trpaslíků. Na pořadí dne algoritmus nezávisí. Prostorová složitost je O(N).

Zdeněk Dvořák a Jan Kára seznam volných trpaslíků reprezentují binárním vyhledávacím stromem, čímž docilují průměrné rychlosti O(N· log N), jež je zároveň nejlepší možná. Pro počty trpaslíků, pro které lze na dnešních nedokonalých 64-bitových počítačích zpracovávat jejich faktoriál jako přirozené číslo, však obyčejné řešení v čase O(N2) neznamená žádné zdržení a uznávali jsme jej jako optimální.

Vzorový program tvoří rekurzivní procedura, která se nejprve dvanáckrát od posledního trpaslíka v řadě k prvnímu zanoří a spočte si při tom příslušné faktoriály. Pak se postupně vynořuje zpátky k poslední pozici a s pomocí těchto faktoriálů uvedeným algoritmem určuje jednotlivé trpaslíky.

Program

Jirka Hanika