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

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

Řešení úloh

• 17-2-1: Prasátko Květ(ák)omil
• 17-2-2: Bobr Béďa
• 17-2-3: Krkavec Kryšpín
• 17-2-4: Mravenec Ferda
• 17-2-5: Jazykozpytcova pomsta

17-2-1 Prasátko Květ(ák)omil (Zadání)

Jak si mnozí řešitelé správně povšimli, tato úložka byla zaměřena převážně na procvičení hešování – to se nám bude hodit dokonce dvakrát.

Nejprve si povšimněme, že se po nás chce pouze spočítat počet výrazů v programu, jejichž hodnota je různá – výrazy se stejnou hodnotou bychom nevyhodnocovali dvakrát, ale poprvé uložili do pomocné proměnné a podruhé použili tuto uloženou hodnotu. Upřesněme si ještě, co to znamená „mít stejnou hodnotu“. Představme si, že bychom za proměnné ve výrazech postupně dosazovali jejich definice tak dlouho, dokud by alespoň jedna proměnná neměla svou počáteční hodnotu. Pak dva výrazy E₁ a E₂ jsou si rovny, pokud

• E₁=E₂=v, kde v je nějaká proměnná, nebo
• E₁=E₁' op E₁'', E₂=E₂' op E₂'', kde op je buď + nebo * a buď
  • E₁' je rovno E₂' a E₁'' je rovno E₂'', nebo
  • E₁' je rovno E₂'' a E₁'' je rovno E₂'.

Samozřejmě ověřovat rovnost přímo podle této definice je nevhodné (už proto, že takto rozexpandované výrazy mohou mít i exponenciální velikost). Místo toho každému výrazu přiřadíme číslo, které bude reprezentovat jeho hodnotu – tj. dva výrazy dostanou stejné číslo právě tehdy, pokud jsou si rovny, jinak dostanou různá čísla.

První hešovací tabulka A bude jménu proměnné přiřazovat číslo hodnoty, která je aktuálně v této proměnné uložena. Ve druhé hešovací tabulce B si pak budeme pamatovat čísla hodnot výrazů, které se v programu vyskytují – klíčem této tabulky budou trojice (operátor, číslo hodnoty levého operandu, číslo hodnoty pravého operandu), a jim bude přiřazeno číslo hodnoty tohoto výrazu. Na konci stačí vypsat počet různých čísel hodnot v tabulce B, protože to bude právě počet různých hodnot výrazů v programu.

Čísla hodnot výrazů určujeme takto:

• Když zpracováváme nějakou proměnnou poprvé, přiřadíme jí nové číslo hodnoty.
• Když zpracováváme přiřazení var₁ = var₂, pak proměnné var₁ přiřadíme stejné číslo hodnoty, jaké má proměnná var₂.
• Když zpracováváme přiřazení var₁ = var₂ op var₃, pak si nejprve zjistíme čísla hodnot v proměnných var₂ a var₃ – nechť to jsou n₂ a n₃. Pak se podíváme do hešovací tabulky B, zda v ní je uložen výraz (op, n₂, n₃). Je-li tomu tak, pak jeho číslo hodnoty přiřadíme proměnné var₁. Jinak tento výraz přidáme do tabulky B s novým číslem hodnoty, a toto číslo přiřadíme proměnné var₁.

Zbývá si rozmyslet, jak ošetřit komutativitu operací. To je ale snadné – před prací s tabulkou B stačí čísla hodnot v trojici seřadit tak, aby druhé z nich bylo menší nebo rovno třetímu.

Časová složitost na operaci s tabulkou A je v průměrném případě O(k), kde k je délka názvu proměnné. Protože pro každý výskyt proměnné v programu provedeme právě jednu operaci s touto tabulkou, dohromady bude časová složitost pro práci s ní O(n), kde n je délka vstupu. Časová složitost pro práci s tabulkou B je O(1) na operaci, a počet operací s ní je roven počtu přiřazení ve vstupu, tj. celková časová složitost je O(n) – toto je složitost v průměrném případě, v nejhorším případě, kdy by docházelo ke všem možným kolizím, by časová složitost byla O(n²). Paměťová složitost je zřejmě O(n).

