Čtvrtá série jedenáctého ročníku KSP
Řešení úloh
11-4-1 Výlet po řece (Zadání)
V této úloze se mělo zjistit, zda ve vrcholově ohodnoceném stromu existuje prostá cesta (tj. cesta, ve které jdeme každým vrcholem právě jednou), jejíž součet hodnot vrcholů dává zadané číslo N. Bylo dobré si uvědomit dva fakty. Mezi každými dvěma vrcholy existuje právě jedna prostá cesta – to plyne z toho, že graf je strom. To, že se jedná o binární strom (na soutoku se stékají vždy jen dvě řeky), není až zas tak důležité a nemění to podstatně charakter úlohy. Daleko důležitější je první fakt, který znamená, že stačí zkontrolovat pouze počet cest kvadraticky úměrný počtu vrcholů, tj. pro každou dvojici vrcholů cestu mezi nimi.
Algoritmus bude tedy vypadat následovně: Pro každý vrchol grafu vi budeme graf procházet do hloubky. Přitom si budeme počítat vzdálenost vrcholu, ve kterém právě stojíme, od vrcholu vi. To budeme provádět tak, že při průchodu vrcholem směrem dolů přičteme jeho hodnotu a při návratu ji zase odečteme. Takto budeme znát délku cesty z vrcholu vi do všech vrcholů, kterými jsme prošli při procházení do hloubky – tedy do všech vrcholů. Po provedení tohoto pro všechny vrcholy vi jsme zkontrolovali ceny cest mezi všemi dvojicemi vrcholů. Pokud se při procházení v nějakém vrcholu rovná cena cesty ceně hledané, algoritmus nalezl řešení a skončí. V opačném případě po zkontrolování všech cest víme, že cesta požadované ceny neexistuje.
„Časová složitost bude někde mezi lineární a exponenciální,“ jak vtipně uvedl jeden řešitel ve svém řešení. Přesněji kvadratická vzhledem k počtu vrcholů, tj. O(n2). To je proto, že časová složitost procházení je lineární a to provedeme právě n-krát. Lépe to ani nejde, protože musíme vyšetřit počet cest kvadraticky úměrný počtu vrcholů. Paměťová složitost roste lineárně s počtem vrcholů, tj. O(n). To je způsobeno prohledáváním do hloubky a pamětí potřebnou na reprezentaci grafu.
K programu bych dodal jen formát vstupních dat. Nejprve je načten počet vrcholů a požadovaná cena cesty. Pak pro každý vrchol načteme čtyři čísla – cenu hotelu a tři sousedy v grafu udané pořadovými čísly, pokud je jich méně (například list má pouze jednoho souseda) mají zbývající hodnotu -1.
[Úloha na prázdniny: Tento problém je řešitelný dokonce v čase O(n log n), zkuste přijít na to, jak. Pro vyvážené stromy to je jednoduché, pro nevyvážené poněkud obtížnější, ale přeci jen zvládnutelné. –M.M.]
11-4-2 Komplot (Zadání)
Všechna došlá řešení byla více méně správně a je možné je rozdělit do dvou skupin: První skupina počítala obsah tak, že z mnohoúhelníka postupně „ořezávala“ trojúhelníky. Přístup je to sice funkční, leč pomalý (obvykle O(N2) až O(N3)). Druhá skupina počítala obsah jako součet obsahů lichoběžníků nebo trojúhelníků. Do této kategorie spadají i ti řešitelé, kteří se odkázali do literatury. Proti odkazům do literatury v zásadě nic nenamítám, ale přeci jen celou úlohu zamést tím, že je to vyřešeno v té a té knize se mi nezdá ideální. Vzhledem k tomu, že většina těchto řešitelů neuvedla ani náznak důkazu správnosti, přišli tím o bod (tento byl totiž připsán zpravidla panu H. J. Bartschovi). Jinak i ostatní řešitelé často na důkaz správnosti zapomněli…
Teď už k samotnému řešení. Uvažme mnohoúhelník „rozřezaný“ přímkami vedenými každým z bodů kolmo k ose x. Každá část musí být protnuta sudým počtem hran (jistě když projdeme hranou na jednu stranu, tak se opět někdy musíme vrátit zpět). V mnohoúhelníku pak je vždy část mezi první a druhou hranou, mezi třetí a čtvrtou hranou atd. Pokud by to tak nebylo, nějaká hrana by neohraničovala mnohoúhelník ale vedla by uvnitř něj či vně. Abychom tedy zjistili příspěvek dané části k obsahu, stačí tedy přičíst plochy pod lichými hranami a odečíst plochy pod sudými hranami (pokud by některým matematičtěji založeným jedincům vadilo, že plochy pod některými hranami mohou být nekonečné, mohou si představovat, že přičítáme pouze plochu k nejspodněji položenému průsečíku). Ještě se nám bude hodit, když si uvědomíme, že liché hrany vždy vedou zleva doprava (pro zadání proti směru hod. ručiček) a sudé opačně. To snadno dokážeme sporem. Nechť jsou pod sebou dvě hrany vedoucí stejným směrem. Bez újmy na obecnosti zleva doprava. Od pravého konce horní hrany musí nějak vést lomená čára k levému konci dolní hrany. Od pravého konce spodní hrany pak musí nějak vést lomená čára k levému konci horní hrany. To ovšem nelze bez protnutí první čáry, nebo bez průchodu mezi horní a spodní hranou. Spor.
Když si teď představíme zase celý mnohoúhelník, můžeme si všimnout, že se vždy plocha pod jednou hranou celá buď přičítala, nebo odečítala. To totiž plyne z toho, že hrany se nikde nemohou protínat a tedy parita počtu hran nad danou hranou je vždy stejná (pokud náhodou nad naší hranou nějaká hrana přibyla, tak jich musel určitě přibýt sudý počet – jedna hrana doleva a jedna doprava).
K dalšímu zjednodušení algoritmu přispěje poznání, že nemusíme počítat obsahy pod hranami, ale stačí počítat obsahy lichoběžníků určených koncovými body hran a libovolnou pevně zvolenou přímkou (třeba osou x). Čtenář si jistě sám rozmyslí, že i v případech, kdy přímka protíná hranu, či kdy je hrana pod přímkou, přičteme nakonec správný obsah. Navíc pokud k výpočtu obsahu mechanicky používáme vzorec (ax-bx)*(ay+by)/2, kde A a B jsou konce hrany, bude automaticky zajištěno přičtení obsahu u hran jdoucích jedním směrem a odečtení obsahu u hran jdoucích druhým směrem.
Algoritmus má lineární časovou a konstantní paměťovou složitost. Správnost algoritmu byla ukázána výše.
Program je přímou implementací algoritmu, jen dělení dvojkou je vytknuto před všechny výpočty, takže až do konce můžeme počítat v celých číslech. (Z toho mimo jiné plyne velice zajímavý fakt, a to že obsah každého mnohoúhelníka s celočíselnými souřadnicemi vrcholů je celý počet „půlčtverečků“, což dokonce platí i pro oblasti s dírami, ale to je potřeba dokazovat trošku složitěji.)
11-4-3 V jámě (Zadání)
Triviální řešení této úlohy je všechny vzdálenosti setřídit a poté je jednu po druhém projít a zjistit tak, mezi kterými dvěma sousedními prvky je největší mezera. Ale to nám dává algoritmus se složitostí O(n· log n). Pravda, mohli bychom použít příhrádkového třídění, ale to by selhalo, pokud by souřadnice nebyla malá celá čísla. Další možnost je rozkouskovat si ulici na jednotlivé centimetry a u každého si poznačit, zda tam je či není díra, ale to by paměťová i časová náročnost rostly s délkou ulice. Takže je potřeba jít na to jinak…
Nejdříve budeme předpokládat, že díry jsou rozloženy přibližně pravidelně a rozdělíme si ulici (přesněji řečeno část ulice mezi první a poslední dírou) na n-1 stejných úseků a pro každý úsek si budeme pamatovat souřadnici první a poslední díry v daném úseku. Potom probereme všechny díry a určíme, do kterého úseku přísluší a upravíme zapamatované hodnoty pro tento úsek. Pak už stačí jen najít takové dva sousední úseky, u kterých je rozdíl souřadnice poslední díry prvního úseku a první díry druhého maximální, a to je řešení naší úlohy.
Proč však nemůže být hledané řešení někde uvnitř úseku? Délka všech úseků dohromady je xr-xl (xr je souřadnice poslední díry, xl první), délka jednoho úseku tedy (xr-xl)/(n-1). Pokud by hledané řešení leželo uvnitř nějakého úseky, pak by maximální vzdálenost dvou děr byla menší než délka úseku, a proto vzdálenost od první díry k poslední (tedy součet vzdáleností mezi sousedními dírami, xr-xl) menší než součet délek všech úseků, což je spor.
Odhad časové a paměťové složitosti: nalezení minima a maxima provedeme snadno v čase O(n), přiřazení jedné jámy do příslušného úseku v O(1), pro všechny jámy tedy dohromady O(n). Závěrečné nalezení nejdelší mezery mezi krajními jámami úseků rovněž O(n). Celkem tedy O(n). Paměťová složitost je také O(n), protože si stačí pamatovat pouze informace o úsecích.
11-4-4 Turingovy stroje (Zadání)
Analýza všech možných i nemožných Pascalských konstrukcí v úloze 11-3-4 vás jistě znechutila natolik, že nebyvše lačni po zatracení na věky věkův, netroufáme si cokoliv podobného zopakovat. Využijeme proto toho, že již víme, že Pascal se dá překládat do Mikroassembleru a dokážeme proto pouze, že se pro libovolný mikroassemblerský program M dá nalézt příslušný Turingův stroj T.
Hledaný Turingův stroj bude pracovat s tříprvkovou abecedou Σ={°, ♥, Λ} a obsah jeho pásky bude representovat paměťové buňky μ1 uložené v „jedničkové soustavě“, a k tomu ještě prokládaně (možno samozřejmě i jinak, ale tento postup vede k nejjednodušší realizaci instrukcí μ1 na TS). Konkrétněji: Program M má konečnou délku, takže využívá konečný počet registrů, a proto existuje n takové, že registry mimo 0,… ,n-1 využity nejsou. Nyní j-tý registr μ1 uložíme na políčka pásky TS s indexy ni+j, kde i prochází všemi přirozenými čísly (to znamená na j-té políčko a pak vždy n-1 políček přeskočíme, protože v nich budou uloženy hodnoty ostatních registrů). Je-li v registru j hodnota r, je prvních r políček příslušících tomuto registru zaplněno znaky ♥ a ostatní znaky Λ. Navíc si na samý začátek pásky umístíme symbol °.
Instrukce programu M nebudeme ukládat na pásku, nýbrž je rovnou representovat stavy řídící jednotky stroje T. i-té instrukci programu M bude odpovídat nějaká množina stavů Sij, přičemž provádění každé instrukce začíná stavem Si0 a po jejím provedení stroj přejde do stavu Sj0, kde j je číslo následující instrukce (j=i+1, pokud se nejednalo o skok) či do stavu Q (koncového; do něj jdeme, pokud nám program předepsal zastavení skokem před předchozí instrukci), v němž Turingův stroj zastavíme posunem přes levý okraj pásky. Navíc se domluvíme, že po vykonání každé instrukce hlavu stroje přesuneme na první „datové“ políčko pásky (to znamená nalezneme symbol ° a pak poskočíme doprava).
Nyní již k realizaci jednotlivých instrukcí:
INCk: Nalezneme začátek registru k (uděláme k kroků doprava), načež nalezneme první Λ v zápisu hodnoty tohoto registru (postupnými skoky o n políček doprava) a přepíšeme ji na ♥.DECk: Analogicky jakoINC, pouze až narazíme na Λ, vrátíme se na předchozí „číslici“ téhož registru (o n políček zpět) a přepíšeme ji na Λ (pokud tam již žádná taková nebyla, poznáme to podle toho, že potkáme symbol °, tudíž i dekrement nuly vyjde správně jako nula).CLRk: Nalezneme začátek registru k a přepisujeme všechny ♥ v jeho zápisu na Λ.JEQx,y,z: (bez újmy na obecnosti x<y) Nalezneme první políčko zápisu x a zapamatujeme si ve stavu stroje, zda to byla Λ či ♥. Poté posuneme hlavu o y-x políček doprava a porovnáme, zda zde se nacházející odpovídající číslice registru y má stejnou hodnotu. Pokud nikoliv, přejdeme na následující instrukci, ježto rx≠ ry. Jinak posunem o n+x-y políček doprava přejdeme na další číslici registru x a pokračujeme v porovnávání. Pokud jsou obě porovnávané číslice Λ, jsme již na konci obou čísel a tato jsou si rovna, tudíž zvolíme následující stav podle cíle skoku.
Tím je důkaz dokončen.