Pátá série desátého ročníku KSP

Řešení úloh

10-5-1 Společná podmatice (Zadání)

Zkusme nejprve vyřešit následující modifikaci úlohy tohoto příkladu: Jsou zadány dvě matice stejných rozměrů (N×M) a máme nalézt největší stejnou podmatici těchto matic takovou, že je v obou dvou maticích na stejném místě. Tuto úlohu lze snadno převést na hledání největší jedničkové podmatice dané matice tak, že si vytvoříme matici, která bude obsahovat nuly tam, kde se naše matice liší, a jedničky tam, kde se shodují (sledujte obrázek). Nyní vypočteme pro každý nenulový prvek matice, kolik je nad ním a pod ním jedniček a tato čísla uložíme do dvou pomocných matic. Tento výpočet lze provést v čase lineárně úměrném velikosti (obsahu) matic a to průchodem matice vhodným směrem (postupná inkrementace počtu jedniček v právě procházeném souvislém úseku v daném sloupci). Takto vzniklé matice „obalíme“ pásem nul, což nám zjednoduší další výpočet.

Největší jedničková podmatice je největší, což zejména znamená, že existuje nějaká nula těsně za jejím levým okrajem, neboť by jinak bylo tuto podmatici možné zvětšit, to nám zaručuje mimo jiné i její obalení. Náš postup bude takový, že budeme procházet matici po řádcích a od každého přechodu z nulového na nenulový prvek se budeme snažit nalézt největší podmatici, jejíž levá hranice je těsně u tohoto nulového prvku. Mezi takovýmito podmaticemi bude i hledaná (největší) podmatice, jak jsme si již řekli. To je však jednoduché naprogramovat, neboť velikost největší takovéto jednotkové podmatice šířky k, pokud za uvažovanou nulou následuje alespon k jedniček, je rovna k× součtu minima počtu jedniček pod a nad těmito jedničkami. Toto minimum lze snadno vypočítat v konstantím čase, pokud si ho budeme pamatovat pro k-1. Celková časová složitost tohoto algoritmu je tedy O(NM) a paměťová O(NM).

Nyní již snadno vyřešíme naši úlohu. Stačí postupně uvážit všechny vzájemné posuny obou matic a pro každou z nich vyřešit naši modifikovanou úlohu pro výřezy těchto matic tvořené jejich společnou plochou. Jsou-li rozměry matic N1×M1 a N2×M2, potom vzájemných posunů, tj. různých poloh jejich levých horních rohů vůči sobě, je O((N1+N2)*(M1+M2)). Pro každý takovýto posun se provede algoritmus popsaný v úvodu řešení a celková časová i paměťová složitost algoritmu bude

O(max(N1,M1)2·max(N2,M2)2).

Na závěr ještě několik poznámek k programu. Zadané matice jsou uloženy v polích pole1 a pole2, jejich rozměry pak v proměnných pole1? a pole2?. Údaje o výřezech matic jsou ukládány do pole rozdil. Velikost výřezu je uložena v proměnných rozdil?, posun levého horního rohu výřezu vůči levému hornímu rohu první a druhé matice jsou uloženy v proměnných posun1? a posun2?, posun levých horních rohů obou matic pak v proměnných posun?. Za povšimnutí stojí sloučení obou pomocných polí z popisu algoritmu pro hledání společné podmatice v jedno tak, že nulové hodnoty jsou neshodné prvky matic, záporné udávají posun dolů (záporně vzatý) na nejbližší nenulovou hodnotu nad nulovou hodnotou v tomto sloupci, kladné udávají počet nenulových hodnot v souvislém bloku ve sloupci matice – viz obrázek.

1 2 2
2 1 2
1 2 2
2 1 2
+
2 1 1
2 1 2
1 2 1
1 1 1
→
0 0 0
1 1 1
1 1 0
0 1 0
→
0 0 0
1 1 1
2 2 0
0 3 0
→
0 0 0
-1 -2 1
2 -1 0
0 3 0

Program

Daniel Kráľ

10-5-2 Kob ýlam ám alybok? (Zadání)

