Druhá série devátého ročníku KSP

Vzorová řešení


9-2-2 Tiskařský šotek (Zadání)


Mnozí z vás úlohu pojali jakožto "jednorázovou" – to jest jedno načtení dat a pak jeden dotaz a tvrdili, že jejich (naprosto triviální) řešení má časovou složitost přímo úměrnou délce slovníku a že to lépe nejde, poněvadž slovník musí alespoň jednou celý přečíst. Ostatní si naštěstí uvědomili, že takto by byla úloha "o ničem" a vyložili si ji tím správným způsobem: jednou analýza dat a poté mnoho dotazů, přičemž záleží na časové složitosti vyhodnocení jednoho dotazu.

Předem se omlouvám všem zůčastněným za poněkud nemírné využívání symbolu O(f) v celém následujícím textu. Pro bližší poučení o tom, co to vlastně znamená, viz nedávné komentáře o časové složitosti. Bez této symboliky by však byly úvahy níže ještě nepřehlednější.

Asi bude nejlepší nejprve zjistit, kolik vlastně může existovat modifikací daného slova délky w (v celém dalším textu předpokládáme, že celý slovník obsahuje slova mající v průměru tuto délku – usnadní to odhady časové složitosti a na obecnosti to neubírá). Tedy existuje w·(a-1) možností, jak písmeno změnit (a je velikost abecedy), w možností, jak písmeno ubrat, a konečně (w+1)·a možností, jak nějaké přidat (pozn.: nikdo netvrdí, že všechny tyto možnosti dají různé výsledky – existují případy, kdy ne, ale nás zajímá případ průměrný, v němž opravdu budou různé – dumejte podrobněji). Tedy celkem O(w·a) variant, každá délky O(w).

Porovnávat všechny varianty zadaného slova se všemi slovy ve slovníku nejspíše není rozumné – porovnání dvou slov trvá O(w), pro celý slovník tedy O(w·N) (N je počet slov), přičemž těchto porovnání potřebujeme provést O(w·a). Dostaneme tedy výslednou časovou složitost O(w2·a ·N), což asi nebude to pravé.

O něco lepší by bylo rozdělit si slovník na několik menších podle délek slov a porovnávat pouze s těmi slovy, která mají danou délku. Tedy O(N/w) porovnání celkem O(w·a·N). Sice lepší, ale stále ještě nic moc.

Bystrý řešitel si ovšem na tomto místě řekne: "To nápadně připomíná hashování!" A má pravdu… Proč jej tedy nezkusit? Nerozdělíme si slovník do O(w) příhrádek podle délek slov, ale rovnou na N částí – sestrojíme nějakou funkci f, jež každému slovu přiřadí nějaké přirozené číslo od 0 do N-1, a podle těchto hodnot slova roztřídíme. Takto bude v každé příhrádce průměrně jedno slovo a jestliže budou hodnoty funkce f rozděleny dostatečně rovnoměrně, dokonce tam bude typicky jedno nebo dvě slova.

Jestliže tedy chceme hledat nějaké slovo, spočteme si pro něj hodnotu funkce f (řekněme, že najdeme takovou, která bude spočtena v čase O(w) – jednu najdete ve vzorovém programu) a budeme hledat jenom v příslušné příhrádce, ve které bude průměrně O(1) slov. Každé porovnání slova s hledaným nás stojí O(w), takže celkem slovo nalezneme v čase O(w)+O(1)·O(w) = O(w). Celkem zkoušíme O(w·a) variant, což nám tedy trvá O(w2·a). Lépe to jistě nejde, poněvadž v lepším čase bychom nemuseli zvládnout ani všechna řešení vypsat (každá z variant může být řešením délky O(w)). Všimněte si, že časová složitost hledání (počítaná samozřejmě od začátku do konce pro průměrný případ) vůbec nezávisí na N.

Vzorový program pro každou příhrádku uchovává spojový seznam slov v příhrádce se nacházejících. Zbytek by již měl být zřejmý.

Program

Martin Mareš


9-2-1 Psí funkce (Zadání)


