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

Řešení úloh

• 12-2-1: Osmisměrka
• 12-2-2: Šnečí maraton
• 12-2-3: Jednosměrky
• 12-2-4: Vysílače
• 12-2-5: PRAM

12-2-1 Osmisměrka (Zadání)

Vyřešit tuto úlohu nečinilo nikomu velký problém, horší to už bylo s efektivitou navržených algoritmů. Většina z řešitelů zvolila ten nejjednodušší algoritmus, spočívající v myšlence, že pro každé políčko osmisměrky probereme postupně všechna slova a zjišťujeme, zda na tomto políčku nezačínají. Pokud tomu tak je, označíme si u políček, které tvoří nalezené slovo, že jsou vyškrtnutá. Nakonec projdeme celou osmisměrku a vypíšeme všechna nezaškrtnutá políčka. Označíme-li si rozměry osmisměrky M a N a počet písmen ve všech slovech slovníku P, vychází nám časová složitost O(MNP) – políček je M×N, pro každé z nich musím zkontrolovat všechna slova o celkovém počtu P písmen. Paměťová složitost je O(MN+P). Každý asi pochopí proč za toto řešení nesklidil plný počet bodů.

V čem je problém a co by se dalo zlepšit? Asi není nejlepší nápad testovat pro každé políčko všechna slova, ale vytvořit si nějakou strukturu, která nám umožní vyhledat slovo ve slovníku průchodem textu od daného políčka v jednom z osmi směrů. Vyskytly se návrhy stromových struktur, které toto umožňovaly, ale většinou nebyly dotaženy do konce. Toto řešení ale vynechejme, protože si ukážeme ještě lepší algoritmus, který se od tohoto zase tak moc neliší. Hledání ve stromové struktuře probíhá v čase úměrném délce nejdelšího slova slovníku, označme tuto délku D, tedy celková časová složitost takového algoritmu by byla O(MND) plus čas na zkonstruování stromové struktury O(P) a paměťová O(MN+P). To je sice mnohem lepší než předchozí algoritmus, jelikož D je mnohem menší než P, ale naším cílem bude dosáhnout algoritmu pracujícího v čase O(MN+P).

Uvažujme jednodušší případ – máme řádek textu a chceme v něm najít a vyškrtat výskyty určitých slov v lineárním čase vzhledem k jeho délce. Pokud toto budeme umět, můžeme to provést na všechny řádky, sloupce a diagonály a budeme mít kýžený výsledek. Jak to ale provést? K tomu nám dopomohou konečné automaty – takový konečný automat si lze zjednodušeně představit jako stroj, který se může vyskytovat v různých stavech (ale vždy právě v jednom), který ze vstupu vezme jedno písmeno a přejde z aktuálního stavu do jiného (cílový stav závisí na přečteném písmenu), pak vezme další písmeno a zase přejde do nějakého stavu atd. Automat má také určité zvláštní stavy, do kterých když se dostane, znamená to, že posledních k písmen tvoří nějaké hledané slovo. Např.: Mějme automat rozpoznávající slova LES, ALES, ESO, pak při analýze textu PRALESOV po zpracování šestého písmene se automat dostane do stavu, který znamená, že zatím přečtený text končí na slova ALES a LES, a po zpracování sedmého písmene, do stavu indikujícího, že na konci prozatím přečteného textu je slovo ESO.

Pro náš případ bude postačující, když si automat po zpracování každého písmene někam poznamená délku nejdelšího z hledaných slov, které tvoří konec (příponu) prozatím přečteného textu – jestliže žádné takové slovo neexistuje bere délku nulovou. Tedy po skončení práce obdržíme od konečného automatu pole, ve kterém bude pro každé písmeno textu délka nejdelšího slova ze všech hledaných, která jsou obsažena v textu a končí v tomto písmeni – pro výše uvedený příklad bude výsledek (0,0,0,0,0,0,4,3,0). Podle takového pole už určitě dokážeme v lineárním čase vzhledem k jeho délce (a tedy i délce analyzovaného textu) vyškrtat písmena obsažená v nalezených slovech. Zbývá ještě ukázat, že dokážeme efektivně zkonstruovat automat pro libovolný slovník. To lze pomocí algoritmu Aho-Corasickové s časovou a paměťovou složitostí O(P), tedy celý algoritmus na luštění osmisměrek využívající konečných automatů má celkovou časovou i paměťovou složitost O(MN+P). Že to lépe nelze, je vidět z faktu, že tento čas potřebujeme už jen k načtení slovníku a osmisměrky. Správnost algoritmu, zde dokazovat nebudu, ale poznatků chtivý čtenář se může podívat do studijního textu J. Pavelka, M. Chytil: Algoritmy. Významná část textu je v upravené podobě k dispozici zde.