Poznámka na závěr – zde popsaná metoda identifikace redundantních výpočtů se s mírnými vylepšeními skutečně používá v kompilátorech. Anglický název je Value Numbering.

Program

Zdeněk Dvořák

17-2-2 Bobr Béďa (Zadání)

Všichni správně uhodli, že jde o hledaní minimální kostry grafu a že předem dané hrany tvořící cykly nijak nevadí. Mnoho z vás ale pak zvolilo buď zbytečně pomalý algoritmus (no comment :–)) nebo použili více či méně rychlou implementaci DFU. Ta sice běží v čase O(N·α(N)), ale pro tuto úlohu je zbytečně složitá.

Naše řešení bude založeno na Jarníkově algoritmu pro hledání kostry. Budeme postupně budovat kostru tak, že začneme s jedním libovolným vrcholem a vybereme si jeho souseda takového, že ještě v kostře není, a přitom je k současné kostře nejblíže. Takto pokračujeme, dokud nepřidáme vrcholy všechny.

Popsaný algoritmus naimplementujeme pomocí haldy tak, že na začátku začneme s libovolným vrcholem a do haldy přidáme všechny hrany, které z tohoto vrcholu vedou. V každém kroku pak z haldy vezmeme hranu s nejmenším ohodnocením a podíváme se, jestli nějaký její konec ještě není v kostře. Pokud ne, přidáme ho do ní (je momentálně nejblíž vytvářené kostře) a do haldy vložíme všechny hrany z tohoto vrcholu vedoucí. Pokud už oba konce hrany v kostře jsou, neděláme nic. Tento celý postup se opakuje, dokud je v haldě nějaká hrana.

Jaká bude časová složitost? Každou hranu přidáme do haldy maximálně dvakrát a na každý vrchol sáhneme nanejvýš čtyřikrát (tolik z něj vede hran). Pokud by naše operace s haldou byly v konstantním čase, bude celková časová složitost O(N·M).

V haldě budeme mít naštěstí jenom hrany s ohodnocením 0 (dopředu vyryté kanálky), 1 (svislé kanálky) a 2 (vodorovné kanálky). Můžeme si tedy pamatovat hrany ve třech polích podle jejich ohodnocení a pokud hledáme hranu s nejmenším ohodnocením, zkusíme pole s ohodnocením 0, a pokud je prázdné, tak 1 nebo 2. Každopádně všechny tyto operace (přidat hranu a odebrat hranu s nejmenším ohodnocením) zvládneme v konstantním čase.

Můj program bude mít v poli h[i] vrcholy, ke kterým vede z už propojené části hrana s ohodnocením i. Vrchol v nich může tak být až 4× (přidán z různých stran), ale to mi nijak nevadí. Do polí fv a fs si na začátku načtu již hotové hrany.

Program

Tomáš Gavenčiak

17-2-3 Krkavec Kryšpín (Zadání)

Těžiště trojúhelníku je zároveň středem kružnice opsané, je to bod, který je od všech vrcholů stejně vzdálen. Souřadnice těžište trojúhelníku lze tedy můžeme spočítat podle vzorce x = (x₁ + x₂ + x₃) / 3 a y = (y₁ + y₂ + y₃) / 3.

Další vzorec, který budeme potřebovat, je z fyziky: těžiště soustavy hmotných bodů lze spočítat jako vážený průměr souřadnic těch bodů. Tedy

kde x_i, y_i jsou souřadnice bodů a m_i je jeho hmotnost. Pro naše účely na jednotce hmotnosti nezáleží. Vzorec bude fungovat i pro záporné „hmotnosti“, což se nám bude hodit pro nekonvexní útvary.

Ještě potřebujeme znát plochu jednoho trojúhelníku, tu lze získat jednoduše jako S = 1/2 ·|AB ×AC | neboli S = 1/2 ·|(B_x-A_x) ·(C_y-A_y) - (C_x-A_x) ·(B_y-A_y) |.

Pro konvexní útvary by stačilo rozdělit mnohoúhelník na trojúhelníky A₁, A_i, A_i+1, a těžiště získat pomocí tří vzorců nahoře.

