Matematická olympiáda – kategorie P

Řešení úloh domácího kola 64. ročníku

P-I-1 Mezery

Velmi láká zkusit úlohu řešit hladově, tedy pokusit se na každý řádek výstupu přepsat tolik slov ze vstupu, kolik je jen možné. Toto řešení ale není optimální. Například uvažme vstup, skládající se z 50 jednopísmenných slov, následovaných slovem délky 29. Prvních 50 slov i s mezerami zabere alespoň 100 znaků, slovo délky 29 se tedy nevejde na první dva řádky a bude muset být až na třetím řádku. Hladové řešení by na první řádek dalo 30 jednopísmenných slov (šířka mezer 30/29) a na druhý 20 slov (šířka mezer 40/19). Chyba těchto dvou řádků je celkem 23,245. Na druhou stranu, kdybychom místo toho dali na první i druhý řádek 25 slov (šířka mezer 35/24), chyba by byla pouze 10,083.

Jistě by bylo možné zkoušet všechny možnosti zalomení textu. Například lze použít následující rekurzivní funkcí, která vrátí nejmenší možnou chybu textu skládajícího se z prvních n slov seznamu S s tím, že prozatím poslední řádek nepovažujeme za speciální (tj. započítáváme i jeho chybu a vyžadujeme, aby na něm byla alespoň dvě slova). V kódu S(a,b) označuje podseznam S skládající se a-tého, (a+1)-ního, …, b-tého slova z S.

NejmenšíChyba(S, n)

Nakonec vyzkoušíme všechny možnosti pro poslední řádek, optimální chyba celého textu tedy bude minimum z NejmenšíChyba(S,n-p) přes všechny volby p, kde 1 ≤ p ≤ n a řádek S(n-p+1,n) i s mezerami má délku nejvýše 60.

Toto řešení samozřejmě bude velmi pomalé. Pro text skládající se například z N slov délky 1 bude hloubka rekurze v každé větvi alespoň N/30 a každé volání procedury NejmenšíChyba na úrovni rekurze menší než N/30 vede k 29 rekurzivním voláním. Časová složitost je tudíž alespoň Ω(29N/30), tedy exponenciální.

Povšimněme si ale, že proceduru NejmenšíChyba voláme mnohokrát se stejným parametrem n. Nabízí se tedy si její hodnoty ukládat a nepočítat je znovu. Modifikovaná procedura vypadá takto:

NejmenšíChyba(S,n)

(Pole předpočítáno před zahájením výpočtu zinicializujeme na samé nuly.)

Tělo této procedury se provede nanejvýš N-krát a cyklus v ní obsažený má nejvýše 29 iterací (neboť 31 i jednopísmenných slov se na řádek nevejde), celková časová složitost tedy bude lineární Ο(N), a stejná bude i paměťová složitost.

V řešení není nutné používat rekurzi. Místo toho můžeme postupně vyhodnocovat NejmenšíChyba(S, 0), NejmenšíChyba(S, 1), …, NejmenšíChyba(S, N) a tato volání pouze čtou předchozí výsledky z pole hodnota. Tuto variantu organizace výpočtu (které se také říká dynamické programování) využívá níže uvedený program. Z něj je také vidět, jak lze nejenom určit optimální hodnotu chyby, ale také vypsat příslušné zalomení textu.

Vzorový program P-I-1 (C)

P-I-2 Rušení stanic

Na vstupu jsme dostali souvislý neorientovaný graf s N vrcholy a M hranami. Nejprve si rozmysleme, že hledané pořadí vrcholů existuje pro každý možný vstup: k tomu stačí ukázat, že v každém souvislém grafu existuje vrchol, po jehož odebrání je zbylý graf stále souvislý.

Takový vrchol najdeme snadno tak, že v zadaném grafu uvážíme nejdelší možnou cestu (pokud je takových více, vybereme libovolnou) a vezmeme jeden její krajní vrchol u. Kdyby po jeho odebrání graf už nebyl souvislý, musel by existovat vrchol w, do kterého bychom se z druhého krajního vrcholu v vybrané cesty nedostali. V původním grafu bychom se do něj dostali jen přes vrchol u a složením vybrané cesty z v do u a cesty z u do w bychom dostali ještě delší cestu, což není možné, protože jsme vybrali nejdelší. Odebráním vrcholu u tedy souvislost neporušíme.