Čísla Ψ(n) jsou značně velká už pro malá n, proto rozhodně není možné řešit úlohu tak, že spočítáme hodnotu Ψ(n) a vydělíme ji třinácti. Uděláme proto něco jiného – ukážeme, že pro n>3 je Ψ(n) mod 13 = 3. Program tedy bude zcela triviální.

Nejprve ukážeme, že zbytek mocniny dvou po dělení třinácti záleží jen na zbytku exponentu po dělení dvanácti. Platí totiž 212 = 13·315 + 1, tudíž podle binomické věty platí

(212)m = (13·315 + 1)m = (13·315)m +
+
(m)
1
(13·315)m-1 + …+
+
(m)
m-1
(13·315)1 + 1 =
= 13·k + 1

(k je přirozené číslo); proto je 212·m+a = (212)m·2a = 13·k·2a + 2a. Právě jsme dokázali, že 212·m+a mod 13 = 2a mod 13. Pro zjištění Ψ(n) mod 13 proto stačí zjistit Ψ(n-1) mod 12.

Pro n>3 lze Ψ(n-1) psát ve tvaru 22k=4k, kde k>0 je přirozené číslo (Ψ(n-2) je totiž sudé). Takže (opět binomická věta):

Ψ(n-1) = 4k = (3+1)k = 3k +
(k)
1
3k-1 + …+ 1.

Zbytek Ψ(n-1) po dělení dvanácti je tedy jedno z čísel 1, 4, 7, 10. Pokud je totiž Ψ(n-1) = 12·a + b, je (podle předminulé věty)

1 = Ψ(n-1) mod 3 = (3·(4·a) + b) mod 3 = b mod 3.

Ovšem pro n > 3 je Ψ(n) dělitelné čtyřmi, proto je Ψ(n-1) mod 12 = 4.

Z toho, co jsme zjistili v předchozích dvou odstavcích, již přímo plyne, že pro n>3 je Ψ(n) mod 13 = 24 mod 13 = 3, což jsme chtěli dokázat.

Ti z vás, kteří za úlohu dostali (skoro) plný počet bodů, většinou postupovali podobně, jako právě skončené řešení. Častá chyba byla takováto: napíšu si tabulku čísel 2n mod 13, zjistím že 212 mod 13 = 20 mod 13, 213 mod 13 = 21 mod 13. Prohlásím, že je zřejmé, že se zbytky opakují s periodou dvanáct. Podobně "zjistím", že čísla 2n mod 12 se (pro n>2) opakují s periodou dva. Protože Ψ(n-2) je sudé, znám zbytek Ψ(n-1) = 2Ψ(n-2) po dělení dvanácti a tudíž i zbytek Ψ(n) = 2Ψ(n-1) po dělení třinácti. V čem že je ta chyba? Pokud zkoumáme nějakou posloupnost čísel, je často vhodné napsat si tabulku prvních několik členů a hledat v ní nějaké zákonitosti. Proti tomu rozhodně nic nenamítám. Nicméně to, že nějaká zákonitost platí pro prvních několik (lhostejno zda 10, 100 nebo 1010) členů, nedává žádnou záruku, že platí pro všechny členy. (Například číslo 22n + 1 je prvočíslo pro n < 5, ne však pro n větší.) Abychom dokázali něco pro všechny členy posloupnosti, je třeba buď vymyslet nějaký důkaz (na vytvořené tabulce nezávislý), anebo zdůvodnit, proč by měla tabulka pro velká n vypadat stejně — v našem případě stačilo konstatovat, že (2·a) mod m = 2·(a mod m) mod m a tedy každý řadek v tabulce zbytků závisí jen na předchozím řadku. Pokud je tedy k-tý řadek stejný jako l-tý, musí být i (k+1)-ní stejný jako (l+1)-ní, atd. Přidáním této úvahy se z výše uvedeného chybného řešení stane řešení správné.

Robert Šámal


9-2-3 Překla-datel (Zadání)


