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

Celý leták, který posíláme také papírově, v PDF.

Řešení úloh

18-2-1 Potrhlý syslík (Zadání)

Většina z vás si s tímto úkolem hravě poradila. Je však nutné dodat, že samotný postup není dostačující řešení. Vždy je třeba říci, proč zvolený postup funguje. Ale i to se většině řešitelů povedlo, a tak se v rychlosti koukněme, jak by mohlo vypadat vzorové řešení.

Máme 50 mincí, 18 je otočeno lícem, zbylé jsou otočeny rubem. Oddělme libovolných 18 mincí a označme je jako první hromádku. Ostatní mince tvoří hromádku druhou. Všechny mince v první hromádce otočíme a nahlédneme, že tím je úkol splněn. Z původních 18 mincí otočených lícem se do první hromádky dostalo právě k z nich. A tedy 18-k je počet rubem otočených mincí v první hromádce. Po otočení všech mincí v této hromádce se počty rubem a lícem otočených prohodí. V první hromádce tak bude 18-k lícem otočených mincí. Ve druhé hromádce je ale již od začátku 18-k lícem otočených mincí, protože celkem jich bylo 18 a k z nich připadlo do první hromádky. Počty v obou jsou tak shodné a úloha je vyřešena.

Jak mnozí z vás také poznali, princip řešení není dán tím, že mincí bylo právě 50 a 18 bylo lícem otočených a že řešení se dá spolu se zadáním úlohy zobecnit a stále bude fungovat. Dodejme ještě, že k takovýmto úlohám není třeba psát zdrojový kód. V některých došlých řešeních se zbytečně otáčely mince tam a zase zpět, za což byl strháván jeden bodík, protože taková řešení jsou vlastně pomalejší.

David Matoušek

18-2-2 Kvakulátor (Zadání)

Vzpomenu si na ZŠ a písemné dělení "pod sebou". Tam vše záleželo na zbytcích – vyšel-li nám někdy po vyčerpání cifer čitatele zbytek 0, nemělo číslo periodu, pokud se nějaký zbytek opakoval potom, co nám došly cifry čitatele, vznikla tak automaticky perioda. Ještě předtím ale zajistím, aby a<b tak, že provedu a'=a mod b, kde mod je zbytek po dělení. Počítáním s a' místo a se mi perioda určitě nezmění. První zbytek si tedy nastavím rovnou jako z1=a mod b (zbavím se tak všech cifer a najednou a potom při dělení pod sebou "připisuji" už jen 0). Další zbytky získám postupně jako zi+1=(10 zi) mod b. Všimněte si, že cifry výsledku nás vůbec nezajímají, po nalezení opakování zbytků se budou opakovat i cifry, neboť cifra závisí jen na předchozím zbytku a b, které je pevné. Délka periody je nanejvýš b-1, protože po více než b-1 číslech 0..b-1 potkám buď 0 nebo nějaký zbytek dvakrát.

Jednodušší cesta, jak najít periodu, je pamatovat si zbytky zi v poli a pokaždé pole prohledat, zda už zbytek máme. Toto má časovou složitost O(b2) a paměťovou O(b).

Trochu chytřejší je nepamatovat si pole zi, ale zda a kde jsem již potkal zbytek z v poli az. Potom zjišťuji, zda jsem již zbytek potkal v konstantním čase a dostanu časovou i paměťovou složitost O(b).

Situaci mi komplikuje jen možná před-perioda, bez ní bych si mohl zapamatovat první zbytek a prostě si na něj počkat až ho potkám znovu. Před-perioda má ale délku nanejvýš b, stačí tedy provést prvních b dělení a zb buď bude 0 (pak je perioda 0) nebo si ho zapamatuji a až ho potkám na pozici zb+p, našel jsem periodu délky p. Časová složitost je tak pořád O(n), paměťová O(1).

Existuje i rychlejší řešení pracující v čase O(√b) nebo i lepším (hlavně podle zběsilosti použité faktorizace), ale to je příliš složité na to, abych ho zde uspokojivě popsal.

