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

Vzorová řešení


12-1-1 Dlaždiči (Zadání)


Dobrých řešení této úlohy bylo přibližně jako dinosaurů (šafrán je v našich krajích příliš častý). Je ovšem třeba přiznat, že je to i naše chyba, protože jsme špatně odhadli obtížnost této úlohy… S výjimkou tří dobrých řešení pomocí párování v bipartitním grafu se nám zde sešla pěkná řádka heuristik a backtrackingů. Chybou autorů heuristik bylo často neexistující nebo nekorektní zdůvodnění správnosti (jinak byste totiž zjistili, že váš algoritmus nefunguje). Také odhady složitosti zjevně dělaly problémy mnohým řešitelům.

A teď už k řešení úlohy. Náš problém s dlaždicemi převedeme na poměrně známý problém perfektního párování v bipartitním grafu. Na ten už existují rychlé a osvědčené algoritmy. Abychom si řešení mohli vysvětlit, uvedeme si nejdříve několik definic:

  • Graf G je uspořádaná dvojice (V, E), kde E = V×V: (i,j)∈E ⇒(j,i)∈E. Prvky množiny V budeme nazývat vrcholy, prvky množiny E hrany. A teď lidsky: Graf je nějaká sada bodů, přičemž některé body jsou pospojovány čárami — klasickým příkladem je třeba silniční síť. Křižovatky jsou vrcholy, silnice mezi křižovatkami hrany.
  • Bipartitní graf je takový graf, kde vrcholy lze rozdělit na dvě skupiny tak, že hrany vedou pouze mezi těmito skupinami. Tedy žádná hrana nevede mezi dvěma vrcholy stejné skupiny.
  • Párování v grafu je taková množina hran, že žádné dvě hrany nesdílí vrchol. O párování řekneme, že je perfektní, jestliže v každém vrcholu končí jedna z vybraných hran.

A jak tyto pojmy souvisí s naším problémem? Naše plocha k vydláždění je vlastně bipartitní graf. Políčka k vydláždění budou vrcholy a hrana mezi dvěma vrcholy povede tehdy, jestliže odpovídající políčka sousedí hranou. To, že to bude graf bipartitní plyne z faktu, že pokud si představíme šachovnicové obarvení plochy a do jedné skupiny zařadíme "bílé" vrcholy a do druhé "černé" vrcholy, tak zajisté povedou všechny hrany pouze mezi vrcholy s různými barvami. Dlaždice jsme na plochu mohli položit tam, kde byla dvě sousední políčka volná. To je tedy přesně tam, kde nyní mezi odpovídajícími vrcholy vede hrana. Rozložení dlaždic na ploše tedy odpovídá nějakému párování – požadavek na to, aby hrany neměly společný vrchol přesně odpovídá požadavku, aby se žádné dvě dlaždice nepřekrývaly. Tedy problém, zda lze plochu vydláždit jsme převedli na problém, zda existuje párování "zahrnující" všechny vrcholy – tedy perfektní párování.

Algoritmus na hledání perfektního párování bude pracovat tak, že bude postupně (v každém kroku o 1) zvětšovat velikost párování. Pokud již párování nepůjde zvětšit, zjistíme, zda pokrýva všechny vrcholy. Pokud ano, plochu vydláždit jde, pokud ne, plochu vydláždit nejde. Aktuální párování (na počátku třeba prázdné – nejsou spárovány žádné vrcholy) budeme vylepšovat následovně: Nalezneme cestu, která začíná v nespárovaném vrcholu, pokračuje po hraně, která není v párování, pak po hraně, která v párování je, a tak dále až do vrcholu, který spárování není. Pokud na této cestě (zjevně musela mít lichou délku, protože začínala i končila hranou mimo párování a všude se hrany pravidelně střídaly) zaměníme hrany v párování a mimo něj, zjevně získáme párování o jednu hranu větší. To zase můžeme stejným způsobem zlepšovat. Pozorování, že takováto cesta bude vždy existovat, pokud párování jde zvětšit vám necháváme k rozmyšlení (návod: zkuste to sporem a podívejte se na graf zachycující rozdíly mezi párováním, ve kterém jste cestu už nenašli, a maximálním párováním).

