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

Řešení úloh

• 15-5-1: Komprimovaný obrázek
• 15-5-2: Odečtolam
• 15-5-3: Manhattan
• 15-5-4: Továrna
• 15-5-5: Haskell

15-5-1 Komprimovaný obrázek (Zadání)

Nejdříve si zakomprimované úseky rozdělíme do jednotlivých řádků. Stejnobarevné řádky zpracováváme najednou, čímž je jeden úsek rozdělen maximálně na 3 části.

Dále je, postupně po řádcích, rekonstruován původní obrázek. Po zpracovaní celého řádku budeme znát velikosti stejnobarevných oblastí končících na tomto řádku.

Při zpracovávání jednobarevného úseku na řádku k němu připojujeme všechny sousedící stejnobarevné úseky z předchozího řádku. Je důležité si uvědomit, že v řádku se může nacházet několik různých stejnobarevných oblastí, které sousedí s jednou oblastí na předchozím řádku (např. pro obrázek s dvěma čtverci se stejným středem) a kterou bychom tak mohli nedopatřením přičíst víckrát. Řešením může být chápaní úseku (jednobarevných oblasti) jako množin a operaci spojení jako jejich sjednocení.

Množinu si pamatujeme v stromu, jehož kořen „ví“, kolik má množina prvků, a ostatní vrcholy ukazují na nějaký jiný (nadřazený) prvek množiny. Sjednocení spočívá v „přivěšení“ menší množiny k větší a identifikace množiny v nalezení jejího kořene. Abychom zlepšili průměrnou časovou složitost vyhledávaní kořene z O(log S) na O(log ^* S), po každém nalezení kořene upravíme všem prvkům na cestě ukazatel přímo na kořen. Tento algoritmus je znám pod jménem Union-Find.

Ke zjištění maximální stejnobarevné plochy si stačí pamatovat jenom posledně zpracovaný řádek. Uvědomíme-li si, že v jednom řádku může být jenom S různých úseků (S je šířka řádku), vystačíme si s pamětí O(S).

Každý úsek je zpracován maximálně třikrát a v jednom řádku je 2·S-krát vykonána operace find na S prvcích. Časová složitost algoritmu je proto O(N + N/S·S· log ^* S) = O(N log ^* S).

Program

Miro Rudišin

To je ale hezký trik! Ale nešlo by to lineárně? Na celý obrázek se můžeme dívat jako na neorientovaný graf: vrcholy jsou jednobarevné úseky, hrany odpovídají tomu, který s kterým sousedí. Hran je lineárně mnoho (je to totiž rovinný graf) a také je dovedeme v lineárním čase najít, stačí zopakovat algoritmus z předchozího řešení a místo sjednocování Union-Find stromečků přidávat hrany do grafu. A pak už jen graf prohledáním do šířky rozložíme na komponenty souvislosti a spočítáme, jak je která velká.

Martin Mareš

15-5-2 Odečtolam (Zadání)

(Díky Petru Škodovi a Milanu Strakovi)

Každý tah na odečtolamu zachovává součet všech čísel s = a₁ + a₂ + … + a_n (a+b+c = a+b + -b + c+b).

Ukážeme, že pro s = 0 nemá hra řešení (kromě triviálního případu, kdy jsou ve všech vrcholech nuly už na začátku). Protože se součet zachovává, musí hra s s=0 skončit v konfiguraci 0,0,0,…,0. Jenže každý tah otočí znaménko záporného čísla, takže není možné z nenulového čísla vytvořit nulu.

Nechť t je absolutní hodnota součtu všech záporných čísel na odečtolamu.

Výpočet bude probíhat ve fázích, z nichž každá sníží t. Každá fáze bude trvat nejvýše n² tahů. Fáze se bude skládat z nejvýše n podfází.

Na začátku podfáze vybereme nějaké záporné číslo (když žádné není, vyhráli jsme), které je vpravo od případných nul a kladného čísla (určitě existuje). Přečíslujeme vrcholy tak, aby vybrané číslo bylo a₂. Táhneme a₂ a dostaneme:

Dokud se nedostaneme na konec posloupnosti a dokud je to možné, táhneme vrchol vpravo od předchozího vrcholu:

Když dojdeme na konec posloupnosti (to nastane pokud -a₂ > a₃+a₄+… +a_n), bude situace takováto:

což můžeme přepsat jako:

Protože -a₂ > a₃+… +a_n = s-a₁-a₂, tak a₁-s > 0. t se snížilo o s, protože na prvním místě je s+a₂ a a₁-s > 0 a ostatní členy se jen přesunuly. Snížili jsme t, takže skončila fáze.

Na konec posloupnosti nedojdeme, pokud existuje i takové, že -a₂ < a₃+… +a_i. Situace bude následující:

Nechť u = a₁+...+a_i-1. Výraz pak bude:

Zde a₁ je nezáporné (tak jsme ho vybrali) a a_i je určitě také nezáporné, protože jinak by se podfáze musela zastavit už na a_i-1. V posloupnosti se změnily jenom tři členy, ostatní se nejvýš přesunuly: a₁→a₁+a₂; a₂→a₁-u; a_i→u+a_i-a₁.

