Pravidla KSP

Úlohy

Úlohy v semináři bývají povětšinou algoritmického rázu – důraz je tedy kladen zejména na nalezení vhodného algoritmu řešícího daný problém a nikoliv na různé triky týkající se obelstění nevýhod toho či onoho počítače. Z toho též plyne, že vyžaduje-li se program, má tento být (pokud ovšem není v zadání uvedeno jinak) v některém z obvyklých vyšších programovacích jazyků (asi nejznámějšími jsou Pascal, C, C++, C# a Python). Také není potřeba věnovat žádnou zvláštní péči načítání vstupu – můžete předpokládat, že je vždy korektní a že se vždy vejde do paměti, pokud tedy není v zadání řečeno jinak. Neprahneme ani po žádných speciálních efektech a jiných "vylepšeních". Jde nám hlavně o algoritmy, nikoliv o návrh uživatelských rozhraní a navíc vytváření oken či tlačítek jen snižuje čitelnost zdrojového kódu. Proto okénka v Delphi ani unity crt a graph v Turbo Pascalu raději nepoužívejte. Stejné doporučení platí pro objektové programování, v žádné úloze není bezpodmínečně nutné a typicky pouze zbytečně prodlouží zdrojový kód. Zkrátka, program samotný slouží jen jako způsob formálního zápisu Vašeho algoritmu.

Protřelejší programátoři, kteří začínají čerstvě řešit, se také obvykle ptají, zda mohou ve svých řešeních používat nejrůznější pokročilé knihovny, například oblíbenou knihovnu STL jazyka C++. Naše stanovisko je takové, že užívání knihoven silně nedoporučujeme. Naší filozofií je, že každé programátorské dílo se skládá z jednotlivých menších stavebních dílů, „cihliček“, algoritmů a datových struktur, které se posléze nějak lepí dohromady. Protože nemá smysl se v korespondenčním semináři zabývat gigantickými projekty, zaměřuje se KSP právě na nácvik tvorby takových „cihliček“. Tyto „cihličky“ nebo alespoň jejich části se samozřejmě dají najít uvnitř některých knihoven, ale řešení, které tupě používá práce někoho jiného, jíž navíc absolutně nerozumíte (víte snad, co se doopravdy děje uvnitř STL?), nemá pro Vás jako řešitele žádný smysl. Z tohoto důvodu považujeme užívání cizích knihoven za nevhodné. Nicméně povolujeme libovolně využívat informace dostupné v kuchařkách a v rozumné míře se do nich odkazovat.

Bodování

Pro každou úlohu je předem stanoven maximální počet bodů, takže například nemáte-li u jedné série čas na vyřešení jedné úlohy, můžete si vybrat tu, za kterou je bodů nejméně. Tu a tam se ale může stát, že někdo dostane více bodů, než je maximum, třeba nalezne-li podstatně lepší řešení, než měl původně na mysli autor úlohy. Hodnotí se zejména:

  • Funkčnost: tedy zda algoritmus danou úlohu řeší.
  • Efektivita: jak rychle řešení pracuje a kolik na to spotřebuje paměti; bývá zvykem u každého algoritmu uvádět jeho asymptotickou časovou a paměťovou složitost (viz níže).
  • Přehlednost a kvalita popisu algoritmu: popis, z něhož není vůbec poznat, jak algoritmus vlastně funguje, je hodnocen stejně jako popis prázdný.
  • Důkaz správnosti: vedle popisu samého byste též měli více či méně formálně dokázat, že algoritmus se v konečném čase dobere požadovaných výsledků.
  • Popis programu: není nutno znovu rozebírat, jak program pracuje, neboť to mělo být napsáno již v popisu algoritmu; užíváte-li nějakých méně obvyklých programátorských obratů, je dobré o nich napsat. Rovněž komentáře v textu programu nejsou na škodu.
  • Kvalita programu: ač nevysokým počtem bodů, přeci jen též bereme ohled na přiměřenost použitých programátorských obratů.

Jelikož každý začátek je těžký, mladším řešitelům trochu pomáháme. V každé sérii najdete více úloh, od jednoduchých spíše logických hříček až po zapeklité problémy, samozřejmě s patřičně odstupňovaným bodováním. Z úloh, které nám pošlete, si vybereme pět nejlépe hodnocených, a než body zapíšeme do výsledkové listiny, přepočítáme je ještě podle následujícího vzorečku:

vzorec na prepocitavani bodu

Zde je b původní počet bodů, M maximální počet bodů za úlohu, b' nový počet bodů (zaokrouhlíme na jedno desetinné místo) a α konstanta závislá na Vašem služebním stáří, měřeném počtem sérií s, které jste nám odevzdali:

vzorec na prepocitavani bodu

Co doopravdy s Vašimi body tato formulka provede, můžete najít v následujícím grafu:

Ukazka bodovacich krivek

Úspěšní řešitelé a vítězové

Úspěšným řešitelem ročníku se stane každý, kdo získá alespoň polovinu z možných bodů. To může skýtat různé výhody, například od roku 2012 úspěšným řešitelům promíjíme přijímačky na Matfyz.

Nejlepší tři řešitelé každého ročníku se navíc stanou vítězi KSP a vyhrají nějakou cenu.

Fair play

Pravidlem číslo jedna nadále zůstává striktní dodržování zásad fair play. Nebudeme se zabývat řešeními, která jsou zjevně opsaná od Vašich spolužáků. Taktéž bychom byli neradi, aby se nám, jako ostatně již několikráte, stávalo, že se úlohy KSP stanou náplní středoškolské výuky informatiky. Nemáme nic proti tomu, abyste si úlohy na některé z hodin rozebrali, ale nepovažujeme za vhodné využívat výsledků dosažených v semináři jako kritéria pro hodnocení prospěchu. Nastanou-li nějaké problémy, seznamte své učitele s obsahem tohoto odstavce.