Program

Tomáš Gavenčiak

18-2-3 Jeřábník Evžen (Zadání)

Z počtu došlých řešení je jasné, že vás demolice bažiny zaujala, ale poradit Evženovi, jak ovládat jeřáb nejen spolehlivě, ale také rychle, byl pro vás oříšek. Pojďme ho tedy rozlousknout.

Jednoduché řešení problému je zapamatovat si úhel natočení každého segmentu a po každé změně výslednou pozici demoliční koule spočítat. Pokud víme počáteční bod i-tého segmentu a jeho absolutní úhel α v rovině, spočítáme z něj pozici (i+1)-ního segmentu posunutím o délku segmentu ve směru α. Takto postupným počítáním koncové pozice segmentů dojdeme až k pozici koule. Pokud máme n segmentů a dostaneme m dotazů, tento algoritmus poběží v čase O(m·n). Podobný algoritmus poslala většina z vás.

My se ovšem nespokojíme s jednoduchým řešením. Potřebujeme si zapamatovat některé pozice, abychom je nemuseli pokaždé počítat znovu. To uděláme celkem klasickou metodou — postavíme nad segmenty intervalový strom.

Předpokládejme nyní, že n je mocninou dvojky. Potom si segmenty představíme jako listy dokonale vyváženého binárního stromu. Protože počet vrcholů se na každé další hladině zdvojnásobí, je hloubka našeho stromu log2n, neboli O(log n). Pokud spočteme tuto geometrickou posloupnost velikosti hladin, dostaneme 2n-1, a tedy náš strom má celkem O(n) vrcholů.

Každý vnitřní uzel stromu u bude reprezentovat skupinu segmentů, které jsou listy podstromu s kořenem u. Tuto skupinu po sobě jdoucích segmentů si můžeme představit jako jeden dlouhý segment, který začíná na počátku prvního segmentu a končí na konci posledního segmentu.

Každý segment můžeme charakterizovat jeho délkou a relativním natočením vůči předchozímu segmentu. Pokud chceme podobně popsat i složený segment, musíme ještě přidat natočení posledního segmentu ze skupiny, protože právě ten určuje, jak bude natočen další segment. Jednoduchý segment pak má v tomto popisu oba úhly stejné.

Protože bychom ale museli pro složené segmenty složitě počítat jejich délku a vstupní úhel, zapamatujeme si rovnou souřadnice bodu, kde by tento segment končil, kdyby byl umístěn do počátku a předchozí segment mířil do kladného směru osy y. Díky tomu jsou data segmentu nezávislá na ostatních segmentech a nebudeme jich muset tolik měnit při otočení jeřábu.

Jak tedy vytvoříme složený segment? Souřadnice segmentu v označme x(v) a y(v), výstupní úhel α(v). Vezměme vnitřní uzel u, který má dva syny s1 a s2. Pak souřadnice u spočítáme jako otočení souřadnic s2 o úhel α(s1) a přičtení k souřadnicím s1. Výstupní úhel u je součtem výstupních úhlů jeho synů.

x(u) = x(s1) + x(s2)·cosα(s1) + y(s2)·sinα(s1)
y(u) = y(s1) + x(s2)·sinα(s1) + y(s2)·cosα(s1)
α(u) = α(s1) + α(s2)

Již umíme skládat segmenty a můžeme tedy ze segmentů v listech vygenerovat složené segmenty tak, že půjdeme po hladinách stromu od nejnižší k nejvyšší a budeme je popsaným způsobem plnit. Všimněte si, že odpověď na dotaz, kde je koule jeřábu, se schovává již v kořeni stromu, protože ten je složením všech dílčích segmentů.

Složitější je otázka, zda dokážeme také tuto strukturu aktualizovat po otočení nějakého segmentu. Podívejme se, kolik složených segmentů se změní při otočení jednoho segmentu. Jsou to pouze ty, které tento segment obsahují, a ty leží na cestě od listu ke kořeni. Stačí tedy při změně segmentu projít po cestě od segmentu ke kořeni a upravit všechny složené segmenty. To uděláme stejně, jako bychom je vytvářeli znova.