Takže co s ufounskými daty? Podle mne byla úloha docela jednoduchá, ale… Sešla se spousta řešení, povětšinou pomalých (384 kroků), některá dokonce opravdu pomalá (512 kroků). Objevily se též nějaké nápady, jak pomocí různých triků zrychlit výpočet dvakrát, ale to stále ještě není ono.

Nejlepší (nám známé) řešení má 33 kroků. Využívá zřejmého faktu, že otočit 2n-bitové číslo je totéž jako navzájem prohodit obě jeho n-bitové poloviny a pak každou z nich otočit zvlášť. Nejprve tedy prohodíme 2 64-bitové bloky, pak vždy 2 sousední 32-bitové (uvědomte si, že to je možno učinit najednou pro obě dvojice bloků! – viz text programu), …, v posledním kroku pak sousední dvojice bitů. Pro prohazování sousedních bloků dané velikosti potřebujeme 5 instrukcí, v prvním prohazování se dají dvě z těchto instrukcí ušetřit.

a = x < 64
b = x > 64
x = a | b
 
a = x < 32
b = x > 32
a = a & 0xFFFFFFFF00000000FFFFFFFF00000000
b = b & 0x00000000FFFFFFFF00000000FFFFFFFF
x = a | b 
 
a = x < 16
b = x > 16
a = a & 0xFFFF0000FFFF0000FFFF0000FFFF0000
b = b & 0x0000FFFF0000FFFF0000FFFF0000FFFF
x = a | b 
 
a = x < 8
b = x > 8
a = a & 0xFF00FF00FF00FF00FF00FF00FF00FF00
b = b & 0x00FF00FF00FF00FF00FF00FF00FF00FF
x = a | b 
 
a = x < 4
b = x > 4
a = a & 0xF0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0
b = b & 0x0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F
x = a | b 
 
a = x < 2
b = x > 2
a = a & 0xCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
b = b & 0x33333333333333333333333333333333
x = a | b 
 
a = x < 1
b = x > 1
a = a & 0xAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
b = b & 0x55555555555555555555555555555555
y = a | b

Pavel Machek


9-2-4 Nesčetní námětové (Zadání)


Došlá řešení byla velice různorodá. Základní potíž spočívala v tom, že nebylo zcela jasné, zda se veškerá data mají šanci vejít do paměti a zda jsou náměty číslovány postupně či "děravě". Z toho pak vznikaly následující varianty úlohy (korektní řešení libovolné varianty bylo hodnoceno plným počtem bodů):

  • Náměty jsou číslovány postupně: stačí jednoduché pole počítadel a zbytek je, doufejme, zcela jasný.
  • Náměty nejsou číslovány postupně:
    • Data se nevejdou do paměti: nutno použít stromy nebo hashování a tak si zorganizovat počítadla pro jednotlivé náměty i přes jejich roztroušenost.
    • Data se vejdou do paměti: toto je pravděpodobně jediná kombinace, u které vznikne opravdu zajímavá situace. Problém se redukuje na úlohu typu "máte pole a najděte v něm hodnotu, která se vyskytuje nejvícekrát."

Naše vzorové řešení se bude zabývat třetí variantou úlohy a bude jakousi variací na věčně omílané téma "QuickSort".

Vybereme si v poli libovolnou hodnotu z (pokud možno někde "uprostřed" pokrytého rozsahu hodnot, ale to se nedá snadno zaručit) a rozdělíme všechny prvky pole na dvě části: v jedné (tu soustředíme v oblasti s indexy 1,…, k) budou prvky xi ≤ z, ve druhé (s indexy k+1, …, N) pak prvky zbylé (xj > z). Jesliže je libovolná část menší než N/2, hledané číslo v ní zaručeně nemůže být. Takto nám zbyde buďto jedna nebo dokonce žádná (v případě 2·z=N) část ono číslo obsahující a tu můžeme zpracovat identickým způsobem, dokud nezjistíme, že obsahuje jen jediné číslo, což je číslo hledané.

Číslo z budeme určovat v jakémsi "předprůchodu" jako aritmetický průměr všech xi a při tom ještě budeme testovat, obsahuje-li pole více než jednu hodnotu. (Samozřejmě by to šlo dělat i jinak – například prostým vybráním xN/2.)

