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

Celý leták v PDF.

Dostává se k vám první číslo hlavní kategorie 38. ročníku KSP.

Letos se můžete těšit v každé z pěti sérií hlavní kategorie na 4 normální úlohy, z toho alespoň jednu praktickou opendatovou. Dále na kuchařky obsahující nějaká zajímavá informatická témata, hodící se k úlohám dané série. Občas se nám také objeví bonusová X-ková úloha, za kterou lze získat X-kové body. Kromě toho bude součástí sérií seriál, jehož díly mohou vycházet samostatně.

Autorská řešení úloh budeme vystavovat hned po skončení série. Pokud nás pak při opravování napadnou nějaké komentáře k řešením od vás, zveřejníme je dodatečně.

Odměny & na Matfyz bez přijímaček

• Termín série: neděle 2. listopadu 2025 ve 32:00 (tedy další ráno v 8:00)
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

• Odměna série: Odznáček do profilu na webu si vyslouží ten, kdo z každé úlohy série získá alespoň 2 body.

Zadání úloh

• 38-1-1: One-shot burza
• 38-1-2: Bambulus
• 38-1-3: Mediánový poddaný
• 38-1-4: Jedno slovo
• 38-1-S: Hoďte si kostkou

38-1-1 One-shot burza (11 bodů)

Trpaslík Plesnivous se rozhodl, že drakův poklad je pro něj moc práce a musí si vydělat jinak. Jenže vydělávat standardní cestou je zaprvé náročné, zadruhé neefektivní a zatřetí nic pro něj. Proto se rozhodl jít za Lady Hrochtenzií – místním orákulem. Ta mu sdělila cenu uhlí pro každý z příštích N dní.

Bohužel si ale důlní úřad kontroluje velké finančně-uhelné transakce, proto smí Plesnivous za svých K sesterciů pouze jednou nakoupit libovolné kladné celé množství uhlí a jednou ho všechno prodat. Chce při tom postupovat se značnou obezřetností, aby si vydělal co nejvyšší sumu. Pomozte Plesnivousovi zjistit, kdy má uhlí nakoupit a kdy prodat, aby skončil s co nejvíce sestercii.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Na prvním řádku dostanete N, počet dní, na které Lady Hrochtenzie předpověděla ceny uhlí, a K, Plesnivousův kapitál v sesterciích. Na druhém řádku dostanete N kladných celých čísel reprezentující ceny uhlí v daných dnech.

Formát výstupu: Na jednom řádku vypište dvě čísla – den, ve který má Plesnivous uhlí nakoupit a kdy prodat. Dny indexujeme jako správní trpaslíci od nuly. Pokud je takových řešení více, vypište libovolné z nich. Pokud Plesnivous na uhlí nemůže nic vydělat, nebo by dokonce prodělal, vypište namísto toho -1. Pozor, Plesnivousův výdělek se nemusí vejít do 32-bitového čísla.

8 6
3 7 2 4 9 1 5 4

5 6

Když by Plesnivous nakoupil v den 5, nakupoval by uhlí za 1 sestercius, tedy by jich mohl koupit 6. 6 uhlí potom v den 6 prodá každé za 5 sestercií, čímž získá peněžní obnos v hodnotě 6·5=30 sestercií. Vydělal tedy 30-6=24 sestercií, což je pro daný vstup maximální.

38-1-2 Bambulus (12 bodů)

Matúšovi se konečně podařilo rozjet jeho kariéru motivačního řečníka. O jeho sérii přednášek „Bambulus: tři pilíře životního štěstí?“ je nebývalý zájem a nezřídka bývají představení vyprodaná. Nově nabytá sláva s sebou však nese jistá úskalí: Matúšovi obdivovatelé se nemůžou shodnout na tom, který z pilířů jeho učení je nejdůležitější, a rozdělili se na tři navzájem rozhádané tábory. Jedni věří, že klíčem ke všemu je ladění (harmonie se sebou i okolím), druzí vidí hlavní smysl v řádění (následování svého vnitřního dítěte a žití v okamžiku), třetí nedají dopustit na parádění (hledání vnitřní i vnější krásy ve všedních věcech).

