Druhá série dvacátého devátého ročníku KSP

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

• Termín série: 5. prosince 2016
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

• Odměna série: Sladkou odměnu pošleme každému, kdo získá alespoň polovinu bodů z pěti odevzdaných úloh.

Zadání úloh

• 29-2-1: Cesty do školy
• 29-2-2: Hledání pomsty
• 29-2-3: Billboardová většina
• 29-2-4: Nejsložitější záhon
• 29-2-5: Plánování návštěv
• 29-2-6: Souvislá plocha
• 29-2-7: Strom ve stromu

29-2-1 Cesty do školy (10 bodů)

Studentka se chce dostat do školy za právě K minut – ne více, ale ani ne méně (to by musela zbytečně čekat na chodbě). Zajímalo by ji, kolika různými způsoby to jde udělat. Protože venku už začíná být docela zima, nechce se ani po cestě nikde zastavovat. Raději celých K minut stráví chůzí, i kdyby to znamenalo trochu si zajít, nebo třeba jít kus tam a zpátky.

K dispozici má mapu, ve které je zakresleno N význačných míst – kromě startovního a cílového bodu (koleje a školy) také různé křižovatky a další místa, přes která je možné procházet. Dále mapa obsahuje seznam povolených přesunů: každá jeho položka říká, že z místa i jde dojít na jiné místo j, a to za přesně jednu minutu. Jinudy než podle povolených přesunů se pohybovat nelze. Pozor, u přesunů záleží na směru. Může se stát, že je povoleno jít z i do j, ale ne z j do i (třeba protože v opačném směru je to moc do kopce).

Formálněji: je dán orientovaný graf. Jeho vrcholy odpovídají místům a hrany povoleným přesunům. Zajímá nás, kolik v něm existuje různých sledů mezi danými dvěma vrcholy s a t dlouhých přesně K hran. Sled je něco jako cesta, jen se na něm mohou opakovat vrcholy a hrany.

Uvažujme například následující mapu a K=6, s=a, t=g:

V ní existuje právě pět sledů délky 6 vedoucích z a do g. Jsou to abcdefg, abfgefg, abdgefg, abdefdg, abfdefg.

Řešení

29-2-2 Hledání pomsty (13 bodů)

Předpokládejme, že text na nástěnce je zašifrovaný jednoduchou substituční šifrou. Ta funguje tak, že pro každé písmeno abecedy nahradíme všechny jeho výskyty v původním textu nějakým jiným písmenem (např. každé A změníme na X, každé B na U atd.).

Navíc platí, že dvě různá písmena nikdy nenahradíme stejným, protože pak by se text nedal jednoznačně dešifrovat. Předpisu, které písmenko nahrazujeme kterým, se říká klíč.

Korektními způsoby, jak zašifrovat slovo PAPIR, jsou např. UWUXI nebo PEPZN, ale nikoli SDFGH (každé P jsme nahradili za něco jiného) nebo naopak CLCKC (P i R jsme nahradili stejným písmenem).

Dostanete zašifrovaný text (neznámým klíčem) a hledaný řetězec (nezašifrovaný). Vaším úkolem je najít všechny pozice, na kterých se v původním textu mohl zadaný řetězec vyskytovat. Různé výskyty mohou předpokládat různé klíče.

Například slovo POTOPA v textu ZAGHAHGZGHLQWUW můžeme najít na dvou místech:

  POTOPA
ZAGHAHGZGHLQWUW
     POTOPA

V prvním případě klíč překládá P→G, O→H, T→A, A→Z. Ve druhém je správné přiřazení P→H, O→G, T→Z, A→L.

Snadno si rozmyslíte, že jinde už se toto slovo vyskytovat nemůže.

Řešení

29-2-3 Billboardová většina (13 bodů)

Erika probíhá ulicemi, kde visí spousta volební reklamy: billboardy, plakáty, …Víme, v jakém pořadí okolo reklamních materiálů proběhla a které strany propagovaly.

Rádi bychom uměli pro libovolnou část její cesty zjistit, jestli v tomto úseku měla nějaká strana nadpoloviční většinu reklamních materiálů (a tedy by přesvědčila lidi, kteří projdou jen tuto část cesty).

Na vstupu dostanete nejdřív posloupnost N přirozených čísel (a₀, … , a_N-1). Ta udává, které strany propagují jednotlivé plakáty, v pořadí, v jakém je Erika míjela (tedy a_i je číslo strany propagované i-tou reklamou). Čísla stran můžou být libovolně velká.

