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

Vzorová řešení


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 E1 a E2 jsou si rovny, pokud

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

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í var1 = var2, pak proměnné var1 přiřadíme stejné číslo hodnoty, jaké má proměnná var2.
  • Když zpracováváme přiřazení var1 = var2 op var3, pak si nejprve zjistíme čísla hodnot v proměnných var2 a var3 – nechť to jsou n2 a n3. Pak se podíváme do hešovací tabulky B, zda v ní je uložen výraz (op, n2, n3). Je-li tomu tak, pak jeho číslo hodnoty přiřadíme proměnné var1. Jinak tento výraz přidáme do tabulky B s novým číslem hodnoty, a toto číslo přiřadíme proměnné var1.

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(n2). 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ž (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 = (x1 + x2 + x3) / 3 a y = (y1 + y2 + y3) / 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

x = (x1 m1 + x2 m2 + … + xn mn) / (m1 + m2 + … + mn)
y = (y1 m1 + y2 m2 + … + yn mn) / (m1 + m2 + … + mn)

kde xi, yi jsou souřadnice bodů a mi 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 ·|(Bx-Ax) ·(Cy-Ay) - (Cx-Ax) ·(By-Ay) |.

Pro konvexní útvary by stačilo rozdělit mnohoúhelník na trojúhelníky A1, Ai, Ai+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 ·((Bx-Ax) ·(Cy-Ay) - (Cx-Ax) ·(By-Ay) ) (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, Ai, Ai+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 Oi pole O vytvořené z i prvních kostek. Zřejmě O0[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 Oi, pak pole Oi+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 Oi[s] není Null, zkusíme k součtu přidat kostku. Pokud je Oi[s] < Oi+1[s+h], nastavíme Oi+1[s+h]:=Oi[s] a podobně pokud Oi[s]+1 < Oi+1[s+d], nastavíme Oi+1[s+d]:=Oi[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 On, 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 Ti[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(N2·K). Časově nejnáročnější operací je právě naplnění těchto polí, tedy časová složitost je také O(N2·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 {ai;  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,q0,δ,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+1j? 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.

→*←
Druhá úloha byla myšlenkově jednodušší, zato bylo potřeba být pečlivější a dát si pozor na některé zrady, které mohly nastat. V podstatě všichni, kdo úlohu odeslali, správně přišli na to, že stačí vzít automaty M1=(Q1,A1,q
0
1
1,F1) a M2=(Q2,A2,q
0
2
2,F2), které jsou dle definice regulárního jazyka schopné rozpoznávat jazyky L1 a L2, a vhodně je sériově zapojit do nového stroje M, který bude rozpoznávat jazyk L1.L2. Například můžeme na každý přijímací stav fi stroje M1 „přivěsit“ kopii stroje M2 tak, že ztotožníme stav fi s počátečním stavem stroje M2. Počátečním stavem zvolíme počáteční stav q
0
1
stroje M1 a jako koncové stavy zvolíme koncové stavy F2 strojů M2.

Z přijímacích stavů M1 se však ještě výpočet může vrátit zpět do vnitřních stavů M1, a tyto zpětné šipky nemůžeme vynechat. Po napojení stroje M2 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.

Ještě je potřeba vyřešit několik důležitých technických detailů. Pokud bychom spojení obou automatů realizovali ztotožněním přijímacího a počátečního stavu, mohlo by se ještě stát, že se výpočet, který již přešel do M2 přes propojovací stav, vrátí zpět do stroje M1, což my určitě nechceme. Napojení se tudíž musí řešit rafinovaněji: Vezmeme stroj M1 a pouze jednu kopii stroje M2. Z každého stavu stroje M1, ze kterého vede šipka pro písmeno a do některého přijímacího stavu z F1, natáhneme ještě jednu šipku pro písmeno a navíc do počátečního stavu q
0
2
stroje M2. Také je třeba ošetřit, když při práci stroje M1 přijde znak z abecedy stroje M2 a naopak. Zavedeme proto „odpadní“ stav qerr, ze kterého už nebude úniku a směřovat do něj budou šipky pro všechny špatné znaky.

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

M=(Q1∪Q2∪{qerr}, A1∪A2, P, δ, F2)
přesně definujeme. Pokud je stav q
0
1
∈F1, bude množina počátečních stavů P={q
0
1
, q
0
2
}, v opačném případě P={q
0
1
}. Přechodová funkce δ bude
δ(q,a)=
1(q,a)} pro q∈Q1, a∈A1, δ1(q,a)∉F1
1(q,a), q
0
2
}
pro q∈Q1, a∈A1, δ1(q,a)∈F1
2(q,a)} pro q∈Q2, a∈A2.
{qerr} pro q=qerr, a∈A1∪A2
{qerr} pro q∈Q1, a∈A2\A1 nebo
pro q∈Q2, a∈A1\A2

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 L2 nevrátila zpět do pravidel pro L1. 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