Třetí série dvanáctého ročníku KSP

Řešení úloh

12-3-1 Strýček Skrblík (Zadání)

Došlá řešení byla většinou správně, ba co víc, dokonce asymptoticky optimální. Jen nekteří řešitelé potřebují data nejprve vložit do pole a pak je sekvenčně číst. Proč?

Většinou jste také zpomínali dokázat, že řešení skutečně najde úsek s minimálním součtem – zde je důkaz celkem jednoduchý (viz níže), ale je potřeba jej udělat. Pokud se to někomu zdá zbytečné, nechť uváží jinou úlohu: najdi nejdelší období s zápornou bilancí. Zdálo by se, že je to uloha velmi podobná, ba až stejná. Ale ouha…všechno je jinak. Přemýšlejte sami, já vyřeším raději původní úlohu.

Předpokládejme, že existuje aspoň jedno nekladné období. Zadefinujme nadějný úsek jako úsek s nekladným součtem takový, že pro každé i menší nebo rovné délce úseku je součet prvních i členů nekladný a nedá se již prodloužit bez porušení předchozích podmínek.

Pak:

  1. Žádné dva nadějné úseky se nepřekrývají
  2. Úsek s minimalním součtem leží v nějakém nadějném úseku, a lze jej umístit tak, aby začínal prvním prvkem tohoto úseku.

Důkaz:

  1. Nechť první úsek P začíná na i a druhý (D) na j (i<j) a D se překrývá s P a není jeho částí. Pak úsek od i do konce D je nadějný a navíc je delší než P. Tedy P nemohl být podle definice maximální v délce a tudíž ani nadějný. Spor.
  2. Pokud budeme rozšiřovat minimální úsek (přesněji úsek s minimálním součtem) na obě strany podle podmínek (nekladnost prefixu), dostaneme nutně nadějný úsek. Pokud neleží začátek min. úseku na začátku tohoto úseku, je součet prefixu nula (jinak by se nejednalo o minimální úsek), tedy můžeme minimální úsek prodloužit až k začátku úseku vnějšího.

Pokud neexistuje žádné nekladné období, správným výstupem je minimum ze zadaných hodnot.

Algoritmus nebude dělat nic jiného, než že bude hledat nadějné úseky a zkoušet, zda součet některého z jejich prefixů nebude náhodou menší než doposud nalezené minimum a případně minimum upraví. Zároveň pokud najde nějaké kladné číslo, porovná jej s minimem a taktéž je případně upraví.

Hledání nadějných úseků je jednoduché – beru postupně čísla; najdu-li záporné, pak začíná nadějný úsek, ten trvá tak dlouho, dokud je suma po každém přidání čísla nekladná. Pak pokračuje hledáním dalšího nadějného úseku.

Časová složitost je lineární, paměťová konstantní.

Program

Pavel Nejedlý

12-3-2 Vypočítavý Robin (Zadání)

Smutně rozjímaje nad družinou zamítnutým nákupem nové houfnice, jež by úlohu krajně zjednodušila, Robin nepokojně bloumal lesem. Bylo mu jasné, že triviální algoritmus s časovou složitostí O(n3) není přijatelný (každou dvojici bodů spojit se zbylými). Teprve po probdělé noci dostal nápad vybudovat všechny přímky (těch bude řádově n2), které stačí následně setřídit a zjistit počet shodných přímek. Ještě lépe - setřídit vždy podle směru přímky procházející jedním bodem. Tím se dostal již na přijatelnou úroveň O(n2 log n). Třídění mu k sobě dostane stejné přímky, na druhou stranu zbytečně třídí nestejné přímky mezi sebou. Nešlo by to bez něj? Dvé jeho uhlově černých oček zablýsklo – hashování! Nejenže dostane shodné přímky k sobě, ale navíc pro jednotlivou přímku provede 'zatřídění' v konstantním čase, což znamená výsledný algoritmus v O(n2).

K implementaci: v textu jsme používali výrazu „setřídit přímky“. Pro tuto operaci, stejně jako pro hashování je dobré mít přímku v nějakém rozumném zápisu – zde konkrétně směrnicovém tvaru s tím, že speciálně ošetříme vertikální případ. Hashovat budeme podle hodnoty směrnice, kolize různých přímek budeme řešit dynamickým seznamem pro danou hodnotu hashovací fce. Pro každou položku hashovacího pole zavedeme počítadlo, které nám bude udávat počet přímek v daném směru, procházejících právě zpracovávaným bodem. Po zpracování každého bodu musíme pročistit hashovací pole, což naštěstí časovou složitost nijak nezhoršuje. Šlo by se tomu vyhnout, pokud bychom hashovali všechny přímky najednou. To by však mělo za následek zhoršení časové složitosti, nehledě na fakt, že by se komplikovalo použití počítadla atd.