Poté bude následovat Q dotazů. Každý dotaz je tvořen dvojicí čísel (k, ℓ). Úkolem vašeho algoritmu je pro každý dotaz určit, zda v úseku a_k,a_k+1,… ,a_ℓ-1 posloupnosti má nějaké číslo strany nadpoloviční zastoupení.

Například pro posloupnost

Vyhodnocovat každý dotaz zvlášť by bylo pomalé. Zkuste si na začátku pro posloupnost něco předpočítat, abyste pak zvládli dotazy vyřizovat rychleji. Předpokládejte, že počet dotazů bude řádově srovnatelný s N.

Řešení

29-2-4 Nejsložitější záhon (9 bodů)

Na náměstíčku tvaru N-úhelníku jsou různé chodníčky, které jsou ale vedené tak, že se navzájem nekříží a vycházejí jen z pomyslných rohů, nikoliv ze samotných stran.

Oblasti mezi chodníčky tvoří květinové záhony. Nás by zajímalo, který záhon má nejsložitější tvar, tedy je tvořen mnohoúhelníkem s nejvíce stranami.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Na prvním řádku vstupu dostanete čísla N a K udávající počet vrcholů N-úhelníka a počet chodníčků. Na dalších K řádcích následuje popis chodníčků – každý chodníček je určen dvěma čísly udávajícími, mezi kterými dvěma vrcholy náměstíčka vede. Vrcholy číslujeme od 0 do N-1 v pořadí na obvodu.

Formát výstupu: Na výstup na prvním řádku počet vrcholů na obvodu největší souvislé oblasti (záhonu) a na druhém řádku mezerou oddělená čísla zajímavých vrcholů ohraničujících tuto oblast – to jsou takové vrcholy, kde přecházíme z jednoho chodníčku na druhý. Čísla vypište v rostoucím pořadí, v jakém se vyskytují na obvodu této oblasti. Pokud existuje více takových oblastí, vyberte libovolnou.

8 3
5 1
0 5
2 4

4
0 5

Nejsložitější záhon má tvar čtyřúhelníku – můžeme si vybrat (1,2,4,5) nebo (0,5,6,7). Na prvním jsou významné všechny body, na druhém jen body 0 a 5.

Řešení

29-2-5 Plánování návštěv (10 bodů)

Petr stráví příštích N týdnů ve Švédsku. Každý z jeho K kamarádů by rád přijel na návštěvu. Každý víkend může Petr ubytovat právě jednoho svého kamaráda. Zároveň se kvůli různým již naplánovaným akcím každému z kamarádů hodí právě 2 víkendy.

O každém z kamarádů se dozvíte, které 2 víkendy by se mu pro návštěvu hodily. Rozhodněte, zda se mohou u Petra vystřídat všichni, nebo zda bude muset Petr některé odmítnout.

Můžete předpokládat, že K ≤ N.

Řešení

29-2-6 Souvislá plocha (11 bodů)

Několik skupin lidí se přetahuje o určitý předmět. Do tabulky o R řádcích a S sloupcích barvami vyznačujeme, kdo ho vlastnil který den. Zakreslujeme po řádcích, když dojdeme na konec řádku, pokračujeme na dalším.

Informace k nám ale chodí, jen když se majitel změní. Dostaneme tak třeba informaci, že první skupina měla předmět 5 dní, druhá skupina 2 dny, první skupina 3 dny, …

Nejúspěšněji působí skupina, jejíž barva je nejvíc vidět, a nejvíc vidět je souvislá oblast. Oblast je souvislá, když jsou v ní všechna políčka sousední, tj. sdílí hranu (nestačí sousedit rohem). Nás zajímá zejména to, která skupina má největší souvislou oblast.

Předpokládejte, že skupin je málo, maximálně 200. Naopak tabulka může být obrovská, počítejte s tím, že se vám nemusí vejít do paměti. Ale jeden řádek se do paměti určitě vejde.

Na vstupu dostanete čísla R, S, K, Z, popisující rozměry tabulky, počet změn skupin a počet změn vlastnictví (včetně prvotního získání). Na dalších Z řádcích jsou popsané jednotlivé změny vlastnictví — vždy která skupina předmět získala a na jak dlouho. Na výstup vypište číslo skupiny, které patří největší souvislá oblast.

3 10 2
0 2
1 2
0 2
1 2
0 4
1 6
0 12

