Korešpondenčný seminár z programovania je súťaž v programovaní a tvorbe algoritmov 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ť
Elektronické verzie je možné získať z nasledujúcich linkov:
Dopyt po fyzickej papierovej verzii je ale taký veľký, že v bežných obchodných sieťach žiadny exemplár nezoženiete :-)
Najistejší spôsob, ako sa k takýmto vzácnym zbierkam dostať, je zastaviť sa na matfyze v KSPáckej miestnosti T2. Taktiež sa k nej dá dostať 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.
Ceny oboch zbierok sú rovné ich výrobným nákladom: prvá zbierka stojí 5 eur, druhá 6 eur.
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 na emailové adresy:
kuko [zavináč] ksp [bodka] sk, misof [zavináč] ksp [bodka] sk, ksp [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í. Chyby z tohto zoznamu sa nachádzajú iba vo fyzických verziách zbierok.
Zoznam nájdených chýb v prvej zbierke
- Zmazať vetu o škriatkovi.
- V riešení úlohy 522 posledná veta "(Mimochodom..." nie je pravdivá.
- V úlohách 1131 a 1521 správne meno algoritmu je "Ahov-Corasickovej algoritmus".
Zoznam nájdených chýb v druhej zbierke
- ZMAZAŤ vetu o škriatkovi!
- Niekoľko obrázkov nám zle vytlačili. Sú to obrázky na str. 61, str. 74 a str. 76.
- 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
-
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
-
Malý lenivý krtko z úlohy 943 má aj ľahšie naprogramovateľné riešenie v čase $O(n \cdot log n)$ (v C++ za použitia STL). Jeho anglický popis je tu.
-
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 \cdot 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 \cdot 23 \# \cdot n$, pre $n=0$ až $24$.
-
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=\frac{3k+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=3k$, no a $3k$ má tú vlasnosť, že sa v postupnosti hodnôt $2r \mod 3k$ (pre $r=0,1,\dots$) vyskytnú práve všetky čísla menšie ako $3k$, 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$, $32$, atď.
Pre všeobecné n teraz lineárne riešenie zostrojíme nasledovne: Nájdeme najväčšie $k$ také, že $n \geq \frac{3k+1}{2}$. V lineárnom čase zrotujeme časť poľa, aby sme dostali v poli postupne prvé a druhé diely prvých $\frac{3k+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.
-
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.
-
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ú neorientovanú 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.
-
V úlohe 1314 existuje aj lepšie riešenie v $O(p \cdot log p)$, pri ktorom nezostrojujeme celý graf, ale len tie jeho hrany, ktoré zodpovedajú hranám Delaunayovej triangulácie danej množiny bodov.
Čas poslednej úpravy: 7. október 2022 22:41