Tyto rozbroje jsou problém pro Matúšova vystoupení, jelikož příslušníci rozhádaných táborů si odmítají sednout vedle sebe. Po minulém představení, kde kvůli tomu zůstala půlka míst volná, už Matúšovi došla trpělivost. Přicházející diváci prostě dostanou nějaké místo přidělené, a basta. Jenže jak, aby byli pořád všichni spokojení, ale přitom volných míst zbylo co nejméně? Matúš je zaneprázdněn googlením motivačních citátů, a tak tento úkol připadl na vás.

Hlediště je tvořené N židlemi umístěnými v jedné řadě. Na začátku je hlediště prázdné a pak do něj po jednom přicházejí diváci. Vaším cílem je navrhnout algoritmus, který dostává události tvaru „právě přišel divák vyznávající 1./2./3. pilíř“ a na každou z nich odpovídá místem, na které si daný divák má sednout. Chceme přitom, aby vedle sebe nikdy neseděli dva diváci vyznávající různé pilíře.

Váš algoritmus je online: diváci přicházejí jeden po druhém, a nový divák přijde až potom, co umístíme předchozího. Již usazené diváky nejde přemisťovat.

Kvalitu vašeho řešení budeme hodnotit podle ztráty – množství volných míst, které zbývají v okamžiku, kdy už nejde umístit dalšího diváka. Stejně jako u časové složitosti nás zde nezajímá konkrétní číslo, ale pouze asymptotické chování: zdali je volných míst Θ(N), Θ(√N), nebo nějaká jiná funkce v N. Počet volných míst vyhodnocujeme na nejhorším možném vstupu. Můžete si představit, že před vchodem stojí Ríša, který Matúšovi nepřeje úspěch, a který dovnitř pouští diváky v takovém pořadí, aby váš algoritmus selhal co nejdříve. Ríša zná zdrojový kód vašeho algoritmu a má opravdu hodně času na vymýšlení co nejzapeklitějšího vstupu.

Příklad: Uvažme algoritmus, který každého přicházejícího diváka umístí na co nejlevější použitelné místo. Takový algoritmus nechá až N/2 míst volných, a to v situaci, kdy se nám přicházejí střídavě vyznavači 1. a 2. pilíře – pak budou na sudých místech sedět diváci a lichá místa budou prázdná. Naopak si jde rozmyslet, že více než N/2 volných míst nikdy nezůstane. Ztráta tohoto algoritmu je tedy Θ(N).

Cílíme na algoritmus, který v nejhorším případě ponechá Θ(log N) míst volných, ale částečné body získáte i za asymptoticky horší závislost na N (třeba Θ(√N)). Ve vašem řešení nezapomeňte zdůvodnit, proč je jeho ztráta zrovna taková, jaká tvrdíte.

Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.

38-1-3 Mediánový poddaný (14 bodů)

Za sedmero horami a sedmero řekami vládl moudrý král Ríša. Ten si udržoval svoje rádce, kteří mu každoročně počítali a plánovali chod království. Nicméně aby rádci mohli připravit své plány, potřebovali by sehnat reprezentativního poddaného…

Ríšovo království je rozděleno na K krajů. Protože Ríša má rád pravidelnost, v každém kraji je právě N poddaných, kde každý poddaný má unikátní celočíselnou pracovitost P_i (1 ≤ P_i ≤ P_max). Rádci by chtěli sehnat poddaného, pro něhož se počty poddaných s vyšší pracovitostí a s nižší liší nejvýš o 1. Tedy poddaného, který je mediánem všech poddaných v celém království.