0

Tabulka z příkladu vypadá následovně:

Největší souvislou oblast má skupina 0 (na obrázku šedá).

Řešení

29-2-7 Strom ve stromu (15 bodů)

V druhém dílu našeho stromového seriálu ukážeme, jak popisovat podstromy pomocí DFS očíslování. Hlavně si ale předvedeme, jak vytvářet datové struktury pro stromy tím, že daný strom uložíme do úplně jiného stromu, totiž intervalového.

DFS očíslování

Začněme opakováním z minula. Spustíme-li na zadaném stromu prohledávání do hloubky (DFS), můžeme jeho průběh popsat posloupností levých a pravých závorek: levou zapíšeme, kdykoliv shora vstoupíme do vrcholu, pravou, jakmile se chystáme vystoupit nahoru.

Například pro strom na obrázku vyjde posloupnost závorek ((()(()(()())))()). Každému vrcholu jsme takto přidělili jeden pár závorek a tyto páry se navzájem nekříží (říkáme, že tvoří dobré uzávorkování).

Navíc si ke každému vrcholu v zapamatujeme čísla in(v) a out(v). Ta budou říkat, na kolikáté pozici v řetězci závorek se nachází levá, resp. pravá závorka odpovídající vrcholu v. Pro náš ukázkový strom to vyjde takto:

Můžeme si to představit také tak, že máme nějaké hodiny (počítadlo), které odtikávají jednotlivé kroky DFS, a hodnoty in a out pro daný vrchol udávají čas prvního vstupu a posledního výstupu.

Všechny iny a outy dokážeme spočítat v lineárním čase. Potom nám prozradí ledacos zajímavého o tvaru stromu. Například pomocí nich můžeme poznat vzájemný vztah dvou vrcholů. Představme si nějaké dva vrcholy u a v:

• Pokud u je potomkem v (ať už přímým či nepřímým), musí být pár závorek patřících k u uvnitř toho od v, takže musí platit
  in(v) < in(u) < out(u) < out(v).
• Pokud je naopak v potomkem u, dostáváme
  in(u) < in(v) < out(v) < out(u).
• V ostatních případech musí jeden pár závorek skončit, než druhý začne (páry se přeci nekříží), takže nastane jedna z těchto možností:

  	in(u) < out(u) < in(v) < out(v),
  	in(v) < out(v) < in(u) < out(u).

Dovedeme tedy v konstantním čase zjistit, jaký je „příbuzenský vztah“ u a v.

Nestromové hrany

Občas se potkáme s případy, kdy mezi vrcholy stromu vedou ještě nějaké další hrany, které nejsou přímo součástí stromu (jako když vánoční stromeček ozdobíme řetězy). Těmto hranám říkáme nestromové a často nás zajímá, mezi jakými částmi stromu vedou.

Úkol 1 [2b]

Je dán strom na n vrcholech a m nestromových hran. Předpočítejte v čase O(n+m) tabulku a pak pomocí ní v konstantním čase odpovídejte na dotazy typu „vede nějaká nestromová hrana ven z podstromu s kořenem v?“.

Intervalové stromy

Brzy se nám bude hodit uložit všechno, co víme o daném stromu, do šikovné datové struktury – překvapivě opět stromové (její struktura má ale s podobou původního stromu pramálo společného).

Intervalový strom je datová struktura, která si pamatuje nějakou posloupnost x₁,… ,x_m a umí s ní provádět následující operace:

• Init(x₁,… ,x_n) – inicializace – O(n)
  vytvoří nový strom se zadanými hodnotami
• Get(i) – bodový dotaz – O(log n)
  vrátí aktuální hodnotu x_i
• Set(i,t) – bodový update – O(log n)
  nastaví x_i na hodnotu t
• RangeMin(i,j) – intervalový dotaz – O(log n)
  spočítá minimum z x_i, x_i+1, … , x_j
• RangeAdd(i,j,δ) – intervalový update – O(log n)
  přičte ke všem prvkům x_i,… ,x_j hodnotu δ

Existuje mnoho verzí intervalových stromů. Ty nejjednodušší popsané v naší kuchařce neumí intervalový update, ale zato dokáží provádět bodové dotazy v konstantním čase. Nám se bude více hodit pokročilejší podoba s líným vyhodnocováním změn. Ta už zvládne všechny operace. Detaily si prosím přečtěte v Medvědově knížce, v kapitole o datových strukturách.