Jak dlouho nám to bude trvat? Již jsme si ukázali, že náš strom má hloubku O(log n) a tedy celková časová složitost je O(m· log n). Paměťová složitost je O(n), protože strom má také lineární velikost.

Ještě se podíváme na implementaci našeho algoritmu. Pokud vytváříme vyvážený strom, do kterého nechceme přidávat nebo z něj odebírat prvky, často se na to hodí použít implementaci haldy v poli. Ta má kořen na pozici s indexem 1 a synové vrcholu s indexem i jsou (v případě binárního stromu) na pozici 2i a 2i+1. Tím se často zjednoduší veškeré cestování po stromě.

Jako třešničkou na dortu se můžete inspirovat Martinovým (MJ) vzorovým řešením.

Program

Petr Škoda

18-2-4 Stavbyvedoucí (Zadání)

Ah, bezdůvodně čekáš, čtenáři drahý, ďábelské fígle, i když na obyčejný počátek prachobyčejného řešení stavbyvedoucího strastí tato věta vyznívá značně zvláštně. Demonstruje totiž jeden velice důležitý fakt: setřídit slova podle třetího písmenka, pak podle druhého (stabilně, tj. se zachováním původního pořadí, pokud jsou druhá písmenka nějakých dvou slov stejná) a nakonec podle prvního, dopadne stejně jako nejdříve je setřídit podle prvního, pak zvlášť každou skupinu začínající stejným písmenem setřídit podle druhého a skupinky mající stejné i druhé písmeno ještě podle třetího. Totéž samozřejmě platí i pro třídění tabulek podle sloupečků podle Potrhlíkových požadavků: ponejprv řádky třídíme podle sloupečku daného posledním požadavkem, skupiny se stejnou hodnotou tohoto sloupečku pak podle předchozího požadavku a tak dále, až se propracujeme k začátku seznamu požadavků nebo skončíme se skupinkami o jednom řádku. Z toho ovšem ihned plyne, že zabývat se tímtéž sloupečkem vícekrát je zhola zbytečné: pokud po prvním porovnání podle nějakého sloupečku zůstaly nějaké dva řádky v téže skupině, měly v příslušném sloupečku stejnou hodnotu, a proto nám je další porovnání musí ponechat ve stejném pořadí.

Pokud se tedy nějaký sloupeček v posloupnosti požadavků vyskytuje vícekrát, stačí ponechat jen jeho poslední výskyt. Tím určitě dostaneme posloupnost ekvivalentní se zadanou (takové budeme říkat řešení). Zbývá nám ještě dokázat, že žádné kratší řešení nemůže existovat. Kdyby existovalo, vezmeme si nejkratší takové. Určitě se v něm nebudou opakovat sloupečky (jinak by se naším algoritmem dalo ještě zkrátit) a ani v něm nebude žádný sloupeček navíc (to by byl sloupeček, podle kterého se netřídilo ani v zadané posloupnosti, takže bychom ho mohli škrtnout). Tudíž v ní musí nějaký sloupeček z našeho řešení chybět. Pak stačí vytvořit dva řádky, které se budou lišit pouze v chybějícím sloupečku, a takové musí obě řešení setřídit různě, což je evidentní podvod, totiž spor. Podobně můžeme dokázat i to, že naše řešení je nejen nejkratší, ale také jediné s touto délkou: jiné by se nutně lišilo pořadím nějakých dvou sloupečků i, j a mohli bychom sestrojit dva řádky podle i uspořádané opačně než podle j a jinak stejné a opět dojít ke sporu.

Zbývá si rozmyslet, jak naše řešení naprogramovat. Znalci Unixového shellu mohou navrhnout třeba toto:

 nl -s:|tac|sort -t: -suk2|sort -n|cut -d: -f2

