První série devátého ročníku KSP

Řešení úloh

• 9-1-1: Cesta kulhavého koně
• 9-1-2: Kupec Bengálský
• 9-1-3: Strašidlóóó
• 9-1-4: Top secret

9-1-1 Cesta kulhavého koně (Zadání)

Ačkoliv byla tato úloha původně míněna jako něco jednoduššího "na zahřátí", byli jsme nemile překvapeni, že téměř nikdo neposlal korektní řešení. Vyskytovaly se následující neúspěšné pokusy:

1. Heuristiky – to jest řešení založená na různých více či méně podivných předpokladech (typu "když se budu pohybovat tak, abych postupně zmenšoval součet absolutních hodnot svých souřadnic a souřadnic cíle, bude taková cesta zaručeně nejkratší"), které měly společné jedno: chyběl korektní důkaz toho, že nalezená cesta bude vskutku optimální.

A také že bylo velice často snadné vymyslet protipříklad. To si dokonce uvědomili i někteří autoři takovýchto řešení a začali do nich přidávat dodatečné omezující podmínky typu "když jsou dvě možnosti podle mého základního kriteria rovnocenné, vyberu ten tah, kterým se dostanu blíže ke středu" nebo "pokud jsem již od cíle vzdálen v každé ose méně než 3 pozice, dojedu podle přiložené tabulky" – leč opět opomněli zdůvodnit, proč jiné "špatné" situace nastat nemohou.

Pro tato "vylepšovaná" řešení ovšem již hledání protipříkladů nebylo tak snadným, pročež ne každému jsme takový s opraveným řešením poslali. Za všechny zde budiž uveden "universální protipříklad" na alespoň polovinu chybných algoritmů: šachovnice 4 ×4, vycházíme z levého horního rohu (0,0) a chceme se dostat do pravého dolního (3,3). Optimální cesta je například (0,0) – (2,1) – (1,2) – (3,3). Typická heuristika skáče z (0,0) na (2,1), pak na (3,2) nebo (2,3) a odtamtud se již jediným koňským skokem zaručeně do cíle nedostane, tudíž vygeneruje cestu, která není nejkratší (pokud ovšem vůbec nějakou nalezne – mnohé z vašich programů se prostě na takovémto zadání zacyklily na věčné časy).

2. Jednoduchý algoritmus typu "vlna" – začneme políčkem se vzdáleností 0, pak hledáme políčka o vzdálenosti 1, … vždy z políček o vzdálenosti n hledáme políčka se vzdáleností n+1, prostě klasický postup hledání do šířky.

Na tomto postupu ještě nic špatného není, ale přeci jen tu je jeden háček: nestačí si totiž pro každé políčko pamatovat délku nejkratší cesty ze startu do něj a tyto tahy se pokoušet prodlužovat – tím totiž zapomínáte na to, že tahy se musí pravidelně střídat. Ačkoliv nejkratší možný tah vedoucí na pole (x,y) končí tahem koně, nejkratší tah na pole (x+2,y+1) například může být skokem koně z (x,y) s tím, že na (x,y) se dostanete o 1 tah delší cestou, která končí tahem krále, abyste mohli správně navázat.

Místo tohoto poněkud zmateného popisu asi poslouží lépe ukázka, kdy to skutečně selže. Není pro ni ovšem třeba chodit příliš daleko: universální protipříklad pro heuristiky prokáže svoji universalitu i zde. Prvním tahem koně se můžete dostat na (1,2) a (2,1), z těchto pozic pak králem na libovolnou pozici mimo (0,0) a (3,3), tedy i na (1,2) a (2,1), což na první pohled vůbec není rozumné, neboť tam se dokážeme dostat jedním tahem (což si program rovněž uvědomí a na tyto tahy spokojeně zapomene). Nu ano, ale pole (3,3) je dostupné ve třetím tahu (tedy koněm) pouze z (1,2) a (2,1), na která se ovšem musíme dostat králem, takže i takovýto program správné řešení nenalezne.

