První série třicátého osmého ročníku KSP

Celý leták v PDF.

Komentáře k úlohám

Teoretická úloha38-1-3 Mediánový poddaný (Zadání) (Řešení)

Vzorové řešení této úlohy běží v čase O(K log Pmax). Řešitelé ale našli dvě různá rychlejší řešení, kterým stačí čas O(K log(NK)), což je pro K ≤ N totéž jako O(K log N). Obě řešení používají binární vyhledávání na intervalu od 0 do Pmax, stejně jako vzorové řešení, ale jiným způsobem volí „prostřední“ pracovitost, podle které se interval dělí na dva.

Cílem je tuto pracovitost zvolit tak, aby vždy existovala alespoň c-tina poddaných s menší i větší pracovitostí, pro nějakou konstantu c. V tom případě v každé iteraci odstraníme alespoň
1
c
ze zbývajících poddaných a po nejvýše logc (KN) iteracích nám v intervalu zbude jen jeden poddaný, což musí být ten mediánový. Řešitelé našli dva způsoby, jak toho docílit.

Randomizované řešení

První řešení využívá náhody a připomíná algoritmus QuickSelect. V každé iteraci náhodně vylosujeme jednoho ze zbývajících poddaných, každého se stejnou pravděpodobností, a pracovitost tohoto poddaného použijeme k rozdělení intervalu. Pokud bychom zbývající poddané seřadili a rozdělili na čtvrtiny, tak bychom měli 50% pravděpodobnost, že jsme vylosovali poddaného v jedné z prostředních dvou čtvrtin. V tom případě bude alespoň čtvrtina poddaných méně, respektive více pracovitých než on. Průměrně každé dvě iterace tedy zahodíme alespoň čtvrtinu poddaných a náš algoritmus najde medián po průměrně O(K log(NK)) vysláních posla.

Zbývá rozmyslet, jak náhodně vylosovat posla v O(K) vysláních. Nejprve posla pověříme tím, aby v každém kraji spočítal počet zbývajících poddaných, počty označíme z1, z2, … , zK. Poddané pak pomyslně očíslujeme, v prvním kraji od 1 do z1, v druhém od z1 + 1 do z1 + z2, a tak dále, vždy od nejméně po nejvíce pracovitého. Poté vygenerujeme náhodné číslo i mezi 1 a z1 + z2 + … + zK. Snadno spočítáme, do kterého kraje i-tý poddaný patří, a kolikátý nejméně pracovitý tam je. Posla pak pošleme do tohoto kraje, aby nám pracovitost tolikátého poddaného zjistil.

Deterministické řešení

V druhém řešení se budeme inspirovat algoritmem na nalezení mediánu v lineárním čase pomocí mediánu mediánů. Opět pošleme posla do všech krajů, aby nám spočítal počty zbývajících poddaných z1, z2, … , zK, ale tentokrát po něm budeme navíc chtít, aby nám našel mediánového poddaného v rámci každého kraje. Jejich pracovitosti označíme m1, m2, … , mK. Poté z těchto mediánů spočítáme vážený medián m, váhou bude počet obyvatel v kraji. Tento vážený medián si můžeme představit tak, že spočítáme medián multimnožiny, která obsahuje z1-krát m1, z2-krát m2, a tak dále. Interval rozdělíme podle tohoto mediánu mediánů.

Vážený medián m bude mít tu pěknou vlastnost, že alespoň polovina poddaných bude v kraji s mi ≤ m, a alespoň polovina bude v kraji s mi ≥ m. Zároveň v každém kraji s mi ≤ m bude z definice mediánu alespoň polovina poddaných mít pracovitost ≤ m. Tedy alespoň čtvrtina všech zbývajících poddaných bude mít pracovitost ≤ m, a obdobně alespoň čtvrtina bude mít pracovitost ≥ m. V každé iteraci tedy odstraníme čtvrtinu prvků a algoritmus najde medián po O(K log(NK)) vysláních posla.

Benjamin Swart