My si předvedeme jednoduchý (a přiznejme, že daleko efektivnější) program v Pascalu. Bude číst vstupní posloupnost po jednotlivých prvcích a ve frontě si udržovat řešení pro zatím přečtenou část vstupu. Přijde-li požadavek na třídění podle nějakého sloupečku, přidáme tento sloupeček na konec fronty a pokud se již ve frontě vyskytoval, předchozí výskyt odstraníme. Abychom to zvládli rychle, budeme si frontu pamatovat jako obousměrný spojový seznam, tj. pro každý sloupeček si uložíme jeho předchůdce a následníka. Tak nám celá fronta zabere paměť lineární s počtem sloupečků a na každou operaci si vystačíme s konstantním časem, celkově tedy s časem O(M+N) (požadavků+sloupečků).

Ještě přidáme malý trik pro zkrácení programu: Abychom si nemuseli dávat pozor na případy, kdy je fronta prázdná, a udržovat si ukazatel na konec fronty, přidáme do fronty ještě sloupeček 0, který bude stále na začátku i na konci (fronta tedy bude zacyklená) a který pak nevypíšeme.

Program

Tomáš Gavenčiak & Martin Mareš

18-2-5 Krokoběh (Zadání)

Krokodýli šli dneska spát nalačno prakticky u všech došlých řešení a překvapivě u většiny došlých řešení byl spokojen i Potrhlík, který stavbu přežil bez bankrotu. No a nyní, jak se úloha měla řešit. Většina řešitelů (možná pod vlivem kuchařky) používala terminologii teorie grafů, proto jí i v tomto řešení použijeme.

O co tedy šlo. Zjistit, kolik nejméně hran je třeba přidat do grafu, aby se stal 2-souvislý. Hned na začátku si všimneme, že pokud najdeme v grafu komponentu, která je 2-souvislá, tak jí můžeme zkontrahovat (scvrknout) do jednoho vrcholu, aniž by se změnil počet potřebných hran. Takhle můžeme pokračovat tak dlouho, dokud se v grafu budou vyskytovat kružnice. Snadno se dá nahlédnout, že hrany tohoto zkontrahovaného grafu budou mosty v původním grafu (most není součástí žádné kružnice, proto nebude v žádném kroku zkontrahován, na druhou stranu pokud hrana není most, pak je součástí nějaké kružnice a proto bude dříve či později zkontrahována). Je také vidět, že takto zkontrahovaný graf bude les, jelikož neobsahuje kružnice. Dále budeme uvažovat tento les.

Nyní mohou nastat 2 situace. První, kterou dost řešitelů zapomnělo ve svých řešení ošetřit, je ta, že graf byl na počátku 2-souvislý, tj. že se zkontrahoval do bodu. Pak není třeba nic přidávat.

Druhá je zbytek. Kolik bude třeba hran dodat? Jelikož v 2-souvislém grafu má každý vrchol stupeň (tj. kolik hran do něj vede) alespoň 2 a hrana spojuje právě 2 vrcholy, musíme přidat alespoň A + ⌈B/2⌉   (*) hran, kde A je počet vrcholů stupně 0, B počet vrcholů stupně 1 (tj. listů) a zaokrouhluje se nahoru, jelikož v případě lichého B musíme tento lichý list také zapojit do nějaké kružnice, tedy tento lichý list zapojíme na libovolný vrchol.

Nyní, indukcí podle počtu vrcholů dokážeme, že tolik i stačí. Pro 2 vrcholy může les vypadat buď jako 2 vrcholy a pak je třeba přidat ještě 2 hrany (což splňuje vzorec (*)), nebo jsou tyto 2 vrcholy spojené hranou, a pak stačí přidat jednu (opět v souladu s (*)). Všimněme si také, že jsme v obou případech alespoň jednu hranu přidali.