Zaveďme rovnou potřebné termíny – řetězec, který lze číst z obou stran stejně, to jest který je zrcadlově souměrný podle středu, nazveme palindromem. Palindrom je maximální, pokud už ho nelze prodloužit o jeden znak na každé straně. Maximální palindromy mají různé středy a ten nejdelší z nich hledáme.

Otestovat všechny řetězce zadaného textu, zda nejsou palindromy, je možno v čase O(n3) (cyklus přes začátky, cyklus přes konce a cyklus testovací). Většina řešitelů ovšem snadno nahlédla redundanci danou zejména tím, že se takto – beznadějně – testují i řetězce, jejichž prostředky byly nebo budou samy o sobě zavrženy.

Lepší řešení tedy je procházet všechny potenciální středy palindromů, tedy i pozice mezi dvěma sousedními písmeny, a snažit se identifikovat co nejdelší palindrom se středem v tomto bodě. Toto řešení bude v případě velkého množství překrývajících se palindromů (jako například ve větě "Jůůůůůůůůůůůůů, šnek!") pracovat v čase O(n2); navíc pokud se nebudou palindromy překrývat o víc než pevně stanovený počet písmen, bude možno mluvit o lineárním čase.

I toto řešení však má v sobě skrytou redundanci. Pokud zkoumáme určitý střed a víme, že je tento střed někde uvnitř dříve nalezeného velmi dlouhého palindromu, máme vlastně chování okolo tohoto středu už prozkoumáno. Stačí se podívat, jak dopadl jeho zrcadlový kolega na druhé straně dlouhého palindromu. (Procházíme-li jednotlivými středy postupně, byl tento kolega zkoumán ještě před oním dlouhým palindromem.) Může se samozřejmě stát, že kolegové maximálního palindromu sahají až za hranice dlouhého palindromu: ageloKolegajekleVelkejageloKole??? (zkoumáme střed K na pravé straně, v bodu V je střed velkého palindromu, který sahá ještě tři znaky za nás). V každém případě ale víme, že velikost našeho palindromu je větší nebo rovna velikosti jeho zrcadlového kolegy, takže stačí použít tu a pokusit se ještě o prodloužení.

To znamená, že pracujeme nejen s momentálním středem, ale také s tabulkou všech dosud ověřených maximálních palindromů a s nejpravějším bodem, který máme podchycený některým dosavadním palindromem. Nikdy neporovnáváme dva prvky před tímto nejpravějším bodem, protože vše, co potřebujeme, už máme z výše uvedeného důvodu v tabulce: pokud úspěšně sáhneme na prvek za tímto hraničním bodem, tato hranice se tím posune; pokud při prodlužování palindromu neúspěšně sáhneme na některý prvek, ukončí se tím zpracovávaný palindrom a posune se střed. V každém kroku se tedy součet středu a tohoto hraničního bodu zvýší o jedna a tento součet lze shora omezit O(n), proto provedeme nanejvýš O(n) kroků a tento algoritmus je lineární v každém případě. Prostorové nároky jsou rovněž lineární.

Zbývá dořešit drobné uživatelské požadavky na ignorování mezer, velikosti písmen, případně ošetření písmene `ch'. Ty vzorový program implementuje ve funkci get_text_and_make_tokens(); musíme si však do polí original a offset ukládat původní text a přesměrování našich vnitřních znaků na znaky původní, abychom mohli nalezený palindrom věrně vytisknout. Kromě toho mezi každými dvěma vstupními znaky generujeme jeden konstantní vnitřní znak. To je proto, abychom mohli zároveň zpracovávat palindromy liché (se středem ve skutečném znaku) i sudé (se středem v některém `výplňovém' znaku), což lze docílit i bez tohoto plýtvání místem, leč za cenu dalšího znepřehlednění práce s indexy nebo zdvojení časti programu.

Vzorový program pro jednoduchost předpokládá, že znaky malé i velké abecedy jdou po sobě od `A' do `Z' a že je známa horní mez pro délku textu.

Program

Jirka Hanika

10-5-3 Cycloose (Zadání)

