Michal Forišek, Jakub Kováč Zbierka riešených úloh Korešpondenčného seminára z programovania (1983–1998)

O zbierke

Korešpondenčný seminár z programovania je súťaž v tvorbe algoritmov a programovaní pre žiakov stredných škôl. Zbierka obsahuje zadania a myšlienky riešení úloh prvých pätnástich ročníkov tejto súťaže.

Ako ju získať

Dopyt je taký veľký, že v bežných obchodných sieťach žiadny exemplár nezoženiete :-)

Na matfyze v KSPáckej miestnosti T2 ich však ku dňu 20. 10. 2006 sedelo bezmála trinásť krabíc, a šanca je, že nejaké tam ešte sedia naďalej. Najjednoduchší spôsob, ako sa ku zbierke dostať, je teda zastaviť sa u nás na matfyze. Taktiež sa k nej dá prísť na sústredku KSP, prípadne môžete ukecať nejakého známeho KSPáka, nech vám ju donesie alebo trebárs pošle na opačný koniec sveta.

Cena zbierky bola stanovená tak, že sme zobrali výrobné náklady a zaokrúhlili ich smerom nahor. Vyšla nám tak suma 150 Sk = 4.98 EUR(*), čo za takúto skvelú knižku vôbec nie je veľa ;-)
(Pri bežných cenách v Bratislave je to momentálne asi 6 veľkých kofôl.)

(*) Cena prerátaná podľa konverzného kurzu 30,1260 Sk = 1 EUR :-)

Chyby v zbierke

Spravili sme maximum pre to, aby ste dostali do rúk úplne dokonalú knihu. Ale život už veľakrát ukázal, že nič nemôže byť dokonalé, a tak sa nejaké chyby určite nájdu aj v tejto knihe. Ak na nejakú narazíš, daj nám vedieť. Prvé odhalenie ľubovoľnej logickej alebo historickej chyby v tejto zbierke ocenia autori pozvaním šťastného nálezcu na kofolu či pivo (na pivo len plnoletých!), prípadne vlastnoručným napísaním venovania do knižky. Chyby nám oznamujte:

Preferovaný spôsob: napíšte o nej na KSPácke fórum do sekcie Zbierka

Menej preferovaný spôsob: napíšte nám o nej e-mail na adresy

 kuko [zavináč] ksp [bodka] sk, misof [zavináč] ksp [bodka] sk

Ešte predtým ako nám však napíšete, prezrite si, prosím, nasledujúci zoznam už nájdených chýb. Ponúkaná odmena stále platí.

Zoznam nájdených chýb

1. Zmazať vetu o škriatkovi.
2. V riešení úlohy 522 posledná veta "(Mimochodom..." nie je pravdivá.
3. V úlohách 1131 a 1521 správne meno algoritmu je "Ahov-Corasickovej algoritmus".

Zoznam dodatkov

1. K úlohám o dláždení dominami (433 a 1344) existuje aj lepšie riešenie ako to uvedené v zbierke, pozrite napr. http://portal.acm.org/citation.cfm?id=942530.942535
2. Malý lenivý krtko z úlohy 943 má aj ľahšie naprogramovateľné riešenie v čase N log N (v C++ za použitia STL). Jeho anglický popis je tu.
3. K úlohe 1414z o aritmetickej postupnosti prvočísel: V roku 2004 Green a Tao dokázali, že musí existovať ľubovoľne dlhá takáto postupnosť (ale bez návodu, ako nejakú nájsť). Najdlhšia v auguste 2007 známa postupnosť má 24 členov, prvý z nich je 468395662504823 a diferencia 205619 × 23#. (23# = 223092870 je súčin prvočísel po 23 vrátane). Update: 17. mája 2008 našli Raanan Chermoni & Jaroslaw Wroblewski postupnosť dĺžky 25, hodnoty sú 6171054912832631 + 366384×23#*n, pre n=0 až 24.
4. V úlohe 1342 existuje elegantné (aj keď pomerne komplikované) lineárne riešenie, ktoré vyzerá nasledovne : Uvažujme najskôr špeciálnu situáciu, kedy n=(3^k+1)/2. Očíslujme si pozície v poli od 0 po 2n-1. Knihy na pozíciách 0 a 2n-1 sú na správnom mieste. Pre ostatné knihy zjavne platí, že kniha, ktorá začína na pozícii x, chce skončiť na pozícii (2x mod 2n-1).
   Môžeme teda začať tým, že knihu z pozície 1 dáme na pozíciu 2, knihu odtiaľ na pozíciu 4, atď., až kým nedostaneme opäť nejakú knihu na pozíciu 1. Teraz využijeme našu vhodnú voľbu n. Pre naše n platí, že 2n-1=3^k, no a 3^k má tú vlasnosť, že sa v postupnosti hodnôt 2^r mod 3^k (pre r=0,1,...) vyskytnú práve všetky čísla menšie ako 3^k, ktoré nie sú deliteľné 3.
   Keď teda umiestnime knihu na pozíciu 1, presunuli sme už práve všetky knihy, ktoré sú na pozíciách nedeliteľných 3. Ostatné knihy presunieme podobne: Zopakujeme ešte niekoľkokrát ten istý proces, len namiesto začiatku na pozícii 1 postupne začneme na pozíciách 3, 3^2, atď.
   Pre všeobecné n teraz lineárne riešenie zostrojíme nasledovne: Nájdeme najväčšie k také, že n≥(3^k+1)/2. V lineárnom čase zrotujeme časť poľa, aby sme dostali v poli postupne prvé a druhé diely prvých (3^k+1)/2 kníh, a za tým prvé a druhé diely ostatných kníh. Vyššie uvedeným postupom preusporiadame prvú časť, a následne sa rekurzívne zavoláme na druhú časť poľa.
5. V riešení úlohy 1533 druhý odstavec: Rozmyslite si, že ak v našom grafe existuje cesta z x do y (pre x<y) so súčtom ohodnotení hrán d, znamená to, že z nerovníc zodpovedajúcich jednotlivým hranám vieme odvodiť tvrdenie: "v úseku od osady x+1 po osadu y vrátane sa urodilo najviac d plodov". Podobne, ak v grafe existuje cesta z y do x, v úseku sa urodilo aspoň -d plodov.
   
6. V úlohe 1543 nejde o úplne priamočiare použitie maximálneho toku, je potrebné upraviť graf tak, aby sme vedeli obmedziť kapacitu každého vrchola na 1. Štandardná technika ako to dosiahnuť: V prvom kroku nahradíme každú neorienovanú hranu dvoma orientovanými. V druhom kroku "rozdelíme" každý vrchol na dva: "vstupný" vrchol, do ktorého budú vchádzať všetky prichádzajúce hrany, a "výstupný" vrchol, z ktorého budú vychádzať všetky odchádzajúce. V treťom kroku pridáme z každého vstupného vrchola hranu s kapacitou 1 do jemu zodpovedajúceho výstupného vrchola.