Zbývá ještě otázka, jak najít onu kýženou cestu. To jde ale velmi snadno. Použijeme lehce modifikované prohledávání do šířky. Na začátku budeme mít ve frontě ke zpracování nespárovaný vrchol. Krok hledání proběhne tak, že vždy z fronty odebereme vrchol a podíváme se na jeho sousedy. Pokud je nějaký soused nespárovaný, máme hledanou cestu. Pokud jsou všichni spárovaní, přidáme do fronty odpovídající sousedy sousedů v párování (samozřejmě přidáváme pouze vrcholy, které jsme v tomto prohledávání dosud nezpracovali). Když se fronta vyprázdní a nenalezli jsme cestu, do tohoto vrcholu zjevně hledaná cesta nevede a snadno si můžete dokázat, že ani nikdy vést nemůže, takže vydláždění neexistuje.

Algoritmus v každém kroku zvětší párování o jednu hranu. Kroků tedy může být nejvýše N (počet vrcholů). Jeden krok nám trvá O(M), kde M je počet hran. Celkem by čas tedy byl O(M*N). Když si ale navíc povšimneme, že hran je nejvýše 2*N, získáváme lepší odhad časové složitosti – O(N2). Paměťová složitost algoritmu je O(N).

Správnost algoritmu byla ukázána již v jeho popisu. Program je přímou imlementací algoritmu.

Program

Jan Kára


12-1-2 Parník (Zadání)


Tento příklad je možno řešit neobyčejně mnoha různými algoritmy. Zde jsme si vybrali jeden velice elegantní, který ovšem vyžaduje trošku přemýšlení o tom, proč vlastně funguje…

Úlohu si přeformulujme do řeči teorie grafů: máme zadánu nějakou množinu vrcholů (význačné body říční sítě), které jsou spojeny hranami (splavné úseky řeky) a každé hraně je přiřazeno kladné ohodnocení (délka úseku). Navíc víme, že mezi každými dvěma vrcholy vede právě jedna cesta (posloupnost na sebe navazujících hran taková, že první hrana posloupnosti začíná v prvním z vrcholů, poslední hrana končí v druhém z vrcholů a žádný vrchol není navštíven vícekrát). Takovým grafům říkáme stromy a nejprve si je pořádně prohlédneme:

Pozorování 1: Každý strom má alespoň jeden list, to jest vrchol, z nějž vede pouze jedna hrana, a oba krajní vrcholy nejdelší cesty jsou listy. [Nejdelší cesta jistě existuje a kdyby libovolný z jejích krajních vrcholů nebyl list, vedla by z něj ještě alespoň jedna nevyužitá hrana a o tu bychom mohli cestu prodloužit … jenže všechny hrany mají kladné délky, tudíž nová cesta by byla ještě delší než ta nejdelší, což je spor.]

Pozorování 2: Strom o n≥ 1 vrcholech má n-1 hran. [To dokážeme třeba indukcí. Pro strom na jednom vrcholu to jistě je pravda, pokud je n>1 a pro všechna menší n již tvrzení platí, odebereme ze stromu jeden list (jak již víme, vždycky nějaký existuje), tím jsme získali strom na n-1 vrcholech, který má podle indukčního předpokladu n-2 hran, načež list připojíme zpět, čímž přibyl jeden vrchol a jedna hrana, takže hran je celkem n-1, a to je přesně, co jsme chtěli.]

Značení: xy budeme značit cestu mezi vrcholy x a y, d(x,y) pak bude délka této cesty. Jelikož náš graf je neorientovaný, platí d(x,y)=d(y,x).

Tvrzeníčko: Zvolme si libovolný vrchol x a vrchol y od x nejvzdálenější. Potom jedna z nejdelších cest v našem stromu končí vrcholem y.

Důkaz: Ve skutečnosti dokážeme ještě silnější tvrzení: máme-li ve stromu vrchol x, od něj nejvzdálenější vrchol y a cestu ab, pak d(y,b) ≥ d(a,b) (jinými slovy cesta yb je alespoň stejně dlouhá jako ab). Rozlišme dva případy:

  • Cesta xy protíná cestu ab. Označme si p ten ze společných vrcholů těchto cest, který leží nejblíže k b. Potom z toho, že d(x,y)≥ d(x,a) plyne také d(p,y)≥ d(p,a) [protože d(x,y)=d(x,p)+d(p,y) a analogicky pro d(x,a)], a tedy i d(y,b)≥ d(a,b) [d(a,b)=d(a,p)+d(p,b) a stejně tak pro d(y,b)].
  • Není tomu tak. Buď q vrchol na cestě ab nejbližší k vrcholu x. Pak cesta xy nutně protne cestu xb (například ve vrcholu x). Nechť r je poslední z průsečíků těchto cest ve směru od x. Pak jelikož d(x,y)≥ d(x,a), je také d(r,y)≥ d(r,a), tím spiše d(q,y)≥ d(q,a) [k levé straně jsme přičetli a od pravé odečetli kladné čislo d(r,q)] a z toho stejně jako v předchozím případě dostaneme d(y,b)≥ d(a,b).