Program

Aleš Přívětivý

12-2-2 Šnečí maraton (Zadání)

Ke zjištění celkového pořadí budeme postupně umísťovat šneky podle vzrůstajících pořadových čísel. Pak se každý šnek umísťuje až po umístění všech šneků s menším pořadovým číslem a mám tedy jednoznačně danou jeho pozici vůči těmto šnekům.

První šnek nemohl zřejmě nikoho s menším pořadovým číslem předběhnout, zařadíme ho tedy na první místo. Obecně předběhnul-li šnek s pořadovým číslem k celkem s_k šneků s menším pořadovým číslem, vložíme ho na k-s_k-té místo v rekonstruovaném pořadí. Umísťování dalších šneků s vyššími pořadovými čísly doprostřed tohoto pořadí už neovlivní vzájemné pořadí již umístěných šneků podle zadání úlohy. Toto pořadí je tedy korektní a jediné možné.

Nyní už zbývá jediná otázka: volba použité datové struktury pro průběžné ukládání rekonstruovaného pořadí šneků. Máme několik možností:

1. pole – pak ovšem musíme při vložení každého šneka doprostřed posunout všechny další šneky o 1 místo doprava, což zabere O(n) času,
2. spojový seznam – pak snadno vložíme šneka doprostřed seznamu, zato nám však bude dlouho trvat nalezení příslušné pozice, zabere nám to také O(n) času,
3. binární strom – pokud bude tento strom vyvážený, zabere nám jak vyhledání příslušné pozice, tak vložení šneka O(log n) času.

Pořadí tedy budeme reprezentovat binárním stromem. V každém uzlu u budou uloženy tyto informace: číslo šneka u->cislo, počet šneků v levém podstromu u->vlevo a ukazatele na levého a pravého syna u->l, u->p.

Při umísťování k-tého šneka nejprve vypočítáme jeho průběžné pořadí p=k-s_k. Dokud nenalezneme list stromu, provádíme tyto operace:

1. Je-li p≤ u->vlevo, musíme šneka umístit do levého podstromu. Má-li u levého syna, posuneme se na něj (u = u->l). V opačném případě jsme nalezli list stromu a končíme hledání.
2. Je-li p>u->vlevo, musíme šneka umístit do pravého podstromu. Předtím však musíme odečíst počet vrcholů v levém podstromu a ještě jedničku za aktuální uzel, neboť tyto šneky jsme právě skokem do pravého podstromu přeskočili. Přiřadíme tedy p -= u->vlevo+1. Má-li u pravého syna, posuneme se na něj (u = u->p), jinak končíme hledání.

Nyní známe budoucího otce vytvářeného uzlu. Vytvářený uzel bude listem našeho stromu, vynulujeme tedy ukazatele na oba syny a počet vrcholů v levém podstromu. Uložíme do něj číslo ukládaného šneka a připojíme jej k otci. Zbývá nám jen aktualizovat počty vrcholů u->vlevo ve všech uzlech od našeho listu až ke kořenu stromu. Pokaždé, když jsme se při hledání pozice přesunuli na levého syna, vložili jsme 1 uzel navíc do jeho levého podstromu, takže ve všech takových vrcholech po cestě ke kořenu inkrementujeme u->vlevo.

Oba průchody (dolů při hledání pozice a nahoru při aktualizaci u->vlevo) budeme implementovat jednou rekurzivní procedurou vloz_sneka.

Pozn. pro puntičkáře: Tohle všechno nám ještě nezaručuje logaritmickou nářočnost operací hledání a vkládání. Pokud bude pořadí šneků nešťastně zvolené, pak nám strom může degenerovat až na spojový seznam – např. tehdy, když bude vstupní pořadí šneků již setříděné a my budeme muset vkládat uzly vždy jen do levého resp. pravého podstromu. Pro tyto účely byly navrženy různé modifikace binárních stromů, které strom různými způsoby vyvažují – např. AVL stromy nebo 2–3 stromy. Bohužel implementace operací INSERT a FIND je u nich o něco složitější a je nad rámec tohoto příkladu. Volba použité datové struktury nicméně nic nemění na charakteru řešení, takže budeme tento problém ignorovat. Stejně je v průměrném případě časová složitost logaritmická i u obyčejných binárních stromů, takže toho moc nezkazíme.

Časová náročnost algoritmu je tedy O(n log n), paměťová O(n).