Cyklus ze zadání rozhodně nedoběhne zítra, nedoběhne za týden, za rok, ba ani za miliardu let … nedoběhne totiž nikdy, čímž ostatně mnohé z vás doběhl. Pointa pro nedočkavé: typ real má omezenou přesnost, takže během výpočtu dojdeme k r velkému natolik, že r+1 se již zaokrouhlí zpět na r.

A proč tomu tak je? Inu, bude nejlepší, když se podíváme na typ real (resp. float) zblízka. V obou případech se jedná o racionální (nikoliv tedy o obecně reálná, jak se Pascalský název typu snaží namluvit) čísla ukládaná ve formátu s plovoucí řádovou tečkou (floating-point), což znamená, že jsou vyjádřena ve tvaru

x = ±m ·be,

kde:

Pro běžné počítače je b=2, 7≤ M≤ 16 a 23≤ N≤ 64, dále tedy budeme předpokládat výhradně binární representaci.

Příklad: Číslo 5 by se ve floating pointu zapsalo jako 5=+0.625·23. Povšimněte si, že nulu analogicky zapsat nelze – volí se pro ni obvykle nějaký nestandardní zápis (reservuje se jedna hodnota exponentu pro nulu, nekonečna a jiné "podezřelé" hodnoty nebo se v tomto případě připustí m=0). Všechna ostatní čísla (pokud nejsou mimo representovaný rozsah) je možno zapsat právě jedním způsobem (vezmete jejich binární zápis, najdete první jedničku zleva, zvolíte e tak, aby se dostala právě za řádovou tečku [vše před ní již budou nuly] a výsledek prohlásíte za mantisu, ovšem musíte ji ponejprv zaokrouhlit, aby se vešla do N bitů).

A nyní již k slíbenému "protipříkladu". Představte si číslo tvaru r=2N+1=0.5·2N+2. Pro takovéto r nám vyjde r′=r+1 =(0.5+2-N-2)·2N+2, takže mantisa m′ bude rovna 0.5+2-N-2, což je ovšem po zaokrouhlení na M bitů pro její uložení dostupných určitě rovno 0.5, tedy původní mantise, takže r+1=r′=r. (Kdybychom volili r=2N, museli bychom uvažovat o tom, zda se m′ zaokrouhlí nahoru či dolů, při r=2N+1 musí nutně dolů.) A teď si jen stačí uvědomit, že pro největší běžné M vyjde r=265<1020, což je hluboko pod horní mezí našeho cyklu. [Aby se tento rozbor stal opravdu korektním důkazem věčnosti cyklu, bylo by ještě nutno dokázat, že naše "zastavovací" číslo nemůže program přeskočit – toho byste ale již po tomto úvodu měli být schopni vy sami.]

Martin Mareš

10-5-4 S radostí přijmi svůj (o)sud (Zadání)

Algoritmus provádí prohledávání stavového prostoru do šířky. Jednotlivé stavy odpovídají uspořádaným n-ticím <a1,… ,an> popisujícím naplnění jednotlivých lahví, přechody mezi stavy pak přelitím. Tím, že vše procházíme do šířky, máme zaručeno, že nalezneme řešení s nejmenším počtem přelití.

Použijeme klasickou implementaci s frontou na dosud nezpracované stavy. Na počátku fronta obsahuje stav <0,… ,0> (všechny lahve prázdné) a v každém kroku vezmeme jeden dosud nezpracovaný stav a vyzkoušíme všechna možná přelití, přičemž vzniklé stavy zařazujeme na konec fronty (vynecháváme samozřejmě ty, které jsme již jednou viděli, abychom předešli zacyklení).

Program se řídí přesně tímto algoritmem, jediné, co stojí za zmínku, je, že naše stavové n-tice kódujeme celými čísly, abychom jimi mohli snadno indexovat pole. Toto kódování a dekódování stavů je zabezpečeno procedurami Koduj a Dekoduj.

Pokud si označíme s velikost stavového prostoru (to jest součin kapacit lahví zvětšených o 1) a n počet lahví, časová složitost algoritmu bude O(s·n) (každý stav projdeme max. jednou a zkoumáme max. O(n) jeho sousedů), paměťová pak O(s) (potřebujeme pamatovat frontu plus pro každý stav, zda jsme v něm již byli či nikoliv).

Program

Michal Píše