Již pomocí tohoto poznatku můžeme sestrojit algoritmus. Vyzkoušíme každý vrchol, zda jeho odstraněním neporušíme souvislost. Až najdeme vhodný vrchol, odstraníme jej a postup opakujeme. V jednom kroku tedy vyzkoušíme Ο(N) vrcholů a pro každý z nich v čase Ο(N+M) otestujeme souvislost grafu třeba pomocí prohledávání do šířky. Kroků bude celkem N, takže se dostáváme na časovou složitost Ο(N^2 · (N+M)).

K rychlejšímu řešení se dostaneme drobnou úpravou argumentu z prvního odstavce. Abychom našli vhodný vrchol k odstranění, nemusíme volit nejdelší cestu v celém grafu, stačí zvolit libovolný vrchol a z něj prohledat graf a najít od něj nejvzdálenější vrchol. Tento vrchol můžeme bez obav odstranit, protože kdyby porušil souvislost, byl by nějaký vrchol ještě dál od startovního než on, což nelze. Takovýto vrchol snadno najdeme pomocí prohledání grafu do šířky, bude to například ten, který navštívíme jako úplně poslední. Odstraňujeme N vrcholů, tento postup tedy provedeme N-krát, dostáváme tedy algoritmus běžící v čase Ο(N · (N+M)).

Optimálně rychlý algoritmus dostaneme, pokud si uvědomíme, že prohledávání do šířky provedené v předchozím řešení není třeba provádět za každý odstraňovaný vrchol, nýbrž jej stačí provést pouze jednou a zachovat si vrcholy grafu v pořadí, v jakém vstoupily do fronty. Tím máme všechny vrcholy uspořádáné podle vzdálenosti od jednoho konkrétního vrcholu a tudíž je lze díky pozorování v předešlém odstavci jednoduše vypsat od nejvzdálenějšího vrcholu. Tím jsme snížili časovou složitost na Ο(N+M).

Optimální algoritmus snadno dostaneme i pomocí prohledávání do hloubky. Stačí si uvědomit, že každý souvislý graf má kostru, ta je stromem a tudíž má list, jehož odstraněním není porušená souvislost. Stačí tedy najít nějakou kostru grafu a z té potom postupně odebírat listy. Jednu konkrétní kostru dostaneme přímo prohledáním grafu do hloubky. Výsledné pořadí vrcholů pak můžeme získat rovnou při průchodu, pokud daný vrchol vypíšeme, když se z něj rekurze vrací, neboť v tom okamžiku už všechny vrcholy ve stromě pod ním jsou vypsány a on je tím pádem listem.

Vzorový program P-I-2 (C++) [prohledávání do hloubky]

Vzorový program P-I-2 (C++) [prohledávání do šířky]

P-I-3 Ztracený paket

Omezení na paměť nám znemožňují zpracovávat naráz větší množství prvků ze vstupu, což vylučuje například možnost si pro každé číslo pamatovat, zda jsme ho již viděli. Kdyby byla čísla na vstupu setříděná dle velikosti, stačilo by je projít jednou a hledat „díru“, tj. dvě následující čísla na vstupu, která se liší o 2. Jedním přijatelným řešením (které může získat až 7 bodů) je tedy si vstupní soubor setřídit s použitím pomocných souborů nějakou metodou nevyžadující udržování tříděné posloupnosti v paměti, například Mergesortem.

Takové řešení ale vyžaduje číst a zapisovat soubory velikosti řádově n celkem Ο(log n)-krát. Existuje i jednodušší a rychlejší řešení s lineární časovou složitostí založené na vyhledávání chybějícího čísla metodou půlení intervalů, které ale stále vyžaduje použití pomocných souborů.