Pokud při výpočtu plochy použijeme vzorec S = 1/2 ·((B_x-A_x) ·(C_y-A_y) - (C_x-A_x) ·(B_y-A_y) ) (tedy bez absolutní hodnoty), budeme dostávat kladné a zaporné vysledky podle toho, jestli trojúhelník ABC je orientován po nebo proti směru hodinových ručiček. Toho lze obratně využít: vybereme libovolný bod O (třeba počátek systému souřadnic) a použijeme vzorce nahoře pro trojúhelníky O, A_i, A_i+1. Kazdý bod, který je uvnitř mnohoúhelníku bude součástí lichého počtu dílčích trojúhelníků, a díky tomu se bude počítat do celkového výsledku. Body, které jsou mimo mnohoúhelnik, budou součástí sudého počtu trojúhelníků, a díky opačným orientacím se navzájem odečtou a celkový výsledek neovlivní.

Časová složitost je lineární vzhledem k počtu vrcholů, a lépe to nejde, protože výsledek záleží na všech bodech. Paměťová slozitost je konstantní, body jsou zpracovávány hned, jak přichází ze vstupu.

S díky Janu Pelcovi.

Program

Pavel Machek

17-2-4 Mravenec Ferda (Zadání)

Ferda se dlouho probíral vašimi programy, ale naštěstí pro něj a naneštěstí pro Ptáčka Sáčka nalezl mezi řešeními kýžený algoritmus.

Hlavní myšlenkou algoritmu je zpracovávat úlohu postupně. Bude nás zajímat součet horních čísel na kostkách. Pokud otočíme kostku, změní se horní číslo na kostce, a tedy i součet horních čísel. Naším cílem je najít takové otočení kostek, aby součet horních čísel byl co nejbližší součtu dolních čísel. Víme, že součet čísel je menší než K·N. Zajímáme se tedy, pro které součty čísel s existuje otočení kostek, jehož součet horních čísel na kostkách je právě s. Dalším parametrem součtu čísel s je minimální počet otočených kostek O[s], který je potřeba, aby jsme dosáhli součtu s. Pole O budeme budovat postupně. Označme O_i pole O vytvořené z i prvních kostek. Zřejmě O₀[0]=0 a pro ostatní součty s má hodnotu Null, která znamená, že tohoto součtu nelze dosáhnout. Jakmile máme vytvořené pole O_i, pak pole O_i+1 naplníme následovně: Označme čísla na i+1-ní kostce h a d. Projdeme všechny možné součty s od 0 do K·N. Pokud O_i[s] není Null, zkusíme k součtu přidat kostku. Pokud je O_i[s] < O_i+1[s+h], nastavíme O_i+1[s+h]:=O_i[s] a podobně pokud O_i[s]+1 < O_i+1[s+d], nastavíme O_i+1[s+d]:=O_i[s]+1. Samozřejmě v případě hodnoty Null uložíme novou hodnotu. Tímto způsobem sice ztratíme některé možnosti otočení kostek, ale určitě si uchováme ty součty, které potřebují nejmenší otočení kostek. Jakmile naplníme pole O_n, jsme hotovi. Stačí už jen vybrat nejbližší součet a najít kostky, které musíme otočit. Otočení jednotlivých kostek si uložíme už při vytváření pole O – do pole T_i[s] si poznamenáme, zda jsme při vytváření součtu s z prvních i kostek otočili i-tou kostku. Pak už stačí jen vystopovat všechny otočené kostky z finálního součtu prostým odečítáním horních či dolních čísel kostek.

Algoritmus používá k uložení součtů N polí o velikosti K·N, takže jeho paměťová složitost je O(N²·K). Časově nejnáročnější operací je právě naplnění těchto polí, tedy časová složitost je také O(N²·K). V algoritmu jsme použili myšlenku spočítat si řešení pro část vstupu, uložit si ho a pak ho znovu použít pro další výpočet. Tomuto způsobu řešení úloh se říká dynamické programování.

Program

Petr Škoda

17-2-5 Jazykozpytcova pomsta (Zadání)