Nicméně Ríšovo království je velmi velké a rozlehlé, takže se záznamy o pracovitosti poddaných udržují pouze v krajích, kde žijí. Ríša ale může vyslat svého věrného posla s konstantně (Konstantně dlouhá zpráva smí obsahovat jen konstantně mnoho „rozumně velkých“ čísel – čísel velkých nejvýše polynomiálně k číslům na vstupu. Délka zprávy v bitech tedy musí být v O(log K + log N + log P_max).) dlouhým rozkazem do jednoho z krajů. Tam může zkonzultovat archivy a vrátit se s konstantně dlouhým výsledkem. Mezi vysláním posla a jeho návratem uplyne vždy jeden týden. Na základě všech předchozích výsledků může poté Ríša posla vyslat do dalšího kraje.

Například můžeme poslat posla:

• Zjistit nejmenší pracovitost v daném kraji.
• Zjistit počet poddaných s pracovitostmi mezi A a B.

Ale nemůžeme:

• Vyslat ho se seznamem největších pracovitostí v každém kraji, neboť rozkaz je dlouhý Θ(K).
• Nechat si poslat seznam N/2 nejméně pracovitých poddanných v kraji, neboť výsledek je dlouhý Θ(N).

Pomozte Ríšovi zjistit medián pracovitosti. Vaše řešení budou hodnocena primárně podle celkového počtu vyslání Ríšova věrného posla. Při návrhu algoritmu předpokládejte, že K je řádově menší než N, a to je řádově menší než P_max.

Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.

38-1-4 Jedno slovo (8 bodů)

Kevinovi přišla s novou sérií od orgů KSP i nějaká podivně vypadající zpráva… a kdyby jen jedna!

Všiml si, že každý vstup obsahuje na prvním řádku číslo vstupu, zbytku ale nerozumí a potřebuje vaši pomoc.

Nalezněte řešení.

Rada: pokud jste ještě nikdy neluštili šifry, může se vám hodit přečíst si třeba začátek tohoto návodu, po část „Kódování znaků“. Nehledejte však v řešení veliké složitosti, orgové KSP jsou především informatici a spíš než vlajková abeceda je zajímají způsoby kódování, které s informatikou přirozeně souvisejí.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

38-1-S Hoďte si kostkou (15 bodů)

V letošním seriálu se spolu vydáme do říše pravděpodobnostních algoritmů. To jsou takové, které si během výpočtu „hází kostkou“ – tedy generují nějaká náhodná čísla. To dokáže být překvapivě užitečné. Často jsou takové algoritmy daleko jednodušší, nebo dokonce rychlejší (aspoň v průměru) než jejich determinističtí (nenáhodní) příbuzní.

Abychom uměli o náhodě uvažovat, bude se nám hodit matematická teorie pravděpodobnosti. O té už v KSPčku máme kuchařku. Před řešením úloh si ji prosím přečtěte.

Dnešní díl seriálu se bude týkat generování náhody. Budeme používat:

• Poctivé mince – ty generují náhodný bit 0 nebo 1 tak, že obě možnosti mají stejnou pravděpodobnost 1/2.
• Obecné mince – ty generují 1 s nějakou obecnou pravděpodobností p a 0 s pravděpodobností 1-p.
• Poctivé k-stěnné kostky – na nich padají čísla od 0 do k-1, všechna se stejnou pravděpodobností 1/k. Poctivá mince je tedy ekvivalentní s poctivou 2-stěnnou kostkou. Na konkrétním rozsahu hodnot samozřejmě nezáleží, stejně dobře si můžeme pořídit kostku třeba s čísly 1 až k nebo 5 až k+4.
• Obecné k-stěnné kostky – jednotlivá čísla mají pravděpodobnosti p₀, p₁, …, p_k-1, přičemž p₀ + … + p_k-1 = 1.

Stačí ovšem mít k dispozici libovolnou kostku nebo minci, a hned umíme simulovat všechny ostatní. Nejdřív dokážeme, že pomocí poctivé mince dokážeme simulovat poctivou k-stěnnou kostku pro libovolné k≥ 2. Simulací myslíme algoritmus, který bude mít k dispozici funkci na hod mincí a jeho výstupem bude hod kostkou.