Škarohlídi namítnou, že v případě magicky zadaných souřadnic jednotlivých rytířů se v tomto případě dostaneme na O(n3) - krom toho, že je tento případ výjimečný, můžeme tyto škarohlídy potěšit tím, že lze zkonstruovat hashovací alg., jež bude mít O(n2) vždy.

Pakliže bychom zanedbali hashovací pole, bude paměťová složitost O(n). Konečnost i správnost algoritmu je zřejmá.

Několik slov ohledně strategie rytířů – u nezanedbatelného počtu řešitelů by slavilo úspěch umístění rytířů do jedné vertikální přímky, kterážto nemá směrnicové vyjádření a jejich řešení tuto skutečnost jednoduše ignorovala. (Ponechme stranou návrh sečtělého zbrojnoše na nakoupení košilí od firmy Milan Hendrych, Palackého ulice 156.)

Program

Pavel Šanda

12-3-3 Palindromický rozklad (Zadání)

V zadání nebylo bohužel dostatečně vysvětleno, co znamená rozložit, načež někteří účastníci řešili úlohu jinou, zcela triviální – nalezení všech palindromů v daném řetězci; aby toto skloubili s uvedeným příkladem, užívali nepřirozených předpokladů typu jedno písmeno není palindrom. S ohledem na to, že v případě nejasností v zadání není problém se nás zeptat, hodnotil jsem podobné snahy max. 2 body.

Nyní k samotnému řešení úlohy tak, jak byla myšlena, tj. nalézt nejmenší množinu palindromů takovou, že se navzájem nepřekrývají a pokrývají zadaný řetězec.

Jedním ze správných řešení je dynamické programování (další možností, která se vyskytla u jednoho řešitele, je převést si úlohu na hledání nejkratší cesty v grafu; jinak též lze použít backtracking s ukládáním mezivýsledků). Základní myšlenka je tato: budeme si postupně počítat nejlepší rozklady začátků zadaného řetězce o délce 1, 2, … , n (poslední z nich je hledaný výsledek). Každý rozklad (tedy i minimální) daného řetězce délky k, končícího palindromem délky l lze získat spojením rozkladu řetězce délky k-l a tohoto palindromu. Velikost takovéhoto rozkladu je o jedna větší než velikost příslušného rozkladu délky k-l. Velikost nejmenšího rozkladu o délce k-l pro každé možné l už známe, stačí tedy vzít jejich minimum pro všechna l taková, že úsek k-l+1… k je palindrom. Řešení pochopitelně vždy existuje, neboť řetězec můžeme určitě alespoň poskládat z úseků délky 1.

Při samotné realizaci programu si neustále udržujeme seznam palindromů končících na dané pozici (resp. jejich začátků). Jinak je program prostým přepisem uvedeného algoritmu.

Správnost je dokázána v popisu. Konečnost je zřejmá, neboť horní meze všech cyklů jsou omezeny n.

Složitost (n je délka řetězce):

Program

Zdeněk Dvořák

12-3-4 Skákací panák (Zadání)

Skákací panák je vlastně graf G, kde políčka jsou vrcholy a pokud jsou políčka propojena čarou, vede mezi vrcholy hrana. Navíc víme, že graf bude vlastně strom (existence právě jedné cesty mezi každými dvěma vrcholy je jednou z jeho ekvivalentních definic). Úkolem je pak nalézt hamiltonovskou kružnici v G3 (mocnina vlastně znamená, přes kolik hran najednou se může chodit). Kružnici nalezneme následujícím způsobem: Strom si zakořeníme v libovolném (třeba prvním) vrcholu. Z toho začneme strom procházet do hloubky. Pokud má vrchol, ve kterém se momentálně nacházíme, sudou vzdálenost od kořene, vrchol zašlápneme a postupně rekurzivně vyřídíme všechny podstromy. Pokud má vrchol lichou vzdálenost od kořene, nejdříve vyřídíme všechny podstromy a pak až vrchol zašlápneme. Algorimus má lineární časovou i paměťovou složitost vzhledem k počtu vrcholů.

