Pátá série začátečnické kategorie třicátého pátého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
35-Z5-1 Jen tak mimochodem (Zadání)
Úlohu můžeme přirozeně rozdělit na dva podproblémy: nalezení všech míst v textu, kde začíná/končí nějaká odbočovací/vracecí fráze, a pak samotné odstranění všech (i vnořených) odboček.
Na rozehřátí vyřešíme verzi úlohy, kde se odbočky píšou do závorek, tj. odbočovací a vracecí fráze je právě jedna, a to otevírací, respektive zavírací kulatá závorka. Pak umíme lehce poznat, kde v textu začíná a končí odbočka, a můžeme se soustředit na druhý problém.
Budeme text procházet znak po znaku zleva doprava a udržovat si úroveň zanoření, tj. v jak hluboké odbočce se nyní nacházíme. Na začátku je úroveň nula (nejsme v žádné odbočce), a kdykoliv narazíme na otevírací závorku, zvýšíme úroveň zanoření o jedna, a kdykoliv na zavírací, naopak úroveň o jedna snížíme. Můžeme si rozmyslet, že úroveň nikdy neklesne pod nulu (to bychom museli někde mít víc zavíracích než otevíracích závorek) a že aktuální znak chceme vypsat právě tehdy, je-li aktuální zanoření na úrovni nula.
Takový algoritmus má časovou složitost O(N), kde N je délka vstupního textu, protože pro každý znak provádíme jen konstantně mnoho práce.
To bychom měli, jak teď ale vyřešit plnou úlohu, kde odbočovacích i vracecích frází může být více a můžou být víceznakové? To je v plné obecnosti těžké – můžou se dít všemožné divné věci, například můžeme mít dvě odbočovací fráze, kde jedna je podřetězcem druhé, nebo odbočovací a vracecí fráze, co se v textu překrývají. Naštěstí v zadání slibujeme, že žádné takové případy nenastanou.
Budeme dělat to samé, jako doposud, jen detekce odbočení nebo vrácení bude
složitější. Namísto kontrolování, zda je aktuální znak (, musíme projít
všechny odbočovací fráze a pro každou zkontrolovat, zda v textu na aktuální
pozici nezačíná. V řetězcové notaci: ptáme se, zda S[i : i + |O|] = O, kde
i je aktuální pozice, S vstupní řetězec, O aktuální fráze a |O| její
délka. Podobně pro kontrolu vrácení projdeme všechny vracecí fráze a
zkontrolujeme, zda před aktuální pozicí končí, tj. zda S[i - |V| : i] = V.
Můžete si rozmyslet, proč by byl výstup špatně, kdybychom se místo toho opět
ptali, zda V na aktuální pozici začíná. Při implementaci si v obou případech
si také před samotným porovnáváním chceme zkontrolovat, že dané podřetězce
existují (a indexy nám z řetězce nevylézají).
Jaká je časová složitost? Testování, zda fráze délky F končí nebo začíná na aktuální pozici, provádíme v O(F). Pro každou pozici takto testujeme všechny odbočovací a vracecí fráze, takže označíme-li jako Z celkovou délku všech odbočovacích a vracecích frází na vstupu, strávíme na každém znaku O(Z) času, a celková časová složitost je tedy O(NZ).
To sice není optimální, ale v našich vstupech jsou odbočovací i vracecí fráze krátké a je jich málo, a proto toto řešení stačilo na plný počet bodů.
Aho-Corasicková a spol.
Plný počet bodů nás ale nemůže zastavit! Pokud víte o existenci algoritmů na hledání v textu, jako například KMP, algoritmus Aho-Corasickové, nebo Rabinův-Karpův algoritmus (mimochodem, můžete se o nich dočíst víc v naší kuchařce), pak si možná říkáte, že by s jejich pomocí šlo náš algoritmus zrychlit. A vskutku!
Nám se konkrétně bude hodit algoritmus Aho-Corasickové. Nebudeme zabíhat do jeho popisu, ale důležité je, co dělá: na vstupu dostane dlouhý text a několik výrazů, které v něm chceme najít, a na výstupu nám pro každý výraz dá seznam všech pozic v textu, kde se vyskytuje. Jeho časová složitost je O(N + Z + V), kde N je délka textu, Z součet délek hledaných výrazů a V celkový počet nalezených výskytů. V našem případě je nejvýše jeden výskyt na každé pozici, tudíž naše časová složitost je O(N + Z).
Pořídíme si pole stejné délky jako vstupní text, na počátku plné nul, kde si na každý index chceme poznamenat, zda tam začíná (+1) nebo končí (-1) nějaká odbočka (nebo ani jedno). Za tím účelem pustíme Aho-Corasickovou na náš vstupní text a odbočovací a vracecí fráze a pak pro každý výskyt na příslušnou pozici v poli buď přičteme, nebo odečteme jedničku. (Nesmíme zapomenout, že u vracecích frází nás zajímá index, kde fráze končí, nikoliv začíná.) Zbytek algoritmu pak bude v podstatě totožný jako na začátku.
Jak už jsme slíbili, časová složitost Aho-Corasickové bude O(N + Z), což je zároveň i časová složitost celého algoritmu.
Poznámka na závěr: Python (a plno dalších programovacích jazyků) ve standardní
knihovně nemá funkci pro Aho-Corasickovou (str.find je sice také
lineární, ale umí hledat jen jeden výraz najednou). Pokud si ji nechceme sami implementovat a nechceme/nemůžeme použít nějakou knihovnu, můžeme si pomoct malým trikem
a použít regulární výrazy. Ty jsou ještě mnohem silnější než
Aho-Corasicková (umožňují například věci jako „najdi výraz, co začíná na
Uáá, pak obsahuje libovolné množství á a končí na alespoň jeden
vykřičník“) a dalece přesahují rámec tohoto řešení. Důležité je, že
v regulárních výrazech umíme zapsat výraz „najdi podřetězec, který se rovná
řetězci R1, nebo řetězci R2, nebo…“, a že ačkoliv toho obecně neumíme
tolik říct o jejich časové složitosti (záleží na konkrétní implementaci
regexového enginu), v praxi – a speciálně v této úloze – nám můžou stačit.
Pro implementační detaily se můžete podívat do vzorového řešení.
35-Z5-2 Zlaté stránky (Zadání)
Nový název budeme vymýšlet od prvního písmenka – to ovlivní abecední pořadí
nejvíce. Vlastně na něm záleží „nekonečněkrát“ více než na druhém (azzz
je abecedně před baaa) a to platí pro každá dvě po sobě jdoucí písmenka.
Z toho vyplývá, že chceme při každém kroku sestavování názvu vybrat to aktuálně
nejvhodnější písmenko, jelikož má „nekonečněkrát“ větší vliv než písmenka na
všech následujících pozicích.
Takovému algoritmu se říká hladový, protože v každém kroku „chamtivě zhltne“ (rozuměj použije) lokálně nejlepší řešení. (Více o nich v naší kuchařce.) A jak jsme se dozvěděli ve čtvrté úloze této série, tak hladové algoritmy skoro nikdy nefungují, proto musíme na závěr pečlivě ověřit, že nás zhltnutí lokálně nejlepší možnosti nepřipraví o celkově nejlepší řešení.
Jak tedy bude vypadat celkový algoritmus? Dokud to je možné, bereme písmenka shodující se s oficiálním názvem Hipporty (dále jen H). Jakmile dojdou, vezmeme abecedně nejbližší dostupné písmenko. Taková můžou být jedno nebo dvě: jedno abecedně dřívější a jedno pozdější, a my si díky zadání můžeme vybrat libovolné z nich. BÚNO (bez újmy na obecnosti) řekněme, že jsme si vybrali to dřívější; kdyby náhodou nebylo k dispozici a my museli vybrat nejbližší pozdější, bude algoritmus stejný, jen bychom všude prohodili slova „menší“ a „větší“.
Když teď pokračujeme a vybíráme další písmena, chceme vždy abecedně co největší, protože ať budeme dělat, co chceme, vždy už budeme abecedně před H. Touto metodou už můžeme sestavit zbytek názvu.
Zbývá rozmyslet si správnost. Jak by musel vypadat řetězec, který se abecedně vejde mezi náš výstup a H? Určitě se s H nemůže shodovat ve více počátečních písmenkách než my (víme, že by nějakého písmenka musel použít víc než je k dispozici), což znamená, že se od našeho výstupu poprvé liší až někde v druhé části, a to použitím abecedně většího písmenka. Jenže my jsme v každém okamžiku brali největší přípustné písmenko, tudíž i to je nemožné, a takový řetězec tedy nemůže existovat, čímž je důkaz správnosti hotov.
Časová složitost je lineární s délkou názvu společnosti a velikostí abecedy, tedy O(|Σ|·|H|) = O(26 ·|H|) = O(|H|). S opatrnější implementací jde dosáhnout složitosti O(|Σ| + |H|), ale v této úloze to nebylo potřeba.
Co kdyby nám zadání nedalo na výběr mezi nejbližším předcházejícím a
následujícím názvem, ale museli jsme vždy najít ten předcházející? Pak může
naše řešení selhat na okrajovém případu: v okamžiku, kdy se přestaneme shodovat
s H a chceme použít abecedně nejbližší dřívější písmenko, se může stát, že
takové písmenko neexistuje, protože už nám všechna abecedně menší písmenka
došla. Pak se budeme muset vrátit o pár písmenek zpátky (a pokaždé kontrolovat,
zda k aktuálnímu znaku už abecedně nižší písmenko máme), a výsledný řetězec se
pak nebude nutně shodovat s H na co nejvíce písmenkách. Jako příklad můžete
uvážit H = caaa s dostupnými písmenky a, a, b, c, z, z, z.
Algoritmus se zastaví s částečným řetězcem caa, ale výsledný řetězec bude
bzzz. Takže jak vidno, stačí mít jen o trochu těžší úlohu a hladový
algoritmus zase nefunguje. Můžete si rozmyslet, že naznačený „polohladový“
algoritmus již správný je; níže si můžete přečíst jeho implementaci.
35-Z5-3 Karneval (Zadání)
Uvažujme na chvíli, že je karneval již nějak roztahaný po městě, ale dál se nepohybuje. V tom případě můžeme použít prohledávání do šířky, jak lze najít např. v naší kuchařce. Tím dokonce najdeme cestu nejkratší.
Jenže co když se průvod pohybuje? Pak máme obecně problém – v úlohách na hledání cest, kde se průběžně mění prostředí, nemusí platit předpoklady nutné pro BFS. Např. se může vyplatit chvíli počkat (třeba než projede vlak), abychom následně šli přímo, než dočasnou překážku začít dlouze obcházet. Tím přestává platit, že čím dříve na nějaké políčko dojdeme, tím určitě lépe. Je to ale případ karnevalu? Není! Průvod má naštěstí jednu důležitou vlastnost – jakmile na políčko jednou vstoupí, již nikdy neodejde. Pokud tedy odněkud vede cesta do cíle v čase t, jistě byla k dispozici v časech <t (a možná byly i nějaké kratší cesty).
Po této rozvaze tedy můžeme s klidem použít téměř standardní prohledávání do šířky. Akorát ve frontě si musíme u políček pamatovat i to, jakého časového okamžiku se týkají. Až začneme zpracovávat políčko s vyšším časem, než mělo předchozí, posuneme karneval o jeden krok podle pravidel. Na políčka s karnevalem nesmíme vstoupit, tudíž je do fronty nevkládáme. Tuto podmínku však musíme ověřit i ve chvíli, kdy se políčko z fronty rozhodneme zpracovat, karneval na něj totiž mohl právě vstoupit. Jinak je průběh algoritmu standardní.
35-Z5-4 Protipříklad (Zadání)
V úloze 35-Z5-2 hladový algoritmus fungoval, ale na tuto úlohu opravdu nezabere. Jak sestrojit protipříklad?
Pokusíme se nastražit na hladový algoritmus past. Najdeme dvojici řetězců, které mají velký překryv, ale jejich slepení zablokuje jiná dvě slepení. Zablokovaná slepení musí každé mít menší překryv, ale v součtu větší, než to vybrané.
Zvolíme tyto řetězce:
| A | = abcdef |
| B | = cdefgh |
| C | = efghbcd |
| Z | = bcdefz |
Velikosti překryvů vyjdou následovně:
| A | B | C | Z | |
| A | - | 4 | 2 | 5 |
| B | 0 | - | 4 | 0 |
| C | 0 | 2 | - | 3 |
| Z | 0 | 0 | 0 | - |
Hladový algoritmus tedy slepí A+Z na D = abcdefz.
Z toho vyjde další tabulka překryvů:
| B | C | D | |
| B | - | 4 | 0 |
| C | 2 | - | 0 |
| D | 0 | 0 | - |
Teď lepíme B+C na E = cdefghbcd a dostaneme:
| D | E | |
| D | - | 0 |
| E | 0 | - |
Teď máme na výběr buď D+E = abcdefzcdefghbcd nebo
E+D = cdefghbcdabcdefz, obojí o 16 znacích.
Pokud bychom ovšem neskočili na špek, mohli bychom slepit
A+B = abcdefgh a
C+Z = efghbcdefz (překryv celkem o 7).
Finálním slepením získáme nadřetězec
abcdefghbcdefz,
který má jenom 14 znaků.
Hladový algoritmus jsme tedy usvědčili z neoptimálnosti.