Korešpondenčný seminár z programovania (KSP) je súťaž programátorov – stredoškolákov a mladších – pripravovaná skupinou študentov FMFI UK. Jej cieľom je zdokonaliť žiakov v programovaní a v algoritmickom myslení.

Ak študuješ na strednej škole a zaujíma ťa programovanie, neváhaj a zapoj sa do našej súťaže, má to množstvo výhod:

  • Riešením súťažných úloh a štúdiom našich vzorových riešení sa môžeš naučiť mnoho nového. Získané poznatky a skúsenosti sa ti iste budú hodiť v iných súťažiach v programovaní (napríklad pri riešení Olympiády v informatike), počas vysokoškolského štúdia, či pri prijímacích pohovoroch do zamestnania. (Mnoho našich bývalých riešiteľov sa bez ťažkostí zamestnalo v špičkových IT spoločnostiach ako Google, Facebook, ESET, …)

  • Na riešenie úloh máš dosť času a môžeš ich riešiť doma bez toho, aby si niekam cestoval.

  • Medzi zadaniami sa nachádzajú ľahšie aj ťažšie. Každý si môže vybrať tie, ktoré vie riešiť a ktoré považuje za zaujímavé.

  • Pre najlepších riešiteľov organizujeme každoročne dve týždenné sústredenia. Sústredenie je jedinečnou príležitosťou ako spoznať nových priateľov s podobnými záujmami, naučiť sa čosi viac nielen o programovaní a zažiť kopec zábavy.

Ako KSP prebieha?

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 jedenásť až trinásť 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, tri až 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ť cez formulár priamo pod zadaním , kým neuplynie termín, ktorý je 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.

Ako má vyzerať riešenie a za čo dostanem body?

Pokiaľ nie je v zadaní napísané inak, 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í.

Preto viete získať body aj keď toho veľa nenaprogramujete a budete odovzdávať dobré popisy. Navyše v niektorých úlohách netreba programovať vôbec (väčšinou to platí o úlohe číslo 1).

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. Navyše, po uplynutí riadneho termínu bude ešte fáza doprogramovania, počas ktorej môžete svoj program vylepšovať aj s pomocou vzorových riešení (viac v sekcii nižšie). 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 na stránke.

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.

Popis odovzdávajte vo formáte PDF - môžete si byť tak istí, že riešenie bude vyzerať všade rovnako a navyše sa oveľa lepšie opravuje. Dokumenty vytvorené v editoroch ako Word, Openoffice sa dajú priamo v danom programe exportovať do PDF. Existuje takisto množstvo online konvertorov do PDF.

Zopár ukážkovo vyriešených starších úloh nájdete na stránke o ideálnom riešení. 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).

Doprogramovávanie

Po uplynutí riadneho termínu kola nastáva fáza doprogramovávania. Tá trvá zhruba dva týždne a tiež má zverejnený termín, v ktorom končí. Počas tejto fázy už nemôžete odovzdávať slovné popisy. Stále však môžete získať body za naprogramovanie správneho riešenia. Naviac sú počas tejto fázy zverejnené vzorové riešenia, ktoré vám môžu pomôcť úlohu vyriešiť a úspešne naprogramovať.

Počas fázy doprogramovávania si neviete zhoršiť svoje získané skóre. Môžete ho iba vylepšiť a to až o polovicu bodov, ktoré sa vám nepodarilo získať do uplynutia riadneho termínu. Presnejšie to funguje nasledovne:

Zoberieme váš posledný submit pred uplynutím riadneho termínu. Povedzme, že ste zaň získali $X$ bodov. Potom zoberieme posledný submit zaslaný pred uplynutím doprogramovacej fázy, nech ste zaň získali $Y$ bodov. Váš bodový zisk za programovaciu časť tejto úlohy bude potom $X + \max(0, (Y-X)/2)$.

Ak ste teda počas riadneho termínu získali za vaše riešenie 5 bodov a počas doprogramovacej fázy ste odovzdali riešenie, ktoré získalo 10 bodov, celkovo za príklad získate 7.5 bodu.

Ktoré kategórie môžem riešiť?

Kategóriu Z môžu riešiť:

  • tretiaci a štvrtáci1, ak do začiatku príslušného polroka neboli na sústredení KSP,
  • druháci a mladší, ak do začiatku príslušného polroka boli najviac na jednom sústredení KSP.

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.

Čo je na kategórii T iné?

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 aj celoročná príprava riešiteľov na medzinárodné súťaže. Jej víťaza čaká večná sláva a navyše body z kategórie T budú 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 so zadaniami úloh.

Na našej stránke sa dozviete aj viac o tejto kategórii.

Registrácia

Pred odovzdaním 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 odovzdávaním vášho riešenia (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.


  1. Za štvrtákov považujeme študentov, ktorí maturujú v tomto školskom roku; tretiaci sú tí, ktorí budú maturovať budúci školský rok; ostatné ročníky analogicky. 

Čas poslednej úpravy: 13. marec 2017 12:19