3. Backtracking alias prohledávání do hloubky není z principu špatně – na rozdíl od dříve zmíněných "řešení" alespoň správnou cestu vždy najde – ale zato za rekordně dlouhou dobu, která závisí na velikosti šachovnice exponenciálně. Tedy pro šachovnici 30×30 již v praxi naprosto nepoužitelné (miliony let na výpočty obvykle k dispozici nemáme).

A jak tedy? Po tomto vyčerpávajícím (spíše čtenáře nežli téma) výčtu špatných řešení tedy přikročme k nějakému správnému: Použijeme opět prohledávání do šířky, ovšem trošku upravené, aby fungovalo korektně. Pro každé pole si nebudeme pamatovat délku jedné nejkratší cesty do něj, nýbrž cest dvou – té, která končí tahem koně a té, která končí tahem krále.

Na počátku víme, že do výchozího políčka se můžeme dostat cestou délky nula, která de facto končí tahem krále – žádný tah tam sice nebyl, ale dál táhneme tak, jako bychom na něj navazovali – to jest koněm.

Nyní postupně hledáme všechna políčka o vzdálenostech 1, 2, …n, a to tak, že máme-li nalezena všechna políčka vzdálená od počátku méně než k, snadno najdeme i ta, jež mají vzdálenost k – jsou to taková, do kterých se umíme dostat koňským skokem (je-li k liché) nebo královským krokem (je-li sudé) z políček o vzdálenosti k-1.

Leč nás pro každé políčko zajímají pouze délky nejkratší "královské" a "koňské" cesty, tudíž dostaneme-li se novým tahem délky k někam, kam jsme se již dokázali dostat kratším tahem stejného typu, můžeme nový tah s klidným svědomím ignorovat, aniž bychom udělali stejnou chybu jako v "řešení" č. 2, jelikož všechna možná pokračování nového tahu mohou být (kratšími!) pokračováními onoho kratšího tahu, aniž bychom porušili požadavek střídání.

Bylo by ale zbytečné v každém kroku hledat všechna políčka o dané vzdálenosti v nějaké matici. Použijeme tedy fintu: zavedeme frontu F dosažitelných, ale ještě nezpracovaných políček, která bude na začátku obsahovat pouze výchozí pole, během výpočtu pak nezpracovaná políčka seřazená vzestupně podle jejich vzdáleností od startu. Každý krok pak bude vypadat takto:

1. Vyber jedno políčko (x,y) z F (tedy nejbližší ještě nezpracované). Pokud byla fronta prázdná, jsme v koncích a cesta neexistuje.
2. Pokud se toto políčko rovná cílovému, nalezli jsme slíbenou nejkratší cestu a končíme.
3. Vezmeme všechna políčka z (x,y) dosažitelná, přičemž zkoušíme napojit jak tah koně, tak tah krále (pro každý víme, jak bude dlouhý, neboť si to pamatujeme v poli).
4. Pro každé z těchto políček testujeme, zda jsme se do nich již dokázali dostat cestou daného typu, která byla kratší. Pokud nikoliv, poznamenáme si tuto (pro daný typ tahu zaručeně nejkratší) vzdálenost a políčko zařadíme na konec fronty.

Každé políčko se tedy do fronty mohlo dostat nejvýše dvakrát – jednou jako koncové pro královský tah, jednou pro tah koňský. Kapacita fronty tedy musí být alespoň 2MN, kde M a N jsou rozměry šachovnice.

Zbývá ještě dořešit, jak vypisovat nalezenou cestu. Možnosti jsou dvě: jedna by byla začít v cílovém políčku, to vypsat, najít dostupné (resp. doskočné – podle vzdálenosti) políčko s vzdáleností menší o 1 (zaručeně existuje) a tím pokračovat, jako by ono bylo tím cílovým atd. až se dobereme k políčku výchozímu. Nebo můžeme ke každému poli poznamenat pro oba typy tahů nejen jak dlouhý byl minimální tah, ale také odkud přišel a stejným způsobem vypsat cestu "pozadu". Vybereme si první variantu, ježto je paměťově méně náročná.

A jak to je s časovou a paměťovou složitostí? Každé políčko (těch bylo M·N) jsme "vzali do ruky" nejvýše dvakrát a udělali pro něj nějaké konstantní množství operací. Při vypisování cesty jsme zaručeně nepoužili jedno políčko více jak jednou. Časová složitost je tedy O(M·N). Paměť potřebujeme jednak na frontu (2MN položek), jednak na pole obsahující vzdálenost (kMN položek, kde k je nějaké přirozené číslo). Dohromady tedy rovněž O(M·N).

