From KSP.sk

Seminar: Zbierka

Zbierky riešených úloh Korešpondenčného seminára z programovania

O zbierkach

Korešpondenčný seminár z programovania je súťaž v tvorbe algoritmov a programovaní pre žiakov stredných škôl. Zbierky obsahujú zadania a myšlienky riešení úloh, ktoré boli v tomto seminári použité. Táto webstránka je venovaná dvom vydaniam zbierky:

• Prvá zbierka: Zbierka riešených úloh Korešpondenčného seminára z programovania (1983–1998). ISBN 80-88720-09-5, rok vydania 2006.
• Druhá zbierka: Zbierka riešených úloh Korešpondenčného seminára z programovania (1998–2006). ISBN 978-80-88720-16-4, rok vydania 2011.

Ako zbierky získať

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

Najistejší spôsob, ako sa k zbierkam dostať, je zastaviť sa na matfyze v KSPáckej miestnosti T2. Taktiež sa k nej dá prísť na sústredku KSP, prípadne môžete ukecať nejakého KSPáka, nech vám ju donesie alebo trebárs pošle na opačný koniec sveta.

Cena prvej zbierky je rovná jej výrobným nákladom: 5 eur. Cena druhej zbierky bude známa najneskôr na jarnom sústredení KSP 2011.

Chyby v zbierkach

Spravili sme maximum pre to, aby ste dostali do rúk úplne dokonalé knihy. 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 našich zbierkach. Ak na nejakú narazíte, dajte 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 v prvej zbierke

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 nájdených chýb v druhej zbierke

1. ZMAZAŤ vetu o škriatkovi!
2. Niekoľko obrázkov nám zle vytlačili. Tu sú originály: str. 61, str. 74, str. 76.
3. V riešení úlohy 1643 (začiatok druhého odstavca) namiesto "Hľadáme vlastne najmenšiu hrúbku h takú, že..." samozrejme hľadáme najväčšiu takú hrúbku.

Zoznam dodatkov k prvej zbierke

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², 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.
7. V úlohe 1314 existuje aj lepšie riešenie v O(p*log p), pri ktorom nezostrojujeme celý graf, ale len tie jeho hrany, ktoré zodpovedajú hranám Delaunayovej triangulácie danej množiny bodov.