Teď si uvědomíme, že libovolný les jde vyrobit z jednoho vrcholu pomocí operací:

  1. přidej vrchol (a s ničím ho nespojuj)
  2. přidej vrchol a spoj ho hranou s nějakým vrcholem, který už v lese je.

Nyní uvažujme, že pro N vrcholů máme již 2-souvislý les pomocí

  1. A + B/2 hran (pro sudé B)
  2. A + (B-1)/2 hran (pro liché B; 1 cesta nezesouvislena)

Přidejme vrchol X pomocí pravidla:

  1. Vezmeme nějakou přidanou hranu (vedoucí I↔J), tu odstraníme a přidáme místo ní hrany I↔X a X↔J. Tím nám stoupl počet přidaných hran do grafu o 1. Také A se zvětšilo o jedna, takže a), resp. b) stále platí.
  2. Při připojování X mohou nastat tři situace:
    1. Připojujeme ho hranou pod vrchol Y stupně 0. Pak ale od tohoto vrcholu vedou 2 přidané hrany. Vezmeme libovolnou z nich (nechť vede z I) a zrušíme ji. Místo ní zavedeme novou hranu I↔X. Touto operací se nám snížil počet vrcholů stupně 0 v grafu o 1, nicméně z X i Y se staly listy a proto je B o 2 vetší. Tedy a) příp. b) je stále splněno.
    2. Připojujeme ho hranou za list L. Pokud je B liché a list L je konec naší volné cesty, není třeba nic dělat a indukční předpoklady máme splněny. Jinak do tohoto listu vede nějaké přidaná hrana (z nějakého vrcholu I). Pak ale stačí zrušit hranu I↔L a zavést novou hranu I↔X. Tím zůstane počet přidaných hran zachován. L přestal být po tomto kroku listem, nicméně objevil se nový list X, tudíž A i B zůstalo a tedy a), resp. b) stále platí.
    3. Připojujeme-li ho hranou za vrchol stupně alespoň 2, pak se nám zvýší B o 1, A zůstane stejné. Pokud B bylo sudé, není třeba nic dělat. Po tomto přidání bude B liché a vrchol X bude konec nezesouvislněné cesty. Vzorec b) bude zřejmě platit. Nyní pokud je B liché, označíme si list na konci cesty Y. Pokud vrchol X napojujeme za vrchol, který nebyl součástí cesty, pak stačí přidat hranu X↔Y. Pokud napojujeme X na cestu, pak vezmeme libovolnou přidanou hranu I↔J, tu z grafu odstraníme a přidáme 2 nové I→X a J→Y. V obou případech stoupne počet přidaných hran v do lesa o 1, což je v souladu s a).

A je to. Pro sudé B jsme dostali rovnou 2-souvislý graf, pro liché musíme ještě konec cesty napojit na libovolný vrchol, který do téhle cesty nepatří, abychom dostali 2-souvislý graf. Tím se ale dostaneme na A + (B-1)/2 + 1 = A + ⌈B/2⌉ hran.

Program je implementací výše uvedeného. Pomocí algoritmu popsaného v kuchařce 2. série najde v zadaném grafu mosty a pak v každé komponentě 2-souvislosti spočítá, kolik mostů z ní vede. Nakonec spočte hrany, které je třeba přidat, pomocí (*). Časová i paměťová náročnost programu je O(M+N) (při každém průchodu do hloubky se algoritmus zřejmě na každou hranu podívá dvakrát).

Program

Pavel Čížek

18-2-6 Dominující komplikátory (Zadání)

Někteří řešitelé si prostě uložili matici relace dominance (tedy pole indexované čísly bloků, v níž na pozici [A,B] je 1 pokud basic blok A dominuje basic blok B, a 0 jinak). Toto řešení je nepraktické – na dotaz, zda jeden blok dominuje druhý, jsme sice schopni odpovědět v konstantním čase, ale paměťová složitost je O(N2), kde N je počet bloků v programu, což často bude příliš mnoho. Navíc se s touto reprezentací špatně pracuje, pokud optimalizace změní CFG, často je jediná možnost celou matici přepočítat. Dominance je ovšem velmi speciální relace, kterou lze reprezentovat mnohem efektivněji.

