Čtvrtá série čtrnáctého ročníku KSP

Řešení úloh

• 14-4-1: Povodeň
• 14-4-2: Posloupnost
• 14-4-3: Koordinátor
• 14-4-4: Triramidy
• 14-4-5: Turingovy stroje

14-4-1 Povodeň (Zadání)

Při řešení této úlohy bylo klíčovým momentem spočítat, do jaké výšky na kterém čtverci vystoupí hladina. Jeden z efektivních algoritmů (mezi řešeními se vyskytly tři různé) je založen na Dijkstrově algoritmu: všem čtvercům na okraji pole přiřadím výšku hladiny rovnou maximu z jejich výšky a nuly (co kdyby to třeba byla prohlubeň), ostatním čtvercům nekonečno. Nyní vezmu z dosud nezpracovaných čtverců (na počátku jsou všechny čtverce nezpracované) ten s nejmenší výškou hladiny a všem dosud nezpracovaným čtvercům okolo nastavím výšku hladiny jako maximum z jejich výšky a výšky hladiny na onom vybraném čtverci. Druhý krok pak opakuji tak dlouho, dokud zbývají nějaké nezpracované čtverečky. Na vyhledání minima se použije halda, což nám zaručuje složitost O(n² · log n). Všimněte si, že proti standardnímu Dijkstrovu algoritmu nastavujeme výšku hladiny na jenom čtverečku jen jednou (tj. pak už se nesnižuje), což nám umožňuje jisté zjednodušení práce s haldou.

Program

Pavel Nejedlý

14-4-2 Posloupnost (Zadání)

Tahle úložka byla spíš z těch jednodušších, a přestože se vyskytla i řešení, která o sobě tvrdila, že pracují v čase Ω(n³), žádné z nich o tom nedokázalo přesvědčit ani mě. Jak by tedy mohlo vypadat řešení:

Pro zjednodušení předpokládejme, že všechna čísla v posloupnosti jsou kladná. Budeme postupně probírat čísla posloupnosti a zjišťovat, zda se v ní nevyskytuje jejich 2. a 3. mocnina. Toto vyhledávání budeme provádět jednoduše postupným procházením posloupnosti podle velikosti. Tímto bychom dosáhli časové složitosti O(n²), což nechceme. Provedeme tedy drobné vylepšení – při hledání čísla se můžeme zastavit, když aktuálně probrané číslo je větší než hledané (posloupnost je rostoucí, tedy pak už nic nemůžeme najít). To nám ovšem na asymptotické složitosti nic nezmění.

Paměťová složitost je zjevně lineární. Časová složitost je zajímavější, protože v programu se nám vyskytují do sebe zanořené smyčky; přesto je i časová složitost lineární, protože v každé iteraci vnitřní smyčky se ukazatele pozice pro x² a x³ zvětší o 1, což mohou udělat maximálně n krát.

Program

Zdeněk Dvořák

14-4-3 Koordinátor (Zadání)

Túto úlohu lze previesť na hľadanie minima v kruhovej sieti, v ktorej sa koordinátorom stane počítač s najmenším ID. Predpokladajme, že máme k dispozici funkcie ReceiveLeft a ReceiveRight (realizované napr. buffermi správ pre oba smery), ktoré vrátia prvú nespracovanú správu v požadovanom smere. Na začiatku výpočtu všetky počítače kandidujú na koordinátora. Ak sa nejaký počítač dozvie o inom počítači s menším ID ako je jeho, prestane kandidovať a prijaté správy preposiela ďalej v pôvodnom smere. Voľba koordinátora prebieha po kolách. V každom kole všetci kandidáti odošlú svoje ID na obe strany a následne dostanú ID najbližších kandidátov. Ak ich ID nie je najmenšie, prestanú kandidovať. Voľba končí ak prijaté ID sú rovnaké ako lokálne ID. To znamená že v kruhu ostal jediný kandidát. Ten to oznámi ostatným počítačom; napríklad obežníkom, ktorý po prejdení kruhu skončí u neho. V kruhu s N (N>2) kandidujucími počítačmi je N susediacich dvojíc, z ktorých v každom kole vypadne aspoň jeden počítač (ten s vetším ID). Preto sa počet kandidátov každým kolom aspoň zpoloviční. Teda počet kôl je najviac log N. V každom sa pošle najvyše 2N správ. Preto výsledna zložitosť, meraná počtom správ, je O(N log N).

Program

Miro Rudišin

14-4-4 Triramidy (Zadání)

Úloha byla jednoduchá a většina z vás si s ní hravě poradila. Úkolem bylo najít největší jedničkový rovnoramenný pravoúhlý trojúhelník v matici A = {a_i,j} složené z nul a jedniček, jehož odvěsny mají svislý a vodorovný směr.

Pro zjednodušení se budeme nyní zajímat pouze o trojúhelníky mající pravý úhel vpravo dole, zbylé tři případy se vyšetří analogicky. Nechť tedy t_i,j označuje velikost odvěsny největšího jedničkového trojúhelníku majicího pravý úhel vpravo dole na prvku [i,j]. Zřejmě platí:

Pro korektnost si dodefinujme t_0,j=0 a t_i,0=0.

Všimněme si, že pro výpočet prvku t_i,j potřebujeme prvky, které mají alespoň jeden z indexů menší. Budeme-li počítat t_i,j postupně po řádkách, budeme mít vždy při určování t_i,j spočítané všechny dílčí výsledky, a tedy budeme znát i hodnotu t_i,j. Nalezmeme-li pak t_i,j s maximalní hodnotou, víme, že maximální jedničkový rovnoramenný pravoúhlý trojúhelník má dolní pravý úhel na prvku [i,j] a odvěsny velikosti t_i,j. Ostatní natočení trojúhelníku vyřešíme podobně.

Bude-li mít prohledávaná matice A velikost m ×n, budeme muset spočítat m ·n hodnot t_i,j. Každou z hodnot t_i,j počítáme v konstantním čase, tedy celková časová složitost algoritmu je lineární k velikosti matice A, tj. O(mn). Paměťová složitost je rovněž O(mn).

Program

Aleš Přívětivý

14-4-5 Turingovy stroje (Zadání)

Myšlenka vedoucí k řešení této úlohy napadla téměř všechny řešitele. Technické záležitosti při implementaci myšlenky ale zvládl málokdo. Nejčastějšími nedostatky vašich řešení bylo, že jste při kopírování obsahu pásky nepoznali konec kopírované části a začali jste kopírovat již zkopírovanou část (čímž jste vašemu stroji zajistili práci až do konce světa), či že jste nezvládli kopírování znaku Λ, který může být klidně součástí vstupu. Nikdo si pak též nevšiml drobných nedostatků v zadání – stroj nijak nedokáže zjistit, kde končí vstup, a tedy ani to, kam má posouvat obsah pásky. Stroj má také problémy, pokud se znak Λ vyskytuje uvnitř textu na pásce. Proto by správná odpověď puntíčkáře na původní zadání měla znít: „Stroje nejsou ekvivalentní.“. My si proto do zadání doplníme požadavek, aby za posledním znakem vstupního slova byl ještě připsán speciální znak ] a na výstupu budeme místo znaku Λ používat znak Λ'.

A nyní již ke vzorovému řešení. Idea řešení je jednoduchá. Budeme na našem stroji s děrnou páskou simulovat původní stroj tak, že vždy když původní TS zapisuje na nějaké políčko, tak obsah pásky celý zkopírujeme do volného místa, ale již se změněnou hodnotou zapisovaného políčka. Původní obsah pásky při kopírování zakaňkujeme. Tato myšlenka má ale několik technických háčků, které se nyní pokusíme rozřešit.

Protože si budeme potřebovat pamatovat, na jaké pozici stojí hlava, budeme mít od každého znaku dvě verze – s hlavou a bez hlavy. Dále budeme potřebovat mít nějak označený levý konec pásky (abychom nechtěně neukončili běh stroj). To nejsnáze uděláme tak, že celé vstupní slovo (tzn. až po znak ]) zkopírujeme těsně za znak ] a původní vstup zakaňkujeme. Kaňky nám budou značit levý konec pásky. Při tomto kopírování první znak zapíšeme ve formě „s hlavou“ a protože navíc budeme potřebovat odlišit znak Λ uvnitř vstupního slova a mimo něj, budeme při prvním kopírování znak Λ zapisovat jako nějaký nový znak Λ'. Náš stroj se zřejmě může při simulaci chovat, jako by místo znaků Λ' četl znaky Λ. Jak nyní bude přesně probíhat kopírování s přepisem jednoho znaku? Do stavu stroje si zapamatujeme písmeno, které má být zapsáno a posun hlavy. Nyní stroj jede doleva až k nejbližší kaňce (počátek „aktivní“ pásky), tam si načte do stavu znak a zakaňkuje ho. Znak pak přenese na první volné pole vpravo (nezapomeňte, že znaky Λ se díky jejich nahrazení uvnitř slova skutečně budou vyskytovat až za znakem ]). Takto v kopírování pokračujeme s tím, že když kopírujeme znak, kde má nově být hlava (to umíme poměrně snadno zjistit – ve stavu si pamatujeme, jakým směrem se má pohnout hlava a vždy před kopírování znaku jen zkontrolujeme, jestli náhodou není na příslušném sousedním políčku hlava), tak zapíšeme do kopie formu znaku s hlavou a pokud kopírujeme znak, který původně byl pod hlavou, tak místo něj zapíšeme znak zapamatovaný ve stavu. Kopírování končí zkopírováním znaku ] (pokud na této pozici má nově ležet hlava, tak na ni místo ] zapíšeme znak Λ' a znak ] zapíšeme až na následující pozici. Simulace stroje pak končí v okamžiku, kdy by se hlava měla přesunout nad kaňku na levém okraji pásky (na původním stroji tedy přes levý okraj pásky) – v tomto okamžiku už nám stačí jen výstupní slovo naposledy zkopírovat, přitom odstranit označení znaku s hlavou a znak ], a pak jet hlavou neustále doleva až narazí na okraj pásky.

Honza Kára