Čísla a₁-u i u+a_i-a₁ jsou kladná, takže t kleslo o a₁ (aby se podfáze zastavila, musí být a₂+...+a_i-1 = u-a₁ < 0 a a₂+...+a_i = u+a_i-a₁ > 0).

Problém nastane, pokud a₁ je 0, v tom případě ale můžeme vložit další podfázi. S každou podfází se záporné číslo posune doleva, a ubyde jedna nula mezi vybraným číslem a číslem kladným. Nejvýše za n podfází fáze skončí.

Časová složitost je O(n²·t), paměťová složitost je O(n).

Pavel Machek

15-5-3 Manhattan (Zadání)

Řešení je založeno na dynamickém programování – postupně po řádcích (západo-východních ulicích) zleva doprava počítáme počet cest vedoucích do dané křižovatky. Ten je roven součtu počtů cest vedoucích do sousedních křižovatek na západ a na sever (odjinud přijet nemůžeme), které už máme spočítané; případně 0, je-li křižovatka opravována.

Když načteme souřadnice opravované křižovatky, přiřadíme jí hodnotu např. -1 (to můžeme dělat přímo v poli, kam budeme později ukládat počty cest), takže pak zjištění, zda je opravovaná, provedeme v konst. čase. Časová i paměťová složitost tedy jsou O(m·n).

Někteří řešitelé si všimli, že v paměti stačí mít jen právě zpracovávaný a předcházející řádek (dokonce jen části z nich), čímž zlepšili paměťovou složitost na O(k+n). Pak ale nastal problém s určováním, zdali je křižovatka opravovaná, kvůli čemuž si tito řešitelé zhoršili časovou složitost. Ve vzorovém řešení to řešíme tak, že si každou opravovanou křižovatku zařadíme do seznamu pro řádek, ve kterém leží – to se dá v čase i paměti O(k+m) provést třeba použitím spojového seznamu. To, zda je křižovatka opravována, si pak pamatujeme jen pro křižovatky z právě zpracovávaného řádku. Paměťová složitost je O(k+n+m), časová zůstává O(m·n).

Ještě bych se zastavil u velikostí k. Několik z Vás psalo, že křižovatek se v normálním městě neopravuje mnoho, čímž např. ospravedlňovali, že píší O(m·n) místo O(m·n+k· log k). Ona to sice je pravda, ale mezi počtem všech a opravovaných křižovatek platí v normálním městě přibližně přímá úměra a potom by O(k log k) bylo O(m·n· log(m·n)).

Program

Pepa Cibulka

15-5-4 Továrna (Zadání)

Nejprve bych se chtěl za organizátory všem řešitelům omluvit, neboť v zadání úlohy se vyskytla chyba. Pro vzorový příklad je správná odpověď 23, ne 21, jak bylo v zadání uvedeno. Někteří z vás si pak vyložili zadání jinak, než bylo myšleno a to tak, že lisování a balení tvarůžků může probíhat v libovolném pořadí či dokonce paralelně. Vzhledem k této nejednoznačnosti jsme se rozhodli těm z vás, kteří úspěšně vyřešili správné zádání, udělovat 12 bodů a těm, kteří úspěšně vyřešili špatně pochopené zadání, 11 bodů.

Povězme si nejprve pár slov k řešení úlohy, kterou jsme měli původně na mysli. Označme T počet tvarůžků, N_l počet lisovacích strojů a N_b počet balících strojů. Dále nechť λ_i, 1≤ i≤ N_l a β_i, 1≤ i≤ N_b jsou rychlosti jednotlivých lisovacích a balících strojů. Jako l_k budeme označovat nejmenší čas, za který je možné vylisovat k tvarůžků. Ukážeme, že hodnoty l₁,… ,l_T lze spočítat v čase O(T log N_l). K tomu použijeme datovou strukturu zvanou halda, která je vysvětlena v následujícím odstavci.

Halda je datová struktura, která nám umožňuje hledat v zadané množině čísel nejmenší, přičemž můžeme do naší množiny čísla přidávat i odebírat. Časová složitost každé takové operace je O(log n), kde n je počet prvků v haldě. Jak je halda implementována? Halda je reprezentována vyváženým binárním stromem, ve kterém platí, že každý otec je menší než libovolný z jeho dvou synů. Tedy nejmenší prvek haldy je obsažen v kořeni binárního stromu. Nový prvek lze do haldy přidat například tak, že nejdříve vytvoříme nový list binárního stromu, a to tak, abychom neporušili jeho vyváženost. Pokud přidaný prvek je větší než jeho otec, je halda korektní. V opačném případě jej s otcem prohodíme. Pokud je menší než jeho nový otec, tak jej opět prohodíme, atd. Takto postupujeme po cestě ke kořeni, dokud v haldě nezačnou platit požadované nerovnosti. Naopak, když prvek odebereme, tak jej nahradíme prvkem z nějakého listu (opět takového, abychom neporušili vyváženost) a prohazováním na cestě z kořene nebo od kořene napravíme nerovnosti. Zřejmě každá taková operace vyžaduje čas úměrný hloubce stromu, tj. O(log n).

