Programátorské súťaže - návod

Programátorské súťaže sú v podstate druh športu, v ktorom si ľudia porovnávajú schopnosti s otatnými. Existuje veľa druhov programátorských súťaží, nás momentálne zaujímajú tie zamerané na algoritmy. Vo všeobecnosti v nich ide o to, že súťažiaci v limitovanom čase riešia presne definované a ohraničené problémy a na základe kvality svojho riešenia sú nakoniec zoradení.



Základné elementy programátorskej súťaže:

• zadania - množina jasne definovaných úloh, ktoré sa počas súťaže programátori snažia vyriešiť 
• vyhodnocovač - stroj, ktorému súťažiaci posielajú svoje riešenia a on ich vyhodnocuje 
• pravidlá - definujú, akým spôsobom budú súťažiaci zoraďovaný vo výslednom poradí danej súťaže a čo majú povolené a zakázané na súťaži vyvádzať

Zadania

Základný princíp každej úlohy je vždy rovnaký. Ide o premenu nejakých vstupných dát na výstupné dáta. Každá úloha vždy, spravidla v tomto poradí, definuje:


Špecifikácia úlohy

Popis charakteru premeny vstupných dát na výstupné. Ak je úloha jednoduchá, nachádza sa tu presný popis čo má váš program so vstupnými dátami urobiť aby vypočítal prislúchajúci výstup. Príkladom takejto úlohy je napr. „Dvojicu čísiel na vstupe ščítajte a vypíšte na výstup“.

Náročnejšie úlohy môžu trebárs povedať, čo so vstupnými dátami treba urobiť, ale opíšu tento proces tak, že keby sme ho priamo implementovali do programu, mal by ten program nejaký problém. Napríklad by pre vstup daného rozsahu bežal niekoľko rokov, potreboval by 1 TB pamäte a pod.

Takéto v zásade nesprávne riešenie, ktoré nás napadne hneď po prečítaní riešenia je však často dobrý odrazový bod na ceste za dostatočne efektívnym riešením. Súťažiaci musí v tomto prípade nájsť spôsob, akým dosiahne ekvivalentnú transformáciu efektívnejšie.

V iných prípadoch je spôsob transformácie vstupu na výstup uplne skrytý a po prečítaní zadania netušíme, čo so vstupom robiť, aby sme dostali požadovaný výstup. Ani vtedy netreba hádzať flintu do žita. V týchto prípadoch odporúčam opätovne prečítať zadanie aspon zo 3 krát, či sme náhodou neprehliadli nejaký fakt, ktorý daný problém zjednodušuje dosť na to aby sme sa vedeli pohnúť dalej.

Ak sme v zadaní nič nenašli, pozrieme sa na vzorový vstup a skúsime na papier odkrokovať, čo by sa s ním malo diať aby sme dostali správny výsledok. A posledná finta, keď neviem vyriešiť nejaký príklad, uistím sa, že v danej súťaži nie je nejaký iný, lahší príklad. Veľmi často sa stáva, že človek sa zasekne na ťažšom príklade a potom nestihne doriešiť jednoduchšie. Keďže aj v TEAP súťažiach aj v MFF súťažiach rozhoduje v prvom rade počet vyriešených príkladov, takáto chyba vie drasticky ovplyvniť výsledné umiestnenie.

Vstup

Dáta v textovom formáte, ktoré budú poskytnuté vášmu programu, keď ho bude vyhodnocovať testovať. Váš program sa k nim dostane cez štandardný vstup, čo je inými slovami to isté, ako keby ste dáta čítali z klávesnice. Napr:

cin>>x
scanf("%d",&x)

Zadanie presne definuje ako budú dáta na vstupe organizované, aké informácie sa budú nachádzať na jednotlivých riadkoch vstupu a pod. Pokiaľ špecifikácia úlohy nepovie inak, môžete predpokladať, že vstupné dáta, ktoré dostane váš program od testovača budú presne spĺňať špecifikáciu zo zadania.

Z toho vyplíva, že je zbytočné aby ste kontrolovali, či bolo naozaj zadaných 5 čísiel a nie náhodou 6, alebo či dané čísla sú naozaj len kladné a nie je medzi nimi náhodou aj 0.

Výstup

Dáta, ktoré váš program musí vrátiť vyhodnocovaču. Predáte mu ich tak, že ich jednoducho vypíšete na štandardný výstup, čo je presne to isté ako keby ste ich vypisovali do konzoly. Napr:

cout<<x
print("%d",x)

Formát výstupných dát je tiež vždy presne daný v zadaní. Na to, aby boli výstupné dáta vášho programu uznané vyhodnocovačom za správne, musia presne kopírovať formát, ktorý je vysvetlený v zadaní. Takže keď budete mať na jednom riadku vypísať číslo X, značiace počet jabĺčok na strome, nebude výstup vášho programu vyzerať nejak nasledovne:

Jablcok na strome : X

ale jednoducho len

X

Je dôležité podotknúť, že nie je nutné, aby váš program načítal VŠETKY dáta, ktoré sa nachádzajú na vstupe a až potom začal písať dáta na výstup. Tieto dve činnosti sú nezávyslé a môžu byť realizované v ľubovolnom vzájomnom poradí. Napr:

cin>>x
cout<<x+x
cin>>y
cout<<y+y

je to isté ako

cin>>x
cin>>y
cout<<x+x
cout<<y+y

Vyhodnocovač

Ok, program je hotový, čo teraz? Aj MFF aj náš testovač fungujú v podstate rovnako. Prihlásite sa na webstránku, cez ktorú sa dajú vyhodnocovaču riešenia dopraviť, preklikáte sa v menu, vyznačíte zadanie, ktoré váš odovzdávaný program rieší a pripojíte zdrojový kód vášho programu.

Prvá vec čo sa stane s vaším programom je kontrola použitých knižníc a funkcií. V prípade, že je nájdené niečo, čo je v rozpore s pravidlami súťaže, vyhodnocovač vám vráti hlášku Security exception, prípadne náš TEAP-ácky dokonca aj niečo konkrétnejšie.

Ak je všetko v poriadku, vyhodnocovač váš program u seba skompiluje a spustí ho na svoje tajné testovacie vstupy, ku ktorým súťažiaci nemajú z pochopiteľných dôvodov priamy prístup. Ak váš program beží a beží a beží a vyhodnocovač sa rozhodne, že už beží pridlho, zastaví ho a vám sa na webstránke zobrazí odpoveď Time limit exceeded.

Druhou možnosťou je, že program počas svojho behu spraví nejakú nepovolenú operáciu, napríklad vydelí nulou alebo pristúpi do pamäte, ktorá mu nebola pridelená. Vtedy vyhodnocovač zahlási Runtime exception. Predpokladajme teda, že váš program sa sám štastne ukončil.

V takom prípade testovač zoberie výstup, ktorý sa vášmu programu podaril vyprodukovať a overí, či naozaj ide o správne riešenie danej úlohy. Ak sa mu zdá, že nie, dá to vedieť hláškou Wrong answer.

Ak sa mu zdá, že to je skoro ono, len sú tam navyše medzery, prípadne nejaká čiarka atď, poskytne vám hlášku Presentation error.

Poslednou možnosťou je hláška Accepted, po zhliadnutí tejto hlášky sa tešíte, pretože ste zadanie úspešne vyriešili a bol vám pripočítaný bod.

Pravidlá

Pred tým ako sa dáte do súťaženia, je dôležité si prejsť pravidlá danej súťaže. Okrem zoznamu zakázaných funkcií a knižníc a dĺžky trvania súťaže (v rádoch niekoľkých hodín), by ste v nich hlavne mali nájsť algoritmus zoraďovania súťažiacich.

U nás aj na MFF je toto rovnaké. Súťažiaci sú počas súťaže radený primárne podľa počtu vyriešených (Accepted) príkladov. Ak majú dvaja súťažiaci rovnaký počet príkladov, rozhoduje súčet časov, ktoré potrebovali na vyriešenie všetkých nimi úspešne vyriešených príkladov. Napríklad, ak som 10 minút od začiatku súťaže úspešne odovzdal príklad A a 50 minút nato príklad B, bude môj celkový čas 10+50=60. Ak Jožo vyriešil A za 20 minút, na B potreboval ďaľších 30 minút a C skúsil odovzdať ale dostal späť Wrong answer, bude v poradí danej súťaže nižšie ako ja, pretože jeho súčet časov je až 20+50=70. Z toho okrem iného vyplíva, že optimálna stratégia je riešit príklady v poradí od tých najlahších, ktoré budete mať hotové za krátky čas až po tie najťažšie.

Verím, že po zhliadnutí tohoto riešenia sa všetci prestanú báť a budú veselo súťažiť. :-)


http://ksp.sk/~acm/
https://profiit.fiit.stuba.sk/login.php