A je toto řešení skutečně optimální? Se smutkem v očích vám mohu prozradit, že nikoliv. Existuje řešení s časovou složitostí O(M+N), nicméně je poměrně složité a jeho důkaz (alespoň nejlepší, který se nám podařilo nalézt) velice dlouhý, pročež jej zde neuvedeme. Nastiňmež alespoň základní myšlenku: Netriviálním trikem je možno pro každá dvě políčka spočítat v konstantním čase jejich vzdálenost (to je právě to, co se musí složitě dokazovat) a poté můžeme použít první z popsaných metod na vypisování cesty přímo, aniž bychom před tím cokoliv počítali.

Program

Martin Mareš

9-1-2 Kupec Bengálský (Zadání)

Cor Sair ovi to dalo dosti přemýšlení a jednu noc kvůli tomu dokonce nespal, ale výsledek stál za to. Když ve smluvený den přišel k Mer Chantovi, jenž se jen poťouchle usmíval, pravil: "Dobrá, ty bídný Mer Chante, přistupuju na tvé platební podmínky. Koule, které dostaneš, však budu vybírat já!" Mer Chant ochotně souhlasil a dokonce se rozesmál nahlas. Plácli si tedy a vážení mohlo začít. O několik chvil později Cor Sair spokojeně odcházel, drže si v podpaží kouli plnou zlata a Mer Chant jen tiše běsnil v koutku svého hokynářství. (dle řešení Pavla Šedivého).

Jak to Cor Sair udělal?

Vzal nějakých šest koulí a položil je na váhy. Nemusel být génius na to, aby věděl, že na každou misku musí položit 3. Po ustálení vah už věděl, ve které trojici je zlatá koule:

Pokud byla jedna z misek těžší než druhá, byla zaručeně zlatá koule mezi těmi na první misce.

Hmm… a co když zůstaly váhy v rovnováze? To přeci znamená, že obě trojice jsou stejně těžké a že zlatá koule je mezi 3-mi koulemi, které dosud nebyly váženy.

Cor Sair tedy věděl, ve které trojici je zlatá koule a také ve kterých šesti koulích zlatá určitě není – a třemi z nich zaplatil Mer Chantovi za první vážení.

Potom Cor Sair vzal dvě ze tří "nadějných" koulí a položil je na misky vah. Po dalším vážení věděl (obdobně jako v předchozím vážení), která koule je zlatá a už z předchozího vážení měl 3 koule, jimiž Mer Chantovi zaplatil.

A Mer Chant nakonec zjistil, že i kdyby chtěl za každé vážení koule čtyři, i tak by jej Cor Sair přelstil stejným způsobem…

Pavel Machek

9-1-3 Strašidlóóó (Zadání)

Tuto úlohu jste všichni nějak vyřešili, až na pár nefunkčních programů. Nutno zdůraznit, že jste mnohdy ztratili body za chybějící nebo nedostatečný popis algoritmu a hlavně za chybějící popis programu. Podívejte se, jak vypadá vzorové řešení a podle toho zkuste příště psát.

Největší problém byl ve složitosti algoritmu. Někteří napsali i tu nejjednodušší metodu, která byla zkusit každý bod matice (M·N) vzít jako levý horní roh hledaného obdélníka a vyzkoušet k němu všechny možné pravé dolní rohy (těch je přibližně M·N) a vyzkoušet, zda obdélník s danými souřadnicemi je plný nul (přibližně M·N testů). Což dává dohromady přibližnou časovou složitost algoritmu M³·N³, která nikoho nemůže uspokojit.

Dle zadání se v obdélníku (budeme mu říkat matice) mohou vyskytovat nulové a nenulové hodnoty. Velikost nenulových hodnot nás nezajímá, proto ze všech nenulových hodnot uděláme nulové a ze všech nulových hodnot uděláme jedničky.

Abychom se nemuseli zabývat okraji, vytvoříme kolem celé matice pás z nul.