Nyní si popíšeme, jak lze hodnoty l₁,… ,l_T spočítat. Vytvoříme si haldu s N_l prvky s časy, kdy nejdříve daný stroj může vylisovat další (na začátku první) tvarůžek. Čas l₁ se zřejmě rovná času nejrychlejšího stroje, tedy času uvedeného v kořeni. Tento čas nyní z haldy odebereme a nahradíme ho v haldě časem, kdy by daný stroj mohl vylisovat druhý tvarůžek. Nyní čas v kořeni haldy je roven l₂. Čas z kořene haldy odebereme a nahradíme časem, kdy daný stroj vylisuje další tvarůžek atd. To vše snadno provedeme v čase O(T log N_l). Podobně můžeme v čase O(T log N_b) určit minimální časy b₁,… ,b_T nutné k zabalení tvarůžků.

Označme si nyní t₀ minimální čas, za který lze T tvarůžků jak vylisovat tak i zabalit. Zřejmě platí l_i+b_T-i+1≤ t₀ pro všechna i=1,… ,T, neboť v době, kdy se vylisuje i-tý tvarůžek, musí být ještě dost času na zabalení T-i+1 tvarůžků (T-i ještě nevylisovaných a toho, co se právě dolisoval). Na druhou stranu, pokud budou stroje lisovat a balit tvarůžky podle harmonogramu na základě něhož byly čísla l_i a b_i spočtena, všech T tvarůžků bude vylisováno a zabaleno v čase:

Tedy poté, co spočítáme čísla l_i a b_i, jediné co nám zbývá je určit nejmenší z nich, a to snadno zvládneme v čase O(T).

Celková časová složitost našeho algoritmu je O(N_l+N_b+T(log N_l+ log N_b)) a paměťová O(T+N_l+N_b). Poznamenejme, že opatrnější implementací výpočtu minima ze součtů l_i+b_T-i+1 lze paměťovou složitost snížit na O(N_l+N_b). Implementace výše uvedených myšlenek je vcelku přímočará. Za povšimnutí snad jen stojí reprezentace binárního stromu v poli, podobně jako např. v úloze 14-1-4. Binární strom je uložen v poli indexovaném od nuly. Na pozici s indexem 0 je kořen stromu a synové prvku na pozici s indexem k jsou na pozicích s indexy 2k+1 a 2k+2. Vzhledem k tomu, že vždy odstraňujeme z haldy jen její nejmenší prvek, program neobsahuje proceduru pro odstraňování libovolného prvku haldy.

Na závěr bych ještě rád napsal pár poznámek o řešení úlohy, kdy by nebylo potřeba balit jen vylisované tvarůžky (a tedy by bylo možné tvarůžek zabalit ještě před vylisováním). V takovém případě se úloha redukuje na výpočet čísel l_T a b_T, tj. nepotřebujeme určit všechna čísla l₁,… ,l_T a b₁,… ,b_T. Označme si nyní jako τ následující podíl:

Zřejmě l_T≥ τ. Výše uvedenou rovnost si snadno můžeme přepsat do následujícího tvaru:

Označme si nyní jako T₀ počet tvarůžků, které lze vylisovat za čas τ:

Z (1) ihned plyne, že T₀≥ T-l. Tedy τ nám umožňuje určit hodnotu l_T0 a nyní v čase O((T-T₀) log N_l)=O(N_l log N_l) můžeme pomocí výše uvedeného postupu s haldou spočítat hodnoty l_T0,… ,l_T. Analogicky lze v čase O(N_b log N_b) spočítat hodnotu b_T.

Program

Dan Kráľ

15-5-5 Haskell (Zadání)

Chceme, aby funkce Sum pracovala na principu

Sum x y = if y == 0 then x 
                    else Sum (x + 1) (y - 1)

Nicméně vzhledem k tomu, jak jsme si zadefinovali čísla, toto přesně dělá následující výraz:

Správnost dokážeme indukcí podle velikosti y:

• Pokud velikost y je nula, tj. y=Zero, dostáváme
  Sum x Zero = Zero x (Sum (Succ x)) = x.
• Pokud y = Succ y' a pro y' Sum funguje, dostáváme
  Sum x y = Succ y' x (Sum (Succ x)) =
  = Sum (Succ x) y',
  což je podle indukčního předpokladu rovno
  (x+1) + y' = x + y.

Nyní k druhé úloze: Stejně jako operátor pevného bodu simuluje rekurzi, operátory dvojitého pevného bodu odpovídají dvěma navzájem rekurzivním funkcím. Zadání si můžeme přepsat do tvaru a = g a b, b = h a b, kde a = Y₁ g h, b = Y₂ g h. Nyní z první rovnice můžeme pomocí Y vyjádřit a nerekurzivně, a = Y (λs  . g s b) a dosadit do druhé rovnice, b = h (Y (λs  . g s b)) b. Teď tedy máme rovnici pro b a opět si z ní b můžeme vyjádřit, b = Y (λt  . h (Y (λs  . g s t)) t). Použitím definice b pak dostáváme

Analogicky dostaneme

Zdeněk Dvořák