První série šestnáctého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 16-1-1: Telefonní seznam
- 16-1-2: Lokální minimum
- 16-1-3: Důl
- 16-1-4: Neruš mé trojúhelníky!
- 16-1-5: Pravděpodobnostní algoritmy
16-1-1 Telefonní seznam (Zadání)
Jak většina řešitelů správně poznala, tato úložka se dá řešit použitím haldy. Snadno si rozmyslíme, že když „přefiltrujeme“ zadanou posloupnost slov haldou velikosti k – tj. do haldy vložíme prvních k prvků a pak střídavě odebíráme minimum a přidáváme další prvky – je výsledná posloupnost setříděná. Přidání do haldy i odebrání z ní vyžaduje O(log k) porovnání a těchto operací provedeme O(n). Je ovšem nutné vzít v úvahu také to, že porovnání řetězců nelze provést v konstantním čase. V nejhorším případě se může stát, že se dva řetězce liší až na některé z posledních pozic, pak jejich porovnání zabere čas Θ(L), kde L je jejich délka. Výsledná časová složitost tohoto řešení je tedy O(n·L· log k). V paměti si stačí udržovat pouze haldu, prvky se načítají postupně a lze je rovnou vypisovat, tedy paměťová složitost je O(k·L).
Existují ovšem nejméně dvě řešení dosahující stejné nebo lepší časové složitosti:
Je možné prostě zapomenout na k a setřídit slova pomocí přihrádkového třídění. Toto řešení pracuje s časovou složitostí O((n+p)·L), kde p je počet písmen v abecedě, a paměťovou složitostí O(n·L).
Další řešení pracuje na podobném principu jako první řešení, nicméně vyhýbá se použití haldy. Funguje takto: z posloupnosti slov si vezmeme prvních 2k a setřídíme je, to vyžaduje O(k· log k) porovnání. k nejmenších z nich vypíšeme, zbytek přidáme na začátek posloupnosti a opakujeme. Pro důkaz správnosti je potřeba uvědomit si dvě věci:
- Vzhledem k tomu, že pozice každého prvku v posloupnosti se od své správné pozice v setříděné posloupnosti liší nejvýše o k, k nejmenších musí být mezi prvními 2k prvky posloupnosti, a tedy po setřídění tohoto úseku budou na správných pozicích.
- Přerovnáním zbývajících k prvků nepokazíme to, že prvky jsou ve vzdálenosti nejvýše k od správné pozice. Ukážeme to sporem. Nechť tedy takový „pokažený“ prvek existuje. Buď x největší takový. Pokud je jeho správná pozice (v původní nezkrácené posloupnosti) nejvýše 2k, nemohli jsme nic pokazit. Tedy tato pozice je nějaké q, q>2k. Označme t novou pozici slova x, víme že q - t > k. Jestliže t = 2k, je x vůbec největší z prvních 2k, a mohli jsme ho posunout pouze směrem ke q. Tedy t < 2k. Slovo y na pozici t + 1 je větší než x, jeho správná pozice je tedy alespoň q+1. Nicméně (q + 1) - (t + 1) > k a to je spor s tím, že x je největší s touto vlastností.
Časová složitost tohoto řešení je opět O(n·L· log k), protože tříděných úseků je O(n/k). Paměťová je O(k·L), protože si stačí pamatovat aktuálně tříděný úsek. Program implementuje toto řešení, protože se nejsnáze naprogramuje a já jsem líný.
16-1-2 Lokální minimum (Zadání)
Je podivu hodné, kolik lidí se upokojilo s triviálním algoritmem o lineární časové složitosti – i přes explicitní upozornění, že to jde lépe. Pravda, nechalo se najít pár vylepšení typu číst každý druhý prvek, používat pouze konstatní paměťovou složitost, leč k nalezení logaritmické složitosti (co asi tak může být mezi O(n) a nesmyslem O(1)?) je tato cesta neperspektivní. Jest lyže má něco logaritmickou složitost, obvykle se tam nějakým způsobem rovnoměrně rozdělují vstupní data – v tomto případě se bude půlit celý interval a po výběru správné poloviny se úloha bude rekurzivně řešit pouze uvnitř této.
V intervalu [x0… xn/2… xn+1] existuje Lokální Minimum (sporem). Vezmeme prostřední prvek. Pokud je LM, úloha je vyřešena. Jinak se LM nutně nalézá v polovině (či v obou), jejíž krajní prvek xn/2±1 je menší než xn/2.
Proč? Nechť bez újmy na obecnosti xn/2>xn/2+1. Pro spor předpokládejme, že v pravé polovině není LM. Proto nutně xn/2+1>xn/2+2 a stejným argumentem pokračuji až dostávám xn>xn+1, což je hledaný spor, neboť xn+1=∞.
Úlohu proto stačí rekurzivně spustit na vybranou polovinu.
I Plovací sval nahlédne, že to lze provést nejvýše logaritmus-krát, z čehož plyne i celková složitost algoritmu O(log n). Všechna čísla jsou uložena v poli, a tedy paměťová složitost je O(n).
16-1-3 Důl (Zadání)
Většina z vás správně rozpoznala, že tento příklad je jedním z oněch dvou, na které se má použít recept z naší programátorské kuchařky. Úlohu lze vcelku jednoduše vyřešit modifikovaným Dijkstrovým algoritmem, kde místo délky cesty uvažujeme nosnost nejhorší silnice, kterou cesta obsahuje.
Zmiňme tedy jen stručně rozdíly oproti algoritmu z naší kuchařky. Ohodnocení měst není tvořeno délkami nejkratších cest, ale maximálními nosnostmi dosud nalezených cest, kde nosnost cesty je minimum nosností všech silnic, které obsahuje. V každém kroku vybereme dočasně ohodnocené město M s největším ohodnocením, a jeho ohodnocení prohlásíme za trvalé. Poté zkusíme nalézt výhodnější cesty přes město M do zbylých (dočasně ohodnocených) měst. Poznamenejme, že nosnost cesty přes město M je minimum z nosnosti cesty do města M a silnice z města M do sousedního města. Důkaz správnosti se provede podobně jako důkaz správnosti původního Dijkstrova algoritmu.
Přímočará implementace právě popsaného algoritmu bez použití haldy má časovou složitost O(n2) a paměťovou složitost O(n+m), kde n je počet měst a m je počet silnic. Řešení bez použití haldy, lze nalézt ve vzorovém programu. Za pomoci haldy, lze dosáhnout časové složitosti O(m log n).
Existuje i alternativní řešení pomocí datové struktury zvané disjoint find union (DFU), kterou si podrobně popíšeme v některém z následujících dílů naší kuchařky. Datová struktura DFU nám umožňuje udržovat si rozklad množiny na disjunktní podmnožiny. Na začátku je množina rozložena na jednobodové podmnožiny a v průběhu práce s ní můžeme podmnožiny sjednocovat do větších. Tato datová struktura nám pak umožňuje odpovídat na dotazy, zda dva prvky jsou ve stejné podmnožině či nikoliv. Provedeme-li celkem K operací na n-prvkové množině, pak čas spotřebovaný touto datovou strukturou je nejvýše O((K+n)·α(n)), kde α(n) je inverzní funkce k tzv. Ackermannově funkci. Poznamenejme, že funkce α(n) roste s n velmi velmi pomalu a pro počet atomů ve vesmíru je tato tato funkce rovna 4.
Jak tedy takovéto řešení bude fungovat? Nejdříve si silnice setřídíme od té s největší nosností po tu s nejmenší. Následně budeme postupně povolovat silnice, které můžeme použít, tak dlouho dokud nebude existovat cesta z dolu do továrny jen po povolených silnicích. Silnice povolujeme od té s největší nosností. Na začátku není žádná silnice povolena. Množiny měst, mezi kterými existuje cesta jen po povolených silnicích, tvoří právě rozklad množiny všech měst, který udržujeme pomocí DFU. Právě popsané řešení má časovou složitost O(m log m)+O((m+n)·α(n))=O(m log n) a paměťovou složitost O(n+m).
16-1-4 Neruš mé trojúhelníky! (Zadání)
Představitele Bosstánu by jistě potěšilo, že se našlo tolik řešení jejich šifrovacího problému. Avšak ne všechna řešení byla dost rychlá, aby se dala používat. Spousta z vás řešila problém naprosto přímočarým způsobem, který ovšem beží v čase O(n3), a tedy velice pomalu už pro malé n. S malým pozorováním lze tento algoritmus vylepšit až na složitost O(n2). Algoritmus vlastně funguje stejně jako přímočaré řešení jen s tím rozdílem, že si pro každou dvojici bodů pamatujeme interval, ve kterém může ležet třetí bod (a výsledný trojúhelník přitom bude obsahovat střed) a ten pouze updatujeme. Avšak ani toto řešení, jak mnozí poznali, není nejlepší. Vzorové řešení pracuje v čase O(n log n) následujícím způsobem:
Nejprve si vstupní data, body udané úhly, setřídíme. Pak si problém převedeme na opačnou úlohu, tedy kolik trojúhelníku neobsahuje střed. Tato úloha se řeší velice jednoduše, přesněji v lineárním čase. Nejprve si určíme, kdy trojúhelník neobsahuje střed. To nastává právě tehdy, když jsou body trojúhelníka v intervalu dlouhém <180 stupňů, tedy jednodušeji, jsou pouze na jedné půlce kružnice. A tyto body se již určí velice jednoduše. Postupně volíme body na kružnici a pro ně určujeme nejvzdálenější bod po směru kružnice takový, že jejich úhlová vzdálenost je <180 stupňů. Protože konec intervalu pro bod y následující na kružnici po x stačí hledat za koncem intervalu pro bod x, celou kružnici objedeme maximálně 2-krát. Tedy algoritmus má lineární složitost. Zbývá snad už jen dodat, že je nutné si dát pozor na to, abychom započítali každý trojúhelník právě jednou.
Složitost třídění je O(n log n) a algoritmus na hledání počtu trojúhelníků neobsahujících střed má složitost O(n). Tedy celková časová složitost algoritmu je O(n log n) a paměťová složitost je O(n).
16-1-5 Pravděpodobnostní algoritmy (Zadání)
Jak se ukázalo (a jak ostatně napoví i pohled na výsledkovou listinu), generování náhodných čísel s rovnoměrným rozdělením pravděpodobností je problém trochu potvornější, než jak na první pohled vypadá. Nejdříve si ho proto vyřešme pro případ, kdy je N mocninou dvojky, tedy rovné nějakému 2k. Tehdy nám stačí k-krát si „hodit korunou“ (tj. zavolat funkci randbit) a výsledek si vyložit jako dvojkový zápis nějakého čísla mezi 0 a N-1:
int random2(int N)
{
int z = 0;
N--;
while (N)
{
z = 2*z + randbit();
N /= 2;
}
return z;
}
(všimněte si, že k ani nemusíme počítat, že stačí N-1 postupně dělit dvojkou tak dlouho, než vyjde 0).
Všechny výsledky jsou určitě stejně pravděpodobné, protože každé číslo je určeno právě jedním dvojkovým zápisem a pravděpodobnost každého dvojkového zápisu je (1/2)·(1/2)·… ·(1/2) = 2-k = 1/N.
Ale co když N nebude mocninou dvojky? Mohli bychom například zvolit nějaké N′> N, které mocninou dvojky bude (a takové určitě najdeme mezi N a 2N), vygenerovat x v rozsahu 0 až N′-1 a výsledek nějak „upravit“, aby byl vždy menší než N. Jak to ale přesně provést?
Pokus č. 1: Spočíst x mod N: to nebude fungovat, protože číslo 0 můžeme vygenerovat dvojím způsobem (pro x=0 i x=N), zatímco třeba číslo N-1 pouze jedním způsobem (x=N-1), a proto má 0 dvojnásobnou pravděpodobnost než N-1.
Pokus č. 2: Postupné generování dvojkového čísla po bitech si můžeme také vyložit jako hledání nějakého čísla v poli (0, 1, … , N-1) půlením intervalů, přičemž v každém kroku se nerozhodujeme podle nerovnosti s hledaným číslem, nýbrž náhodně. To je bezpochyby pro N=2k totéž, ale v ostatních případech musíme dříve nebo později narazit na interval, který se na dva stejně dlouhé rozdělit nedá. Ať už to ošetříme jakkoliv, opět dostaneme nestejné pravděpodobnosti vygenerovaných čísel.
A není náhodou, že se nám nedaří rovnoměrného rozdělení dosáhnout – ono to totiž na žádný konečný počet volání funkce randbit nelze. Poslyšte důkaz: Kdyby stačilo h hodů mincí, můžeme si program upravit tak, aby randbit volal vždy právě h-krát (počítali bychom si, kolikrát ho zavolal, a nakonec bychom doplnili příslušný počet volání, která by nijak neovlivnila výsledek programu). Program pak může probíhat 2h různými způsoby podle toho, jakou posloupnost náhodných bitů od funkce randbit dostal, přičemž všechny tyto průběhy jsou stejně pravděpodobné. Každé číslo x, které program může vygenerovat, pak odpovídá některým z těchto průběhů (může jich být více, protože lze dospět různými cestami k témuž výsledku) a označíme-li si počet takových průběhů cx, bude pravděpodobnost vygenerování čísla x rovna přesně cx/2h. Jenže pokud není N mocnina dvojky, nemůžeme žádanou pravděpodobnost 1/N vyjádřit jako cx/2h pro žádné cx. [Pokud je a/b = c/d, pak ad=bc, čili v našem případě 2h = N·cx. Jenže v rozkladu levé strany na součin prvočísel vystupují jen dvojky, v rozkladu pravé i jiná prvočísla.] Takže náš program opravdu nemůže fungovat.
Zkusme tedy na konečnost na chvíli zapomenout a navrhnout naprosto přímočaré řešení: Vygenerujeme náhodné číslo mezi 0 a N′-1. Pokud bude menší jak N, prohlásíme ho za výsledek, jinak ho zahodíme a generujeme znovu atd.:
int random(int N)
{
int x;
do
x = random2(N);
while (x >= N);
return x;
}
(zde zneužíváme toho, že výpočet k ve funkci random2 zaokrouhluje nahoru, takže místo do N-1 generujeme až do N′-1, jak potřebujeme).
Jelikož výsledky funkce random2 jsou, jak už víme, všechny stejně pravděpodobné a my si z nich pouze vybíráme a v případě, že si číslo nevybereme, zapomeneme veškerý dosavadní průběh výpočtu, musí být i výsledky naší nové funkce všechny stejně pravděpodobné.
Háček ovšem může být v tom, že nedokážeme předpovědět, kolik iterací bude naše funkce na vygenerování jednoho čísla potřebovat. Může se to povést už napoprvé, ale také se to nemusí povést vůbec – třeba tehdy, bude-li nám funkce randbit vracet stále samé jedničky. Nicméně pravděpodobnost toho, že se nám první číslo nebude hodit, je p=1-N/N′<1/2, pravděpodobnost toho, že ani to druhé ne, je p2 < 1/4, …, l neúspěšných pokusů nastane s pravděpodobností pl<2-l a nekonečná posloupnost neúspěchů má pravděpodobnost 0. [Což neznamená, že by nemohla nastat.]
Zkusme tedy spočítat, kolik pokusů budeme potřebovat v průměru. Nejprve si ale nadefinujme, co takový průměr přesně je: Mějme nějakou množinu náhodných jevů Ω={ω1, ω2, … }, přičemž jev ω∈Ω nastává s pravděpodobností p(ω). Pak pro každou funkci F, která přiřazuje těmto jevům nějaká reálná čísla, můžeme nadefinovat střední hodnotu ΕF takto:
Pokud mají všechny jevy stejnou pravděpodobnost, tedy ∀ω∈Ω: p(ω)=1/|Ω|, splývá tato definice s obyčejným (aritmetickým) průměrem všech funkčních hodnot; pokud ale jsou některé jevy pravděpodobnější, dáváme jim větší váhu, a tak průměr ovlivňují více.
Příklad 1: Pokud budeme házet kostkou a budeme chtít spočítat, kolik nám v průměru padne, bude naše množina Ω={1,2,3,4,5,6} a všechná p(ω) budou rovna 1/6. Pak si stačí zvolit funkci I(x)=x a spočítat její střední hodnotu:
| 6 |
| x=1 |
| 6 |
| x=1 |
| 1 |
| 6 |
| 1 |
| 6 |
| 6 |
| x=1 |
| 21 |
| 6 |
| 7 |
| 2 |
Příklad 2: Házíme dvěma kostkami a chceme spočíst průměrný součet. Množina Ω bude tentokrát zahrnovat všechny uspořádané dvojice (x,y), kde 1≤ x,y≤ 6, každá dvojice bude mít pravděpodobnost 1/36 a střední hodnotu budeme počítat z funkce S((x,y))=x+y [dvojích závorek se nelekejte, pouze vyjadřují, že parametrem funkce nejsou dvě čísla, nýbrž jedna uspořádaná dvojice čísel]. Mohli bychom počítat otrocky podle definice, ale raději si všimneme jedné zajímavé vlastnosti středních hodnot:
Odbočka: Střední hodnota je lineární, to znamená, že platí:
| Ε(F+G) | = ∑ω∈Ω (F+G)(ω)·p(ω) = |
| = ∑ω∈Ω (F(ω) + G(ω)) ·p(ω) = | |
| = (∑ω∈Ω F(ω) ·p(ω) ) + (∑ω∈Ω G(ω) ·p(ω) ) = | |
| = (ΕF) + (ΕG). |
a také (což se dokáže obdobně):
Intuitivně řečeno: Ε lze „přetáhnout“ jak přes +, tak přes násobení konstantou.
Také si všimněme, že střední hodnotu lze ekvivalentně definovat jako:
kde sčítáme přes všechna x z oboru hodnot funkce F a Prω[podmínka] značíme pravděpodobnost, že náhodně vybrané ω∈Ω splňuje podmínku, jinými slovy součet všech p(ω) vyhovujících prvků ω. Pokud je jasné, co je náhodná proměnná, místo Prω často píšeme jenom Pr. Stejně tak závorky okolo (ΕF) budeme vynechávat.
| 7 |
| 2 |
| 7 |
| 2 |
| 7 |
| 2 |
Zpět k analýze našeho algoritmu: Zkusme spočítat průměrný počet volání funkce random2 během výpočtu, čili střední hodnotu funkce R, která každému možnému průběhu výpočtu (tj. tomu, jaké jsme dostali náhodné bity – zbytek je již jednoznačně určen) přiřadí, kolikrát byla v tomto případě random2 zavolána. To můžeme elegantně spočítat třeba tak, že R vyjádříme jako součet funkcí R1, R2, … , kde Ri=1, pokud i-té volání nastalo, jinak Ri=0. Pak dostaneme:
| ∞ |
| i=1 |
| ∞ |
| i=1 |
Pravděpodobnost toho, že Ri=1, jsme již spočítali a je to pi-1 < 21-i, takže podle (*) dostaneme:
Z toho:
| ∞ |
| i=1 |
| ∞ |
| i=1 |
[to není nic jiného než součet nekonečné geometrické řady].
Spočítat z toho průměrnou časovou složitost našeho algoritmu je už hračka: nechť T(ω) značí časovou složitost výpočtu ω, čili O(R(ω)· log N). Pak
[Cvičeníčko: dokažte, že střední hodnotu lze „přetahovat přes O“.]
Takže i přesto, že náš algoritmus na první pohled vypadal velmi neefektivně, v průměrném případě běží jen logaritmicky dlouho (a tím pádem také funkci randbit volá jen logaritmicky-krát).
Jiný, možná elegantnější, způsob odvození hodnoty ΕR můžeme získat takto: Algoritmus v každém případě zavolá funkci random2 jednou a pokud získá moc velké číslo (to nastává s pravděpodobností p<1/2), dostane se opět na začátek a nic si z předchozího nepamatuje. Proto platí:
kterážto rovnice má řešení
[Cvičeníčko: chvíli přemítejte o tom, proč je tato úvaha opravdu korektní.]
Poznámka: Někteří řešitelé vymýšleli různé důmyslné (a někdy i korektní) způsoby, jak část náhodných bitů z neúspěšných pokusů „recyklovat“ v pokusech dalších. To samozřejmě lze, ale jediné, co tím dokážeme, je pro některá N zmenšit multiplikativní konstantu schovanou v O-čku, což nestojí za tu námahu. Kdybychom ovšem řešili obecnější úlohu a bylo naším cílem generovat n náhodných čísel namísto jednoho, začalo by se recyklování náhodnosti vyplácet a došli bychom (po úctyhodném množství počítání) k tomu, že čím větší je n, tím více se průměrný počet náhodných bitů blíží k n· log N (přesně, tedy bez O-čka!). To si ale třeba nechme na jindy, pro zvídavé napovím jen, že jeden ze způsobů, jak toho dosáhnout, je vzít populární kompresní algoritmus řečený aritmetické kódování, inicializovat mu pravděpodobnosti všech znaků na 1/N a poté nechat dekomprimovat posloupnost náhodných bitů.
Ještě jedna poznámka: V mnohých řešeních se vyskytlo počítání dvojkových logaritmů pomocí vzorců typu
To by bylo správně, nebýt jednoho zádrhele: počítač nepočítá s opravdovými reálnými čísly, nýbrž pouze s jejich aproximacemi. Proto všechny výpočty v typech jako je real, float apod. jsou zatíženy chybami, které i po zaokrouhlení mohou být podstatné. Často se samozřejmě dá dokázat, že v daném případě je výsledek správný, ale nebývá to jednoduché, takže pokud se chcete takovým problémům vyhnout, je praktické při počítání s celými čísly používat jen celočíselné operace.
Tak, to už je pravděpodobně všechno.