Mnohem efektivněji lze úlohu vyřešit s použitím jednoduchého pozorování: součet posloupnosti čísel od 1 do n v libovolném pořadí je vždy stejný (rovný N=n(n+1)/2, což ale k řešení úlohy ani nemusíme vědět, jelikož tento součet můžeme prostě určit přímo sečtením všech těchto čísel v programu). Bude-li v této posloupnost jedno číslo x chybět, bude se součet od N lišit přesně o x. Chybějící číslo můžeme určit jako (součet čísel od 1 do n) - (součet čísel ve vstupním souboru).

Při vyjadřování těchto součtů je třeba být trochu opatrný kvůli omezenému rozsahu celočíselných typů. Základní celočíselný typ je často 32-bitový, takže se do něj vejde číslo n ≤ 1 000 000 000, ale už ne nutně součet čísel od 1 do n. Toto můžeme vyřešit prováděním výpočtů v 64-bitovém typu, nebo použitím jiné vhodné operace místo sčítání (například operace xor), pro niž problém s přetečením nenastává. Případně si můžeme všimnout, že algoritmus může fungovat i v 32-bitovém typu, je-li pro něj aritmetika definována jakožto počítání se zbytky modulo 232, tedy jestliže a+b je větší nebo rovno 232, je výsledkem sčítání v příslušném typu číslo (a+b) mod 232 (takto je například definováno chování sčítání pro neznaménkové typy v programovacím jazyce C). V tom případě výsledek výpočtu bude roven ((součet čísel od 1 do n) - (součet čísel na vstupu)) mod 232 = x mod 232. To je ovšem rovno x, jelikož 0 ≤ x ≤ n < 232.

Vzorový program P-I-3 (C)

P-I-4 Magická síť

Úkol 1: Uvažme síť NAE(x,y,a), NAE(a,t,o), ONE(o), NAE(t,t,z) se vstupními proměnnými x, yz. Jestliže x = 1 nebo y = 1, pak můžeme položit a = 0, o = 1 a t = 1 - z, čímž zaručíme splnění všech omezení nezávisle na ohodnocení z. Jestliže x = y = 0, pak musíme položit a = o = 1, díky čemuž omezení NA(a,t,o)E vynucuje t = 0 a omezení NAE(t,t,z) vynucuje z = 1. Tato síť tedy přijímá právě ta ohodnocení, kde x, y nebo z mají hodnotu 1, a proto simuluje omezení OR(x,y,z).

Úkol 2: Síť NAE(a,x,x) přijímá právě ta ohodnocení, kde ax. Proto síť NAE(a,x,x), NAE(b,x,x) vynucuje a ≠ x a b ≠ x, a tedy a = b. Existuje i řešení, v němž se v rámci omezení neopakují proměnné. Síť NAE(a,x,y), NAE(a,x,z), NAE(a,y,z) vynucuje, že nejvýše jedna z proměnných x, y a z má stejnou hodnotu jako a. Síť NAE(a,x,y), NAE(a,x,z), NAE(a,y,z), NAE(b,x,y), NAE(b,x,z), NAE(b,y,z) toto zaručuje jak pro a, tak pro b, a proto není možné, aby ve splňujícím ohodnocení měly a a b různé hodnoty.

Úkol 3: Jestliže hodnoty a, bc splňují omezení NAE, tj. nejsou si všechny rovny, pak také hodnoty 1-a, 1-b a 1-c splňují omezení NAE. Uvažme libovolnou síť s proměnnými x1, …, xn, používající pouze omezení typu NAE. Jestliže ohodnocení x1=a1, …, xn=an splňuje všechna omezení této sítě, pak je zřejmě splňuje i opačné ohodnocení x1=1-a1, …, xn=1-an. Kdyby tato síť simulovala OR(x1,x2,x3), pak by existovalo ohodnocení s hodnotami x1 = x2 = x3 = 1 přijímané touto sítí. Nicméně pak i opačné ohodnocení x1 = x2 = x3 = 0 by bylo přijímané sítí, ale je odmítané omezením OR(x1,x2,x3). To je spor, tedy žádná síť obsahující pouze omezení typu NAE nemůže simulovat OR.