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

Vzorová řešení


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 = a1 + a2 + … + an (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 n2 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 a2. Táhneme a2 a dostaneme:

a1+a2, -a2, a2+a3, a4, … , an.

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

a1+a2, a3, -a2-a3, a2+a3+a4, … , an.

Když dojdeme na konec posloupnosti (to nastane pokud -a2 > a3+a4+… +an), bude situace takováto:

a1+2·a2+a3+… +an, a3, a4,… , an, -a2-… -an,

což můžeme přepsat jako:

s+a2, a3,… , an, a1-s.

Protože -a2 > a3+… +an = s-a1-a2, tak a1-s > 0. t se snížilo o s, protože na prvním místě je s+a2 a a1-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 -a2 < a3+… +ai. Situace bude následující:

a1+a2, a3, … , ai-1, -a2-… -ai-1, a2+… +ai, … , an.

Nechť u = a1+...+ai-1. Výraz pak bude:

a1+a2, a3,… , ai-1, a1 - u, u+ai-a1, ai+1,… , an.

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

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

Problém nastane, pokud a1 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(n2·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).

Některá řešení počítala pouze počet cest do opravovaných a cílové křižovatky: Nejprve spočítala počet cest se zanedbáním předchozích opravovaných křižovatek jako kombinační číslo
(i+j)
i
, kde i,j je číslo řádky, sloupce. Správnost plyne z toho, že Bill vybírá ii+j křižovatek, kudy pojede na jih. Pro každou předcházející rozkopanou křižovatku pak od tohoto čísla odečteme součin počtu dobrých cest, které do ní vedou (ty jsme počítali v předcházejících krocích) a počtu všech cest z ní do zkoumané křižovatky (zase kombinační číslo). Tím je zaručeno, že každá špatná cesta se započítá jen pro první opravovanou křižovatku, přes kterou vede. Pak dosáhli paměťové složitosti O(k) a časové O(k2·(m+n)), případně, pokud si předpočítali faktoriály, paměťové O(k+n+m) a časové O(k2+m+n), což se mi zdálo méně výhodné než předchozí řešení.

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ů, Nl počet lisovacích strojů a Nb počet balících strojů. Dále nechť λi, 1≤ i≤ Nl a βi, 1≤ i≤ Nb jsou rychlosti jednotlivých lisovacích a balících strojů. Jako lk budeme označovat nejmenší čas, za který je možné vylisovat k tvarůžků. Ukážeme, že hodnoty l1,… ,lT lze spočítat v čase O(T log Nl). 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 l1,… ,lT spočítat. Vytvoříme si haldu s Nl prvky s časy, kdy nejdříve daný stroj může vylisovat další (na začátku první) tvarůžek. Čas l1 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 l2. Č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 Nl). Podobně můžeme v čase O(T log Nb) určit minimální časy b1,… ,bT nutné k zabalení tvarůžků.

Označme si nyní t0 minimální čas, za který lze T tvarůžků jak vylisovat tak i zabalit. Zřejmě platí li+bT-i+1≤ t0 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 li a bi spočtena, všech T tvarůžků bude vylisováno a zabaleno v čase:

mini=1,… ,T li+bT-i+1.

Tedy poté, co spočítáme čísla li a bi, 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(Nl+Nb+T(log Nl+ log Nb)) a paměťová O(T+Nl+Nb). Poznamenejme, že opatrnější implementací výpočtu minima ze součtů li+bT-i+1 lze paměťovou složitost snížit na O(Nl+Nb). 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 lT a bT, tj. nepotřebujeme určit všechna čísla l1,… ,lT a b1,… ,bT. Označme si nyní jako τ následující podíl:

τ=
T
1/λ1+1/λ2+… +1/λl

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

T=
τ
λ1
+
τ
λ2
+… +
τ
λl
.
(1)

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

T0=
τ
λ1
+
τ
λ2
+… +
τ
λl
.

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

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:

Sum = λx  . λy  . y x (Sum (Succ x))

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 = Y1 g h, b = Y2 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

Y2 = λg  . λh  . Y (λt  . h (Y (λs  . g s t)) t).

Analogicky dostaneme

Y1 = λg  . λh  . Y (λt  . g t (Y (λs  . h t s))).

Zdeněk Dvořák