Kdyby počet stěn k byl mocnina dvojky 2^b pro nějaké b > 0, stačilo by b-krát hodit mincí a získané bity přečíst jako číslo ve dvojkové soustavě. Takto budou mít všechna čísla od 0 do k-1 stejnou pravděpodobnost 1/2^b = 1/k. (Například pro k=8 bude b=3, hodíme mincemi 101 a výsledek bude 5.)

Pokud k není mocnina dvojky, najdeme si nejbližší mocniny dvojky, tedy 2^b-1 < k < 2^b. Pak stejně jako předtím b-krát hodíme mincí, a tím získáme rovnoměrně náhodné číslo x od 0 do 2^b-1 (rovnoměrně náhodné znamená, že všechny možnosti jsou stejně pravděpodobné).

Je-li x<k, máme vyhráno a oznámíme výsledek x. V případě x≥ k se nabízí oznámit x mod k, ale pozor, to není rovnoměrné: například pro k=5 je b=3 a výsledek 0 oznámíme jak pro hody 000 (x=0), tak pro 101 (x=5). Výsledek 0 má tedy pravděpodobnost 2/8 = 1/4 místo požadované 1/5.

Lepší je v případě x≥ k prostě na všechno zapomenout a házet znovu. Když i napodruhé bude x≥ k, zkusíme to potřetí atd. Tím zajistíme rovnoměrnou náhodnost, ale v nejhorším případě selže každý pokus a algoritmus se nikdy nezastaví. Dokážeme ovšem, že průměrný počet hodů mincí (a tím i průměrná časová složitost) jsou konečné.

Spočítejme pravděpodobnost, že se pokus podaří (tedy bude x < k). To nastane v k případech z 2^b, takže pravděpodobnost úspěchu bude p = k / 2^b. Jelikož k > 2^b-1 = 2^b / 2, bude p > 1/2. Podle lemmatu o džbánu z naší kuchařky vychází střední hodnota počtu pokusů do prvního úspěšného 1 / p < 2. Každý pokus spotřebuje b hodů mincí, takže náš algoritmus potřebuje v průměru (ve střední hodnotě) méně než 2b hodů mincí. To je nejvýše 2 log₂ k + 2, jelikož b ≤ log₂ k + 1. Pokud nám stačí asymptotický odhad, je to prostě O(log k) hodů v průměru.

To je poměrně typická situace: náš pravděpodobnostní algoritmus je v průměru rychlý, ale v nejhorším případě velmi pomalý – máme-li smůlu, dokonce se nemusí zastavit. Podobně Quicksort s náhodnou volbou pivota, zmiňovaný v kuchařce, má průměrnou složitost O(n log n), ale v nejhorším případě kvadratickou.

Úkol 1 [4b]

Ukažte, jak pomocí poctivé k-stěnné kostky simulovat poctivou ℓ-stěnnou.

Úkol 2 [3b]

Ukažte, jak pomocí obecné mince simulovat poctivou. Pravděpodobnost jedničky na obecné minci ovšem neznáte.

Úkol 3 [4b]

Ukažte, jak pomocí poctivé mince simulovat obecnou. Pravděpodobnost p jedničky na obecné minci dostanete na vstupu. Je to nějaké reálné číslo mezi 0 a 1. Můžete předpokládat, že váš počítač umí provádět aritmetické operace s reálnými čísly v konstantním čase.

Úkol 4 [4b]

Dokažte, že neexistuje algoritmus, který by pomocí poctivé mince simuloval poctivou 3-stěnnou kostku, a měl konečnou časovou složitost v nejhorším případě.

Vaše řešení úkolů 1–3 by mělo obsahovat algoritmus, důkaz správnosti (tedy že všechny možné výsledky mají požadované pravděpodobnosti) a výpočet složitosti v nejhorším případě a v průměru.