Z tohoto tvrzeníčka již snadno odvodíme algoritmus pro hledání kýžené nejdelší cesty: Zvolíme si libovolný vrchol x, nalezneme od něj nejvzdálenější vrchol y (pokud jich je více, tak kterýkoliv z nich) a pak od vrcholu y nejvzdálenější vrchol z, načež cestu yz prohlásíme za nejdelší. Z výše uvedeného důkazu plyne, že to vždy bude pravda.

Nejvzdálenější vrchol budeme v obou případech hledat prohledáním stromu do hloubky. Graf budeme representovat seznamy sousedů jednotlivých vrcholů. Začneme ve vrcholu, z nějž vzdálenosti měříme, rekursivním voláním téže funkce nalezneme pro každého syna zpracovávaného vrcholu nejvzdálenější vrchol v podstromu určeném tímto synem a poté z těchto mezivýsledků vybereme nejvzdálenější a ten prohlásíme za výsledek. Jelikož náš graf je souvislý a každou hranu máme reprezentovanou v obou orientacích (při rekursivním volání si ovšem pamatujeme předchozí vrchol, abychom se nezacyklili), projdeme jej nutně celý.

Časová složitost našeho algoritmu je O(N) (při každém z obou prohledávání grafu každý vrchol a každou hranu navštívíme právě jednou; vrcholů je N, hran podle Pozorování 2 je N-1). Paměťová složitost činí O(N2), ale to pouze kvůli neúsporné reprezentaci stromu v paměti, kterou bychom snadno mohli upravit tak, aby si vystačila s pamětí O(N).

Program

Martin Mareš


12-1-3 A sort of sort (Zadání)


Pomůcky: n prázdných papírků
n kbelíků očíslovaných 0..n-1
čas 3n
3 svíce
O třetí noci po slunovratu vezmi čísla,
každé z nich o jedničku zmenši,
do n-kové soustavy přepiš,
na připravené papírky zapiš.

Vezmi papírky popořadě,
na poslední cifru se soustřeď,
do kbelíku s číslem řádným
potom papírek zařaď.

Až rozdáš papírky všechny,
první svíci zapal,
potom papírky postupně
z kbelíků 0 až n-1 vybal
(Pozor však musíš dát:
ten papírek, který první vložen byl,
první musí být vyňat)

Vezmi papírky popořadě,
na střední cifru se soustřeď,
do kbelíku s číslem řádným
potom papírek zařaď.

Až rozdáš papírky všechny,
druhou svíci zapal,
potom papírky postupně
z kbelíků 0 až n-1 vybal.

Vezmi papírky popořadě,
na první cifru se soustřeď,
do kbelíku s číslem řádným
potom papírek zařaď.

Až rozdáš papírky všechny,
poslední svíci zapal,
potom papírky postupně
z kbelíků 0 až n-1 vybal.

Nyní máš papírky s čísly a hle!
čísla popořadě jdou.

Správnost algoritmu je nasnadě. Čísla budou zřejmě korektně seřazena vzhledem k první cifře. Korektní seřazení vzhledem k druhé cifře nám zaručí předchozí průchod. Ten totiž seřadil čísla podle druhé číslice. Když jsme tedy potom čísla rozdělovali podle první cifry, tak první přišla na řadu čísla s nižší druhou cifrou, a tedy v každém kbelíku budou čísla seřazena podle druhé číslice. Když je tedy z kbelíků na konci vybereme, budou korektně seřazena nejen vzhledem k první, ale i vzhledem k druhé cifře. Obdobnou úvahu můžeme provést při řazení podle poslední cifry, čímž dojdeme k závěru, že čísla budou skutečně korektně seřazena.

Program používá pole velikosti O(N2), takže skutečná časová složitost je O(N2). Nebyl by ovšem problém toto pole nahradit dynamicky alokovanými položkami, čímž by se časová složitost stala skutečně lineární.

Program

Pavel Machek


12-1-4 PRAM (Zadání)