Program

Robert Špalek

12-2-3 Jednosměrky (Zadání)

Úlohu si nejdříve (víceméně z cvičných důvodů) přeformulujeme na problém z teorie grafů. Je dáno N vrcholů (v zadání křižovatek) a hrany mezi nimi (v zadání cesty mezi křižovatkami). Úkolem je hrany zorientovat tak, aby se šlo po zorientování dostat z každého vrcholu do každého (říkáme, že graf má být silně souvislý).

A nyní jak tedy danou orientaci hran nalézt (případně zjistit, že taková orientace neexistuje). Graf budeme z libovolného (třeba prvního) vrcholu prohledávat do hloubky (vezmeme vrchol a na každého souseda, ve kterém jsme dosud nebyli se rekurzivně zavoláme. Když jsme takto zpracovali všechny sousedy, vrátíme se). Hrany budeme orientovat ve stejném směru, v jakém jsme přes ně přešli (případně se přes ně dívali na sousední vrcholy).

Navíc si u každého vrcholu budeme pamatovat, jako kolikátý jsme ho navštívili. Při prohledávání si pak budeme pamatovat nejnižší pořadí vrcholu, do kterého jsme se pokoušeli přejít (ale nepřešli jsme, protože jsme v něm už byli). Vždy když se vracíme z nějakého vrcholu, tak zkontrolujeme, jestli je nejnižší nalezené pořadí menší, než pořadí vrcholu, ze kterého se vracíme. Pokud ne, tak orientace hran nemůže existovat. To plyne z následujícího: Protože nejnižší nalezené pořadí je větší než nebo stejné jako pořadí vrcholu, ze kterého se vracíme, nemůže existovat hrana z oblasti „pod“ tímto vrcholem do oblasti „nad“ tímto vrcholem (když se vracíme, prošli jsme již celou dosažitelnou oblast a vyzkoušeli všechny hrany z ní). Jediná hrana propojující tyto oblasti je tedy ta, po které se nyní vracíme. Ať ji ale zorientujeme jakkoliv, vždy se nepůjde dostat buď z oblasti „nad“ do oblasti „pod“, nebo opačně.

Když prohledávání skončí, otestujeme, zda jsme se dostali do všech vrcholů. Pokud ne, graf nebyl ani souvislý a síť tedy zřejmě neexistuje. Pokud ano, přiřazená orientace bude hledaná orientace. Proč? Protože pokud mezi dvěma vrcholy vedla hrana, tak se mezi nimy půjde dostat i po orientaci – vždy když jsme se z nějakého vrcholu po nějaké hraně vraceli, tak jsme zkontrolovali, že se z oblasti „pod“ tímto vrcholem dostaneme do oblasti „nad“, a tedy speciálně že se z tohoto vrcholu dokážeme dostat do vrcholu, do kterého se nyní vracíme proti směru hrany. Jedním směrem se tedy půjde dostat po hraně, druhým po nějaké cestě. Protože původní graf byl souvislý, existovala mezi každými dvěma vrcholy cesta – posloupnost hran. Protože každé dva vrcholy spojené hranou v původním grafu jsou spojené nějakou orientovanou cestou v našem zorientovaném grafu, můžeme orientovanou cestu mezi libovolnými dvěma vrcholy získat jako spojení cest odpovídajících jednotlivým hranám na neorientované cestě (pokud bychom chtěli být korektní, je třeba říci, že spojením nezískáme cestu, ale sled – posloupnost hran, kde se mohou jednotlivé hrany opakovat. Z toho lze ale cesta snadno vytvořit).

Algoritmus má časovou složitost O(M + N), kde M je počet hran a N je počet vrcholů. Program je přímou implementací algoritmu.

Program

Jan Kára

12-2-4 Vysílače (Zadání)

Drtivá většina řešitelů užila triviální algoritmus – probrat všechny dvojice vysílačů. Pochopitelně se v žádném z těchto řešení nevyskytly vážnější chyby; asi polovina z řešitelů si uvědomila, že při porovnávání vzdáleností dvojic se stačí zabývat jejich druhými mocninami, což vede k jistému zrychlení, i když časová složitost je pořád O(n²).

K řešení použijeme metodu Rozděl a panuj. Zadané body si nejprve setřídíme podle souřadnice x.

Správnost algoritmu je zřejmá z popisu; konečnost plyne z toho, že v každém kroku se nám velikost vyšetřované množiny bodů zmenší alespoň o 1.

Složitost (n je počet vysílačů):