Začneme tím, že si zavedeme následující značení: budeme psát A≤ B, pokud basic blok A dominuje basic blok B. Samozřejmě se tím snažíme naznačit, že relace dominance by se mohla chovat jako uspořádání. Je asi vhodné si to zdůvodnit:

Dominance tedy opravdu je uspořádání, ale nemusí to být uspořádání úplné – většinou existují bloky, které jsou v ní neporovnatelné, tj. not(A≤ B) a not(B≤ A). Tím jsme si tedy příliš nepomohli, protože obecné uspořádání v lepším než kvadratickém prostoru reprezentovat nelze. Povšimneme-li si ovšem ještě následující vlastnosti, situace se značně zjednoduší: Pokud se omezíme na bloky, které dominují nějaký pevně zvolený blok C, pak je uspořádání dominancí úplné, tedy pokud A≤ C a B≤ C, pak buď A≤ B nebo B≤ A. Dokažme si toto tvrzení. Předpokládejme, že A≤ C, B≤ C a A a B jsou přitom neporovnatelné. Zvolme si libovolnou cestu p=sv1… vkC z počátku do C. Na p se musí vyskytovat jak A, tak B. Nechť bez újmy na obecnosti p projde jako poslední A, tj. existuje t tak, že vt=A a vi≠ B pro i>t. Protože not(B≤ A), existuje cesta q z počátku do A, která neprochází přes B. Pak ale cesta q, za niž připojíme vt+1… vkC, jde z počátku do C, aniž by prošla přes B, což je spor s tím, že B≤ C.

Pro každý blok C kromě počátku tedy existuje „nejpozdější“ blok, který ho dominuje (budeme mu říkat přímý dominátor bloku C a značit ho d(C)), tedy takový, že pokud A≤ C a A≠ C, pak A≤ d(C). Zřejmě A≤ C právě tehdy, pokud A=d(d(… (d(C))… )). Jestliže si nakreslíme orientovaný graf, jehož hrany jsou dvojice (C,d(C)) pro všechny bloky C, dostaneme strom, orientovaný směrem ke kořeni, jímž je počátek. Platí, že A≤ B, pokud vrchol B patří do podstromu, jehož kořen je A. Další možnost, jak si relaci dominance reprezentovat, je tedy uložit si tento strom a pak při dotazu procházet buď podstrom A, nebo následníky vrcholu B. Paměťová složitost je O(N) – stačí mít uložen tento strom. Oba postupy mají ovšem v nejhorším případě lineární časovou složitost.

Tento strom si proto ještě dále zpracujeme. Provedeme jeho prohledání do hloubky a budeme si počítat čísla kroků (tedy budeme mít čítač, který si zvýšíme o 1 pokaždé, když vstoupíme do vrcholu nebo se z něj vracíme). Pro každý vrchol C si zapamatujeme čísla i(C) a o(C) – čísla kroků, kdy jsme vstoupili do C a kdy jsme se z něj vrátili. Zřejmě A≤ B právě tehdy, když do B vstoupíme až po A, ale vrátíme se z něj předtím, než se vrátíme z A, tedy pokud i(A)≤ i(B) a zároveň o(B)≤ o(A). Paměťová složitost zůstane lineární, neboť pro každý vrchol si potřebujeme pamatovat pouze dvě čísla. Složitost dotazu bude konstantní, stačí provést dvě porovnání.

Na závěr poznamenejme, že většina algoritmů pro určení dominance přímo konstruuje strom přímých dominátorů, takže nikdy není nutné si pamatovat celou matici dominance. Zajímavá otázka je, jak popsanou datovou strukturu opravit, pokud některá optimalizace změní CFG. Strom přímých dominátorů se změní snadno, nicméně popsané očíslování se nám tím pokazí, proto je v praxi nutné použít složitější datové struktury.

Zdeněk Dvořák