Myšlenka, jak vyřešit zadanou úlohu na P-CRCW PRAMu, napadla každého z Vás. Použijeme tolik procesorů, kolik mají zadaná čísla cifer; každý z procesorů bude mít na starosti dvojici cifer stejného řádu, porovnají je a pokud se liší, pak svůj výsledek ve stejný okamžik zapíší do gmem[0] – procesory s nižším číslem (vyšší prioritou) budou porovnávat cifry vyššího řádu a tedy se do gmem[0] zapíše výsledek porovnání rozdílných cifer nejvyššího možného řádu. Bohužel již ne ve všech řešeních byla tato myšlenku úspěšně realizována: Především je třeba před porovnáním cifer obou čísel uložit do gmem nulu, aby byl výsledek výpočtu správný i v případě, že se obě čísla shodují. Výsledek porovnání navíc procesory musí zapsat ve stejný okamžik, tj. nelze nejprve testovat, zda cifry prvního čísla jsou menší než cifry druhého a v kladném případě zapsat jedničku, a dalším příkazem testovat opak a zapisovat dvojku (viz porovnávání čísel 1012 a 1102). Samotný program, pokud máme na paměti tyto dvě věci, je snadné napsat – počet použitých procesorů je O(N), časová složitost je O(1) a paměťová je O(N), kde N je počet cifer porovnávaných čísel.

Vyřešení zadané úlohy na CREW PRAMu bylo velmi snadné; program pro CREW PRAM, uvedený jako ukázkový v zadání první série, totiž řešil následující úlohu: V zadané posloupnosti nul a jiných čísel (v ukázkovém programu čísel procesorů) totiž našel první nenulové číslo a to prohlásil za výsledek; pokud byla celá posloupnost nulová, byla výsledkem nula. Náš program tedy bude fungovat následovně: Nejprve každý z procesorů porovná dvojici bitů stejného řádu a výsledek uloží na příslušnou pozici do globální paměti; zde je třeba dát pozor, že výsledek nelze do globální paměti ukládat rovnou, neboť je nejprve potřeba provést obě porovnání – následující totiž nefunguje (jak každý jistě sám snadno zjistí pro dvojici cifer 0 a 1):

lmem[0]:=cpuid+gmem[0]
if gmem[cpuid]<gmem[lmem[0]] then
  gmem[cpuid]:=1
if gmem[cpuid]>gmem[lmem[0]] then
  gmem[cpuid]:=2
if gmem[cpuid]=gmem[lmem[0]] then
  gmem[cpuid]:=0

Napsat nyní program s využitím postupu použitého ve vzorovém programu v zadání první série je již triviální – počet použitých procesorů je O(N), časová složitost je O(log N) a paměťová je O(N), kde N je počet cifer porovnávaných čísel.

Nyní obraťme svoji pozornost k EREW PRAMu. V zadání první série jsme úmyslně zatajili technické detaily, jak vzorovou úlohu přesně na EREW PRAMu vyřešit; bohužel to znamenalo, že většina z Vás se nad úlohou příliš nepokusila zamyslet. Jediný rozdíl oproti CREW PRAMu totiž spočívá v tom, že všechny procesory nemohou v jediném kroku zjistit počet cifer zadaných čísel – to by totiž vyvolalo konflikt při čtení (různé procesory by se pokusily číst tutéž hodnotu); řešení založené na tom, že na začátku proběhne cyklus délky N, v jehož i-té iteraci si i-tý procesor přečte gmem[0], je zcela neparalelní (a tudíž hodnoceno odpovídajícím počtem bodů) – jenom tento cyklus zabere čas O(N) a tedy ve stejném čase bychom mohli celý výpočet provést i s jediným procesorem. To vyřešíme tak, že si hodnotu rozkopírujeme v globální paměti. Cifry prvního čísla si uschováme bokem, a před první kopírovací vlnou bude znát délku posloupnosti pouze první procesor, který ji zapíše do gmem[1]. Po první vlně budou znát délku dva procesory a bude uložena ve gmem[1] a gmem[2], po druhé vlně čtyři procesory a délka posloupnosti se bude již nacházet v paměťových buňkách gmem[1]gmem[4] atd. Obecně v i-té vlně prvních 2i-1 procesorů zkopíruje obsah gmem[cpuid]2i-1 buněk dál. Po logaritmicky mnoha krocích již délku posloupnosti znají všechny procesory a můžeme pokračovat stejně jako na CREW-PRAMu. Vytvoření programu pro PRAM je nyní již triviální - počet použitých procesorů je O(N), časová složitost je O(log N) a paměťová je O(N), kde N je počet cifer porovnávaných čísel.

Za vyřešení úlohy pro P-CRCW, CREW a EREW PRAM bylo možné po řadě získat 2, 4 a 4 body.

Program – CREW PRAM

Program – EREW PRAM

Daniel Kráľ