• Čas: V každém kroku potřebujeme kromě rekurzivního vyvolání sebe sama lineární čas, tedy t(n)=k*n+2t(

  n

  2

  )=k*n+2k*

  n

  2

  +4t(

  n

  4

  )=… =k*n log n+nt(1), tedy O(n log n).
• Paměť: Kromě rekurze logaritmické hloubky užíváme pouze dvě pole lineární velikosti, tedy O(n).

Program

Zdeněk Dvořák

12-2-5 PRAM (Zadání)

Nejprve zkusme vyřešit zadanou úlohu pomocí pouze jednoho procesoru. Použijeme klasický školní algoritmus pro sčítání (samozřejmě upravený pro binární čísla) – sečteme dvě cifry nejnižšího řádu, pokud je součet větší než jedna, odečteme dvojku a „zapamatujeme“ si jedničku. Poté sečteme dvě předposlední cifry, pokud si „pamatujeme“ jedničku, zvětšíme součet o jedna, a použijeme stejný postup. Časová složitost řešení je lineární s délkou čísel (délku sčítaných čísel dále označujme n). Většina došlých řešení měla taktéž časovou složitost lineární, ale používala n procesorů, a tedy byla horší než řešení neparalelní. Byla dle toho i patřičně obodována. Obecně platí: Jednoprocesorové stejně rychlé řešení je lepší než řešení s více procesory.

Z algoritmu pro jeden procesor je vidět, že kdybychom již měli spočítané přenosy pro všechny řády, pak bychom dokázali vypočítat součet na libovolném typu PRAMu v konstantním čase. Zkusme si tedy rozmyslet, jak lze rychle spočítat všechny přenosy. Označme a_i cifry prvního čísla (a_n je cifra nejnižšího řádu, jedniček), b_i cifry druhého čísla a c_i přenos mezi i-tým a (i+1)-vým řádem; i-tá cifra výsledku je tedy (a_i+b_i+c_i) mod 2. Zkusme zformulovat jasněji pravidla pro výpočet c_i:

• Pokud je a_i i b_i nula je c_i-1 nula.
• Pokud je a_i i b_i jedna je c_i-1 jedna.
• Pokud je jedno z a_i a b_i nula a jedno jedna je c_i-1 rovno c_i, pro i=n je c_i nula.

Tyto podmínky lze rovněž přeformulovat následovně: c_i je jedna právě tehdy, pokud mezi daným řádem a nejbližší dvojicí jedniček na nižším řádu není žádná dvojice nul; formálně: právě tehdy, pokud existuje j>i takové, že a_j=b_j=1 a pro všechna i<k<j je právě jedno z a_k a b_k rovno jedné. To je návod na algoritmus pro výpočet přenosu v konstantním čase s O(n²) procesory. Procesorům budou přiřazeny dvojice čísel [k,l] (0≤ k<l≤ n), procesory s větším l budou mít nižší prioritu (větší číslo). Procesor prohlásí c_k rovno nule, pokud a_l=b_l=0 a rovno jedné pokud a_l=b_l=1. Správnost algoritmu plyne ihned z naší reformulace podmínky pro výpočet přenosů. Časová složitost je konstantní, paměťová je O(n²) a počet použitých procesorů je O(n²).

Při vytváření verze pro CREW a EREW použijeme osvědčený trik s rozkopírováváním jedné hodnoty na n kopií v čase O(log n). Nejprve namnožíme gmem[0] všem procesorům (teď jich je kvadraticky mnoho, ale log n²=2 log n=O(log n)). Pak procesory spočtou hodnoty -1,0,1 (obsah lmem[4] v programu pro CRCW), které určují, zda přenos přes danou cifru „prochází“, „zastaví se“ nebo zde „vznikne“. Tyto hodnoty se spočtou a rozkopírují do n identických polí délky n+1. Následně se určí pro všechna 0≤ i≤ n první hodnota v této posloupnosti za pozicí i různá od -1; ta určuje přenos na pozici i. Vypočítat součet je již pak triviální. Časová složitost takto navrženého algoritmu je O(log n), paměťová složitost je O(n²) a počet použitých procesorů je O(n²). Poznamenejme, že opatrnějším výpočtem přenosů lze docílit paměťové složitosti O(n) s O(n) použitými procesory. Napsat program je nyní již (nudnou) technickou záležitostí. Rozkopírovávací části jsme nahradili komentářem; každý si je jistě zvládne v případě potřeby doplnit sám (viz např. vzorové řešení úlohy z první série).

Program – CRCW PRAM

Program – CREW PRAM

Program – EREW PRAM

Daniel Kráľ