Korešpondenčný seminár z programovania (KSP) je súťaž programátorov - stredoškolákov a mladších - pripravovaná skupinou študentov a doktorandov FMFI UK. Jej cieľom je zdokonaliť žiakov v programovaní a v algoritmickom myslení.
Počas školského roka prebehnú dve samostatné časti súťaže: zimná a letná. Každá časť sa skladá z dvoch kôl, každé kolo obsahuje desať súťažných úloh. Najlepších riešiteľov zimnej časti pozývame na jarné sústredenie; najlepších riešiteľov letnej časti zase na to jesenné.
Súťažiť sa dá v troch kategóriách: Z (pre začínajúcich riešiteľov, obsahuje úlohy 1--5), O (skúsenejší riešitelia, úlohy 4--8) a T (špeciálna kategória pre náročných, päť samostatných úloh). Každá kategória má svoju vlastnú výsledkovú listinu. Na sústredenia pozývame riešiteľov na základe výsledkov v kategóriách Z a O.
Vaše riešenia úloh môžete odovzdávať na stránke http://old.ksp.sk/eRiesenie, kým neuplynie termín určený v zadaniach kola. Po tom, čo riešenia opravíme, nájdete na tomto mieste aj naše komentáre k nim a počet bodov získaný za jednotlivé úlohy.
Najlepších riešiteľov z kategórií KSP-Z a KSP-O pozývame každoročne na dve týždenné sústredenia. Na jesenné sústredenie nepozývame riešiteľov, ktorí už ukončili strednú školu
Kategóriu KSP-Z môžu riešiť:
Kategórií O a T sa môžu zúčastniť všetci stredoškoláci (a mladší) bez obmedzenia. Ak vám to pravidlá dovoľujú, môžete riešiť aj viacero kategórií naraz.
Vašou úlohou je vytvoriť program, ktorý rieši zadanú úlohu. V prvom rade sa snažte, aby bol korektný, t.j. aby dal pre každý vstup správnu odpoveď, v druhom rade aby bol čo najrýchlejší a mal čo najmenšie pamäťové nároky.
Riešenie úlohy pozostáva z programu a popisu použitého algoritmu. V zadaní vždy uvedieme, koľko bodov sa dá získať za program a koľko za popis; výsledný počet bodov za úlohu je súčtom týchto dvoch hodnotení.
Váš program hneď po odovzdaní automaticky otestujeme na viacerých vopred pripravených vstupoch. Body za neho vám pridelíme podľa toho, na koľkých vstupoch dá správnu odpoveď v časovom limite. Len čo sa program dotestuje, dozviete sa výsledok. Ak ste nezískali plný počet bodov, môžete program vylepšiť a odovzdať ho znova. Podrobnejšie informácie o odovzdávaní programov nájdete na našej webstránke.
Popis algoritmu by mal byť natoľko podrobný a zrozumiteľný, aby bolo možné podľa neho napísať program rovnako efektívny, ako ten váš. Ďalej vyžadujeme odhad časovej a pamäťovej zložitosti a zdôvodnenie (ak je to potrebné, aj dôkaz) správnosti algoritmu.
Ak vo svojom riešení používate zložitejšie dátové štruktúry (napríklad haldu, nie obyčajné pole), musíte popísať aj ich implementáciu. To platí aj v prípade, že ich váš programovací jazyk už obsahuje a vy ste ich neimplementovali. Ak si nie ste istí, či niečo môžete použiť bez popisu, radšej to popíšte, prípadne sa spýtajte vo fóre.
Popis odovzdávajte vo formáte PDF alebo ako plain text. Hodnotíme hlavne korektnosť algoritmu a v druhom rade jeho efektivitu. Získaný počet bodov sa dozviete, keď vaše riešenie po termíne odovzdania opravíme.
Zopár ukážkovo vyriešených starších úloh nájdete na stránke http://old.ksp.sk/wiki/Seminar/Riesenie. Na tomto mieste sa tiež môžete dočítať, čo je vlastne časová a pamäťová zložitosť (ak vám tieto pojmy veľa nehovoria).
Keď sa vám zdá, že príkladov je málo, chcete sa naučiť viac, osvojiť si nové finty a vyskúšať si naprogramovať niečo, čo ste doteraz neskúšali, táto kategória je akurát pre vás.
Úlohou tejto kategórie je celoročná príprava riešiteľov na medzinárodné súťaže. Jej víťaza čaká večná sláva a hodnotná vecná cena (zvyčajne je to knižka podľa vlastného výberu). Navyše tento rok budú body z kategórie T mierne zohľadnené pri výbere reprezentácie na Medzinárodnú olympiádu v informatike. (Tento výber má formu týždňového sústredenia, na ktoré sú pozvaní najlepší riešitelia celoštátneho kola Olympiády v informatike, kat. A.)
Na rozdiel od kategórií Z a O, v kategórii T nemusíte písať popis riešenia, odovzdávate len program. Zadania kategórie T už nenájdete v papierovej podobe, ale len na internetovej stránke http://old.ksp.sk/wiki/Zadania/Zadania.
Pred odovzdaním elektronického riešenia je potrebné zaregistrovať sa na našej webstránke a vyplniť požadované kontaktné údaje. Odporúčame sa zaregistrovať pár dní pred dňom, kedy chcete odovzdať vaše riešenie (pre prípad, že by ste mali počas registrácie nejaké problémy).
Účasťou v KSP nám dávate súhlas spracovať a archivovať údaje, ktoré nám poskytnete pri registrácii, ako aj zverejniť vaše meno, školu, ročník a získané body vo výsledkovej listine.
Tešíme sa na vaše riešenia a prajeme vám veľa dobrých nápadov.
KSPáci