A teď správnost algoritmu. To, že algoritmus zašlápne každé políčko právě jednou je zřejmé. Je ale třeba dokázat, že navržené přeskoky nebudou moc dlouhé. To dokážeme indukcí dle hloubky stromu. Pro stromy hloubky 0 a 1 zjevně žádný přeskok není moc dlouhý. Nechť máme strom hloubky k+1. Rozlišíme dvě možnosti:

  1. Kořen bude zašlápnutý jako první. Potom proskáčeme jeho první podstrom (z indukčního předpokladu korektně) a skončíme v jeho kořeni. Z něj pak algoritmus chce přeskočit do sousedního podstromu do hloubky dvě. To je skok přes tři, a tedy je korektní. Z indukčního předpokladu opět korektně proskáčeme i tento podstrom a opět přeskočíme přes tři do souseda. Takto korektně proskáčeme všechny podstromy a skončíme v hloubce jedna. Tento strom jsme tedy celý proskákali korektně.
  2. Kořen bude zašlápnutý jako poslední. Algoritmus tedy z indukčního předpokladu korektně proskáče jeho první podstrom a skončí v hloubce 2 (tedy pod kořenem podstromu). Z tohoto vrcholu ale snadno přes tři přeskočíme do kořene sousedního podstromu, který opět korektně proskáčeme z indukčního předpokladu. Takto tedy korektně proskáčeme všechny podstromy a skončíme v hloubce dvě odkud přes dvě hrany skočíme do kořene celého stromu. Tento strom jsme tedy také proskákali korektně.
Výše jsme ukázali, že všechny skoky budou maximálně délky tři, a tedy navržené proskákání panáka bude koretní.

Program je přímou implementací algoritmu.

Poznámka pro zvídavé: Právě zkonstruovaný algoritmus nám říká, že libovolný souvislý graf (nejen strom) lze proskákat, pokud budeme skákat přes tři (zkuste si rozmyslet proč). Tedy problém hamiltonovské kružnice v G3 je již triviální. Na druhou stranu se dá ale ukázat, že v G2 je problém stejně těžký (tedy NP-úplný), jako v G.

Program

Jan Kára

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

Nejprve popíšeme řešení v čase O(log n), kde n je počet zadaných čísel, s O(n) procesory pro P-CRCW PRAM, CREW PRAM a EREW PRAM. Poté ukážeme rychlejší (a tedy lepší) řešení pro P-CRCW PRAM, jehož časová složitost bude konstantní a které bude používat O(n2) procesorů.

Budeme postupovat podobně jako v ukázkovém programu ve studijním textu a jako při řešení úlohy v první sérii. Nechť jsou prvky posloupnosti očíslované od jedné. Program bude probíhat v několika fázích; počet fází bude ⌈ log n⌉. V k-té fázi bude l-tá buňka paměti, pro 2k|l-1, obsahovat největší číslo úseku délky 2k z naší zadané posloupnosti, který začíná l-tým prvkem. Nyní procesory, jejichž číslo l zmenšené o jedna je dělitelné 2(k+1), porovnají hodnotu v l-té a (l+2k)-té buňce a větší z nich uloží do l-té paměťové buňky. Je zřejmé, že po ⌈ log n⌉ fázích obsahuje první buňka maximum ze všech čísel v posloupnosti. V samotném programu je ještě třeba dbát na ošetření „plusmínus“ jedničkových chyb, které by mohly snadno vzniknout. Program pro EREW je rozšířen pouze o počáteční rozkopírování délky posloupnosti, které jsme již několikráte diskutovali.

Program pro P-CRCW PRAM bude založen na následující myšlence: Každé dvojici prvků (xi,xj) (dvojici bereme uspořádaně) posloupnosti přiřadíme jeden procesor – ten porovná prvky xi a xj a v případě, že xi<xj, tak tento procesor prohlásí, že prvek xi není největším prvkem v zadané posloupnosti. Prvek nebo prvky, o kterých žádný z procesorů neprohlásil, že nejsou největší, jsou zřejmě všechny stejné a zároveň jsou největší ze všech prvků v posloupnosti; tyto prvky zbývá již jen uložit do gmem[0]. Přiřazení dvojic proměnných procesorům uděláme stejně jako v řešení úlohy z druhé série. Právě popsané řešení potřebuje O(n2) procesorů a běží v čase O(1).

Program – CRCW PRAM

Program – CREW PRAM

Program – EREW PRAM

Daniel Kráľ