Operace intervalového stromu lze navíc snadno ohýbat, aby počítaly něco trochu jiného. Intervalové dotazy mohou kromě maxima počítat třeba minimum nebo součet; intervalový update může například najednou nastavit všechny prvky v intervalu na novou hodnotu. Princip zůstává stejný. (Kdykoliv ale při řešení seriálu budete potřebovat nějakou atypickou operaci, nestačí si ji vymyslet – je nezbytné popsat, jak přesně ty standardní upravíte.)

Strom ve stromu

Pojďme si hrát. Dostaneme nějaký strom T, v jehož každém vrcholu je uloženo jedno číslo, na počátku nulové. Chceme umět provádět dvě operace: změnit číslo uložené ve vrcholu a zjistit minimum ze všech čísel uložených v zadaném podstromu.

To je něco podobného, jako umí intervalové stromy, ovšem s podstromy namísto intervalů. Pojďme jim tedy vstup trochu „předžvýkat“. Strom „rozvineme“ do posloupnosti podle toho, jak jím prochází DFS. Pro každý vrchol v definujeme x_in(v) jako číslo uložené ve v a x_out(v) = +∞.

Tím vznikla posloupnost délky 2n. V ní podstrom ležící pod vrcholem v odpovídá intervalu x_in(v), … ,x_out(v). Pro výpočet minima podstromu tedy stačí položit intervalový dotaz (nekonečna v out-ech výsledek nijak neovlivní). Změna hodnoty vrcholu v je triviální: požádáme intervalový strom o bodový update prvku x_in(v), na x_out(v) není třeba sahat.

Obě operace tedy pracují v čase O(log n), jen nesmíme zapomenout, že jsme také spotřebovali čas O(n) na vytvoření intervalového stromu.

Ukázali jsme tedy, jak pomocí DFS očíslování překládat strom na posloupnost, přičemž podstromy se přeloží na intervaly v posloupnosti. S těmi se pak často hodí zacházet pomocí nějakého druhu intervalového stromu. Pojďme si to vyzkoušet na dalších příkladech…

Úkol 2 [4b]

Vytvořte datovou strukturu pro strom s obarvenými vrcholy. Na počátku jsou všechny vrcholy zelené. Chceme umět provádět tyto operace: SetColor(v,c) – nastaví barvu vrcholu v na červenou, zelenou nebo modrou; CountColor(v,c) – zjistí, jaká barva je v podstromu pod vrcholem v nejčastější (je-li to nerozhodně, odpoví, že nerozhodně).

Úkol 3 [6b]

Ještě jedna datová struktura. Na začátku dostaneme strom s vrcholy ohodnocenými přirozenými čísly, Chceme umět operaci Touch(v), která v podstromu pod v provede následující: nalezne minimum z nenulových čísel ve vrcholech, toto minimum od všech nenulových čísel odečte a nakonec ohlásí, jestli už se povedlo všechna čísla v podstromu vynulovat.

Dvojrozměrné intervalové stromy

Další zajímavé triky můžeme provádět s dvojrozměrnými intervalovými stromy. Do těch ukládáme dvojice čísel, které si můžeme představovat jako body v rovině. Roli intervalů pak hrají libovolné obdélníky.

Pro naše účely postačí velmi jednoduchá podoba 2D intervalových stromů, která umí takovéto operace:

• Init((x₁,y₁),… ,(x_n,y_n)) – inicializace – O(n log n)
  vytvoří nový strom s body o zadaných souřadnicích
• RangeCount(x_min,x_max,y_min,y_max) – obdélníkový počítací dotaz – O(log ² n)
  spočítá, kolik ze zadaných bodů leží v daném obdélníku, tedy pro kolik různých i je x_min ≤ x_i ≤ x_max a současně y_min ≤ y_i ≤ y_max.

Jak takový 2D strom sestrojit, najdete například ve vzorovém řešení úlohy 24-4-7, dokonce včetně mazaného triku, který zrychlí intervalový dotaz na O(log n).

V následujícím úkolu nás ale konkrétní implementace nemusí zajímat, stačí použít 2D strom jako černou skříňku.

Úkol 4 [3b]

Dostaneme strom s nestromovými hranami. Chceme si něco předpočítat tak, abychom uměli rychle odpovídat na dotazy typu „existuje nestromová hrana mezi podstromem pod u a podstromem pod v?“.

Martin „Medvěd“ Mareš

Řešení