Pátá série čtrnáctého ročníku KSP
Řešení úloh
14-5-1 Nové slunce (Zadání)
Tato úloha patřila k těm dosti těžkým. Vaše nejlepší funkční řešení (a že jich mnoho nebylo) dosahovala složitosti O(N3). Za tato řešení bylo možno získat až 10 bodů z 12. Za řešení v čase O(N4) pak bylo možno získat až 9 bodů. Nefunkční řešení pak podle míry nefunkčnosti a kvality popisu mohla získat až 5 bodů.
A nyní již k řešení. Nejdříve si učiníme jednoduché pozorování: Na hranici nejmenší kružnice, která obsahuje všechny body, musí ležet buď dva nejvzdálenější body – označme si je A1 a A2 – a střed kružnice je ve středu úsečky A1A2 nebo alespoň tři body. Toto pozorování platí proto, že pokud na hranici kružnice neleží žádný nebo jeden bod, lze kružnici snadno zmenšit tak, že se žádný bod nedostane ven. Pokud na hranici kružnice leží dva body, lze kružnici zmenšit právě když střed kružnice neleží uprostřed spojnice těchto bodů.
Z výše uvedeného pozorování snadno odvodíme algoritmus běžící v čase O(N4) a s trochou snahy i algoritmus běžící v čase O(N3) – oba algoritmy naleznou dvojici nejvzdálenějších bodů v čase O(N2) a vyzkouší, zda kružnice se středem uprostřed mezi těmito body a obsahující tyto dva body na hranici neobsahuje všechny body. Pokud ano, máme zřejmě hledaný střed (menší kružnice totiž zřejmě existovat nemůže). Pokud ne, tak algoritmus prostě vyzkouší všechny trojice bodů. Ke každé trojici sestrojí kružnici opsanou oněm třem bodům, otestuje, zda obsahuje všechny body a pokud ano, tak ji porovná s nejmenší dosud nalezenou kružnicí. Tento postup lze poměrně snadno naimplementovat v čase O(N3). Protože míříme k poněkud vyšším metám, nebudu se detaily implementace tohoto algoritmu zabývat.
Pro jednoduchost nadále předpokládejme, že žádné čtyři body neleží na jedné
kružnici (mohli bychom se obejít i bez tohoto předpokladu, ale situace by se
nám poněkud zkomplikovala). Náš algoritmus je založen na jednoduché rekurzivní
funkci MinKruh(V,H). Ta má jako parametry dvě množiny bodů – H je množina
bodů, které mají ležet na hledané kružnici, V je množina bodů, které
mají ležet uvnitř nebo na hranici. Funkce pak vrací nejmenší kružnici, která splňuje
výše uvedené požadavky. Na počátku voláme funkci s parametry M,
∅ (M je množina bodů, pro které máme kružnici nalézt).
A jak funkce pracuje? Pokud už je množina V prázdná, jen sestrojíme kružnici opsanou bodům v H a jsme hotovi (protože v H budou vždy nejvýše tři body, nebude sestrojení kružnice problém). Jinak vybereme náhodný bod z V, odebereme ho a rekurzivně si necháme nalézt kružnici pro menší V. Pokud nalezená kružnice obsahuje i zvolený bod, nemusíme dále nic dělat a kružnici pouze vrátíme. Pokud kružnice bod neobsahuje, musí bod nutně ležet na hranici nejmenší kružnice pro množinu V∪H. Zařadíme ho tedy do H a rekurzivně se zavoláme na menší V a větší H – kružnice, kterou nám vrátí toto volání bude zaručeně naše hledaná nejmenší kružnice. Všiměte si, že v H nikdy nebudou více jak tři body – pokud nějaký bod dáme do H, tak už musí ležet na hranici nejmenší kružnice. Na té jsou ale nejvýše tři body.
Správnost algoritmu jsem se snažil vysvětlovat v popisu, takže nám už chybí jen odhad časové složitosti. S tou to bude trochu obtížnější. V nejhorším případě může být složitost výše uvedeného algoritmu až exponenciální (pokaždé si vybereme bod z hranice kružnice). V průměrném případě na tom ale budeme o mnoho lépe – časová složitost bude lineární (O(n), kde n je počet bodů). A jak se to spočítá? Inu zkusme to následovně: Označme T(n,k) průměrný čas potřebný ke zpracování množiny V o velikosti n a množiny H o velikosti k. Zřejmě platí, že T(0,k)=c, kde c je vhodná konstanta odpovídající času na nalezení kružnice procházející třemi body. Dále platí:
První člen součtu je za první rekurzivní volání, druhý člen je za druhé volání. To ovšem proběhne pouze pokud jsme špatně zvolili bod a to se stalo právě s pravděpodobností (3-k)/n (v naší množině n bodů je právě 3-k špatných bodů z hranice). d je pak vhodná konstanta odpovídající času na testování, zda bod leží uvnitř kružnice a podobně. Když si nyní dáme trochu práce a rekurenci vyřešíme, vyjde nám skutečně, že T(n,k)=O(n). Na závěr diskuse složitosti bych ješte poznamenal, že existují i algoritmy se zaručenou složitostí O(n log n). Ty už používají poněkud komplikovanějších technik.
Program je přímou implementací algoritmu. Pouze množiny jsou reprezentovány seznamem prvků v poli a pole jsou předávána odkazem (předávání polí hodnotou by nám zkazilo časovou složitost). Při testování, zda bod leží v kružnici pak zbytečně neodmocňujeme a porovnáváme druhé mocniny vzdáleností.
14-5-2 Tramvaje (Zadání)
Tato úloha s veleznámým cestovatelem Dvoukvítem se dala řešit různě. Jistě by v tom každy z vás našel Dijkstru, mnozí hravější z vás našli i jiné mnohdy efektivnejsi algoritmy a tak vypadá i vzorové řešení.
A teď již k řesení. Nejdříve bylo dobré si pohrát se zadaným problémem a zjistit nějaké zákonitosti, které zde platí. Po chvilce uvažování přijdete na to, že se využívají jenom směry od startu ke konci (jet zpět se nikdy nevyplatí). Tedy pokud máme startovní vrchol v levém horním rohu a konec v pravém dolním, potom používáme pouze cesty dolů a doprava. Tím si značně ulehčíme práci. A abychom nemuseli řešit spousty okrajových situací, všechna uskupení si převedeme rotacemi na situaci, kdy je začátek vpravo nahoře a konec vlevo dole. A nyní již stačí projít síť zleva doprava a shora dolů trochu upraveným prohledáváním do šířky. U každého uzlu si budeme počítat nejmenší čas, ve kterém jsme schopni z daného uzlu vyrazit v x-ovém a y-ovém směru. Pak už jen stačí projít a vypsat cestu, která dosáhla nejkratšího času (tu snadno zrekonstuujeme tak, že půjdeme z cíle vždy na políčko, ze kterého šlo vyjet nejdříve).
Správnost algoritmu zřejmě plyne z toho, že směry, které má smysl používat, jsou pouze shora dolů a zleva doprava. Časová složitost algoritmu je O(N·M) a paměťová je O(N·M).
14-5-3 Zapeklitý kabel (Zadání)
Nejprve krátce k bodování této úlohy: Nezbytnou součástí řešení této úlohy měl být i (rychlý) program, který radí technikovi firmy Shumm & Brumm, jak kabely spojovat. K získání plného počtu 9 bodů bylo tedy nejen nutné vymyslet optimální postup spojování kabelů (tedy s 2 návštěvami pekla), ale i program s lineární časovou složitostí, který optimální postup vygeneruje a pak vyhodnotí.
Nechť N označuje počet vodičů v položeném kabelu. Povšimněme si, že pro N=1 je úloha triviální a pro N=2 je úloha naopak neřešitelná. Omezme se tedy na ty případy, pro které platí N≥ 3. Řešme nejdříve případ, kdy N je liché. Při první návštěvě pekla spojíme prvních ⌈N/2⌉ dvojic kabelů, tj. a1–a2, a3–a4, a5–a6, … , aN-2–aN-1. Na druhé straně pak měřením zjistíme, které dvojice kabelů jsou pospojovány do dvojic a který kabel není v dvojici (a tedy odpovídá konci aN v pekle). Při druhé návštěvě pekla, vytvoříme opět ⌈N/2⌉ dvojic kabelů, ale nyní to budou dvojice a2–a3, a4–a5, a6–a7, … , aN-1–aN. Protože víme, který konec b? odpovídá konci aN, můžeme určit, který konec b? odpovídá aN-1. Z výsledků měření v prvním kroku pak můžeme určit, který konec b? odpovídá aN-2 (je to ten konec b?, co byl s koncem b? odpovídajícím aN-1 spárován v prvním kroku). Nyní lze určit konec b? odpovídající aN-3 (je nyní spárován s koncem b? odpovídajícím aN-2), a takto pokračujeme až ke konci b? odpovídajícímu a1.
Pokud je N sudé, je postup potřeba malinko upravit a to následovně: V prvním kroku ponecháme vodiče aN-1 a aN nespárovány, tj. vytvoříme N/2-1 párů vodičů. V druhém kroku ponecháme nespárovány vodiče a1 a aN. Konec b?, který byl nespárován v obou krocích, zřejmě odpovídá konci aN. Druhý konec, který byl nespárován v prvním kroku, odpovídá aN-1. Zbytek postupu je stejný jako v případě, že by N bylo liché.
Zbývá domyslet, jak rychlý může být program, který výše uvedený postup navrhne a vyhodnotí výsledky technikova měření. Samotné vypsání dvojic vodičů, které je třeba spojit v prvním a druhém kroku je triviální. Při vyhodnocování měření v druhém kroku potřebujeme následující:
- Znát jeden či dva (v závislosti na paritě N) vodiče, které byly v prvním kroku nespárovány.
- Ke konci b? umět rychle (tj. v čase O(1)) najít druhý konec b?, se kterým byl spárován v prvním kroku.
První bod je snadný – do speciálních proměnných slepy a slepy2
si uložíme indexy i takové, že bi v prvním kroku nebyl vodivě spojen
s jiným koncem b?. K dosažení druhého bodu, si v prvním kroku naplníme
pomocné pole pary následovně: Hodnota pary[i] je rovna 0,
pokud vodič bi není spárován. Jinak obsahuje (jednoznačně určený) index j
takový, že vodiče bi a bj jsou spárovány (přesněji jim odpovídající konce
a? vodivě spojeny). S pomocí tohoto pole je snadné vyhodnotit
měření v druhém kroku (postupem popsaným v druhém odstavci) v čase O(N).
Paměťová složitost navrženého algoritmu je též O(N) (je třeba uchovat pole pary).
14-5-4 Turingovy stroje (Zadání)
První části úlohy – tj. zjistit, zda Turingovu stroji bude k výpočtu stačit počet políček omezený nějakým daným k – se všichni zhostili úspěšně (ačkoliv více či méně efektivně). S druhou částí úlohy to ale bylo o dost horší a pouze jediné řešení bylo správně.
Ověřit, zda Turingovu stroji bude k výpočtu stačit k políček, je úloha poměrně jednoduchá. Budeme postupně simulovat Turingův stroj. Pokud někdy během simulace bude stroj chtít vstoupit na k+1-ní políčko, řekneme, že stroji k políček nestačilo. Pokud během simulace stroj skončí (hlava narazí do levého okraje pásky), stroji zjevně k políček stačilo. Jediná netriviální otázka je, jak vyřešit případ, kdy se Turingův stroj zacyklí. I to lze ale vyřešit poměrně elegantně – celkový stav stroje (a tím i celý následující výpočet) je zřejmě v každém okamžiku jednoznačně určen obsahem prvních k políček pásky, vnitřním stavem stroje a pozicí hlavy. Pokud má stroj q stavů a a písmen v abecedě, je možných celkových stavů stroje tedy ak·k·q. Pokud tedy stroj vykoná alespoň ak·k·q+1 kroků, musel se zaručeně do nějakého celkového stavu dostat alespoň dvakrát a to znamená, že se musel zacyklit. Stačí tedy při simulaci počítat počet kroků stroje a po určitém počtu kroků již s jistotou víme, že se stroj musel zacyklit.
Otázka, zda stroji stačí nějaký omezený počet políček (ale tento počet nemáme dán), je neřešitelná. Pokud bychom tento problém uměli vyřešit, uměli bychom totiž vyřešit i tzv. Halting problém – tedy problém, zda se daný Turingův stroj na daném vstupu někdy zastaví. Mohli bychom se totiž zeptat, zda danému Turingovu stroji stačí omezená paměť (na to bychom právě použili algoritmus z předpokladů). Pokud je odpověď záporná, stroj se zjevně nikdy nemůže zastavit. Pokud je odpověď kladná, můžeme stroj simulovat s omezeným počtem políček stejně jako je popsáno v předchozím odstavci. Pokud simulace skončí s tím, že stroj chtěl použít více políček, zkusíme ho pustit s prostorem o políčko větším. Jinak simulace může skončit buď tím, že se stroj zacyklil, nebo že doběhl. V obou případech pak stačí dát příslušnou odpověď (tedy stroj neskončí pro první případ resp. skončí pro druhý). Protože počet políček, která stroj potřebuje, je omezený, zřejmě musí jednou simulace skončit buď oznámením o zacyklení či skončení.
Protože si nyní ukážeme, že Halting problém je neřešitelný, nemůže mít řešení ani náš problém. Pro spor předpokládejme, že Halting problém je řešitelný. V tom případě existuje nějaký Turingův stroj H(S,V), který přijme právě když se stroj S zastaví na vstupu V. My si nyní sestrojíme pomocný stroj H'(S), který přijme právě když se stroj S zastaví na vstupu S (tedy když stroji S na vstup podstrčíme jeho vlastní zápis). Ze stroje H'(S) pak můžeme snadno sestrojit stroj A(S), který se zastaví právě když H' odmítl S (tedy právě když se stroj S na vstup S nezastavil) – prostě necháme běžet stroj H' a pokud by chtěl skončit přijmutím, tak se zacyklíme, jinak skončíme. Nyní ale přichází záludná otázka a s ní i spor: Co udělá stroj A na vstup A? Z konstrukce se A zastaví právě když H' odmítl A a to je právě když se A na vstup A nezastavil. A se tedy nemůže ani zastavit ani nezastavit. Nemůže tedy existovat, a proto nemůže existovat ani původní stroj H, ze kterého jsme stroj A snadno sestrojili.