Časová složitost (podobně jako u QuickSortu) může v nejhorším případě být až O(N2), ale tento případ je velice atypický. V případě průměrném se dostaneme na O(N). Důkaz tohoto tvrzení zde nebudeme uvádět, jelikož není příliš snadný, uvedeme ovšem "intuitivní důkaz", proč by tomu tak mělo být: předpokládejme, že zvolíme hodnotu z tak, že k bude "někde kolem poloviny velikosti úseku" – takto po prvním průchodu zbude jeden úsek velikosti o kousek větší než N/2 a ve druhém průchodu buď číslo odhalíme nebo rozdělíme na dva úseky velikosti ≈ N/4, čímž hledání skončí s negativním výsledkem.

Program

Martin Bělocký & Martin Mareš


9-2-5 Top secret (Zadání)


Ze zadání vyplývá, že máme spočítat xs mod N. Jelikož je algoritmus velmi jednoduchý, je úmyslně zapsán hodně formálně.

Budeme postupně počítat hodnoty (x1 mod N)2 = x2 mod N, (x2 mod N)2 = x4 mod N, …. Každou další hodnotu můžeme vypočítat z předchozí pomocí jednoho násobení (umocnění na druhou) a jednoho dělení (operace modulo):

d0 = x
di+1 = x2i+1 mod N = (x2i mod N)2 mod N =
= d
2
i
mod N

Na exponent s se budeme dívat jako na číslo zapsané ve dvojové soustavě:

s=∑
z
i=0
2i si.

Pro každý jedničkový bit si přinásobíme k výsledku hodnotu di:

xs mod N = x^(∑
z
i=0
2isi) mod N =
= (∏
z
i=0
six2i ) mod N = (∏
z
i=0
sidi) mod N.

Jelikož platí následující rovnost, bude vysledek průběžně ořezávat operací modulo, abychom nepočítali se zbytečně velkými čísly:

(a·b) mod N = ((a mod N) ·(b mod N) ) mod N.

Při výpočtu xs mod N podle uvedeného algoritmu spotřebujeme nejvýše 2 log2s násobení a dělení čísel velkých nejvýše N2. Z tabulky časových složitostí uvedené v řešení minulé série plyne, že časová složitost algoritmu je O(log s log 2 N), paměťové nároky algoritmu jsou úměrné velikosti vstupu – O(log s + log N).

Zašifrované číslo bylo

77477815185737682598968113863.

Čísla 0 a 1 není dobré šifrovat, protože se šifrováním nemění – tvoří tzv. pevný bod.

Vzorové řešení je v Pascalu a používá procedury a funkce z minulé série. Původně zde mělo být také řešení v C++. Ukázalo se ale, že je příliš dlouhé na to, aby jej bylo možno otisknout. Zmiňme se tedy jen o všeobecně použitelných myšlenkách, které v něm byly použity:

  • C++ umožňuje definovat operátory i pro uživatelem definované typy. Výpočty s velkými čísly je pak možné zapisovat tak, jak jsme zvyklí – není je třeba překládat na méně přehledné volání funkcí.
  • Při výpočtech s velkými čísly je třeba velmi často jedno číslo přiřadit jinému (zkopírovat). (V Pascalu se toto zkopírování děje neviditelně jako důsledek předání proměnné hodnotou.) Je-li tato operace implementována jako zkopírování kusu paměti, což je pomalé, může běh programu značně brzdit. Jedním z možných řešení tohoto problému je technika, jež se nazývá počítání odkazů (reference counting). Objekt, nazvěme ho BigInt, reprezentující číslo, obsahuje pouze ukazatel na objekt BigCore obsahující jeho hodnotu. U tohoto objektu je pak kromě hodnoty čísla uložen také počet objektů BigInt, které na něj ukazují (reference count). Při přiřazení se pouze zvýší počítadlo v BigCore, který je přiřazován, a pak sníží počítadlo u BigCore s původní hodnotou. Pokud toto počítadlo dosáhne nuly, je objekt zrušen.

Program

Jan Kotas