Dále si vytvoříme 2 pomocné matice (A, B) o stejné velikosti, a na místa jedniček napíšeme počet jedniček, které se nachází přímo pod danou jedničkou (v matici A) a nad danou jedničkou (matice B) (včetně).

Úvaha: Hledaná strana maximálního jedničkového obdélníku musí přiléhat buď k okraji matice, nebo k nulovému prvku. Protože jsme si okolo celé matice vytvořili pás nul, můžeme prohlásit, že strana maximálního jedničkového obdélníka přiléhá k nějakému nulovému prvku.

Složitost a popis programu: Nejprve vytváříme matice A a B. Vytvoření znamená projít každý prvek matice a přičíst jedničku k hodnotě prvku nad (pod) ním. Tedy vytvoření jedné matice má čas. složitost OM·N. Pro druhou matici totéž. Poté postupujeme postupně přes všechny prvky matice A a zároveň B a každý prvek testujeme na nulu (přiléhavá nula), pokud ano, jdeme po nenulových prvcích doprava až k další nule a pro každý nenulový prvek se provádí testování dalších nenulových prvků – napravo až do další nuly – a výpočet: test na doposud největší obsah. Hledání probíhá ve dvou vnořených for-cyklech. Výpočet uvnitř cyklu se provádí pouze pro nulové prvky a probíhá přes všechny nenulové prvky napravo. Nulových prvků je v matici nejvýše N·M. Pro žádný prvek neprobíhá výpočet dvakrát. Tedy celková časová složitost je O(M·N). Pokud jste toto nepochopili, pak si zkuste rozmyslet, že by se dal vnitřní for-cyklus přepsat na while cyklus, aby se žádný prvek matice nemusel testovat dvakrát. Prostorová (paměťová) složitost programu je O(M·N). Matice B je v našem případě zbytečná, neboť bychom její prvky mohli zapisovat přímo do původní matice, která je v našem programu při výpočtu nevyužitá.

Program

Martin Bělocký

9-1-4 Top secret (Zadání)

Jak v počítači reprezentovat velká čísla? Nejjednodušší je omezit shora délku velkých čísel na nejvýše např. sto míst a udržovat je v poli a konstantní délky n:

Je dobré zvolit soustavu, jejíž základ z je mocninou dvojky; v následujícím řešení je z = 256. Použití desítkové soustavy sice eliminuje problémy se vstupem a výstupem, ale rutiny pro počítání jsou pak složitější a pomalejší – je lepší optimalizovat rychlost počítání s čísly proti rychlosti vstupu a výstupu.

Počítání s velkými čísly se dělá přesně tak, jak se počítá na papíře (snad netřeba vysvětlovat znovu – viz učebnice matematiky pro nižší ročníky škol základních).

Časové složitosti operací (n = log N_max je délka největšího čísla N_max):

• sčítání, odčítání: O(n)
• násobení: O(n²), existuje i algoritmus se složitostí cca O(n^1.6).
• dělení O(n²), existuje též rychlejší algoritmus, ale velice složitý.

Nedostatky následujícího vzorového řešení:

• Pro číslo je alokován blok paměti konstantní velikosti, počítá se stále v plné přesnosti. Je otázka, zda dynamické alokování paměti je užitečné, protože je časově náročnější, navíc se většinou počítá s čísly zhruba stejné velikosti.
• Čísla se často kopírují jako blok paměti, přitom by stačilo nějak chytře předávat pouze ukazatele.
• Rutiny nemají jednotné volací konvence: kupříkladu Add(A,A,A) bude fungovat, kdežto Mul(A,A,A) nikoliv.
• Bylo by pěkné, kdyby se operace s velkými čísly zapisovaly stejně jako operace s normálními čísly: např. místo Add(A,B,C) psát C := A + B. V Pascalu to možné není, v C++ je.
• Něco by bylo dobré kvůli rychlosti napsat v assembleru, to by ale nebylo zcela podle pravidel semináře!

Některé (ty významnější) z těchto nedostatků budou odstraněny ve vzorovém řešení příští úlohy, jež bude napsáno v C++.

Top secret – Knihovna

Top secret – Příklad použití knihovny

Jan Kotas