Správných řešení první úlohy, ke kterým jsem neměl žádnou připomínku, tentokrát došlo poskrovnu. Nejběžnější chyba byla následující: V podstatě všichni řešitelé přišli na správnou myšlenku, že automat nutně nějak musí umět rozlišovat hloubku vnoření závorek. Bohužel už málokdo to uměl i správně dokázat. To přeci vůbec není na první pohled zřejmé! Stejně tak bychom mohli tvrdit, že když rozpoznáváme jazyk {aⁱ;  i∈N}, tak je nutné si počítat ono i, ve skutečnosti to samozřejmě potřeba není. Proč by třebas nemohl existovat automat, který používá nějakou úplně jinou metodu? Řešitelům jsem uděloval body podle toho, nakolik myšlenku důkazu dotáhli do konce.

Ale teď už si předveďme jeden z možných správných důkazů. Jeho myšlenka je jednoduchá: automat se nemůže obejít bez rozlišování úrovně vnoření závorek. Jak to ovšem ukázat formálně?

Budeme postupovat sporem, nechť existuje konečný automat M=(Q,A,q₀,δ,F), který má k stavů a rozpoznává jazyk U správně uzávorkovaných výrazů. Vezmeme vhodné správně uzávorkované slovo a ukážeme, že z něj lze vynechat úsek tak, že slovo přestane být dobře uzávorkované, ale automat to vůbec nepozná a prohlásí ho za správné. Tím ukážeme, že žádný konečný automat M, který by měl umět rozpoznávat U, ve skutečnosti nikdy nemůže dobře pracovat.

Když má tedy automat k stavů, uvažme slovo (^k+1)^k+1. Při načítání levých závorek automat nějak mění stavy, ale protože levých závorek je k+1, alespoň jedním stavem se musí projít dvakrát. Existují tedy dva indexy i a j, i<j, že po přečtení j-té levé závorky se automat ocitl ve stejném stavu q jako po přečtení i-té levé závorky. Jinými slovy, automat ve své „paměti“ považuje pozice i a j za nerozlišitelné. V obou případech se totiž stroj nachází ve stavu q, a následný výpočet tudíž musí mít úplně stejný průběh. A co se tedy stane, když automatu podstrčíme slovo, kde vynecháme levé závorky na pozicích i+1 až j? Automat to vůbec nepozná a prohlásí, že slovo je správné!

Dokonce bychom mohli tento úsek ne vynechat, nýbrž zdvojit, ztrojit, zkrátka libovolně mnohokrát znásobit. Když se nad tím zamyslíme hlouběji, podobnou vlastnost musí mít všechny nekonečné regulární jazyky. Stačí vzít dostatečné dlouhé slovo, a pak už se v něm nutně musí vyskytovat úsek, který lze beztrestně odmazat či libovolněkrát „nafouknout“. Tato skutečnost se dá v literatuře najít pod názvem Pumping lemma.

Z přijímacích stavů M₁ se však ještě výpočet může vrátit zpět do vnitřních stavů M₁, a tyto zpětné šipky nemůžeme vynechat. Po napojení stroje M₂ tudíž v propojovacích stavech vznikne více šipek pro jediné písmenko. To je ale přesně nedeterministický konečný automat. Jenže definice regulárního jazyka je taková, že pro něj musí existovat deterministický konečný automat. Tehdy však stačí použít větu dokázanou v zadání, podle které umíme k nedeterministickému automatu M sestrojit ekvivalentní deterministický automat.

Následujícím poněkud odpudivým formálním zápisem ještě výsledný nedeterministický stroj

Na tento výsledný NKA M nyní aplikujeme větu o převodu na DKA a důkaz je hotov.

Ještě bychom měli věnovat pár slov několika málo řešitelům, který svůj důkaz založili na zřetězení gramatik speciálního tvaru X→aY, X→a pro a terminální a X,Y neterminální, jež ke každému regulárnímu jazyku existují. Myšlenka je to samozřejmě dobrá, ale trpí stejnými neduhy při spojování jako automaty. Je opět třeba zajistit, aby se expanze gramatiky z pravidel pro L₂ nevrátila zpět do pravidel pro L₁. Navíc my jsme si ekvivalenci automatu a gramatik výše uvedeného tvaru celou nedokazovali. Druhý směr, tedy konstrukci deterministického automatu z gramatiky, jsme schválně ve vzorovém řešení první série odbyli, neboť ony „detaily, které si každý rozmyslí sám“ znamenají právě konstrukci nedeterministického konečného automatu a jeho následný převod na deterministický například pomocí věty o ekvivalenci DKA a NKA.

Tomáš Valla