• Ako riešiť úlohy

Riešenie úloh

Väčšina úloh v KSP predostrie nejaký problém a vaším cieľom je vymyslieť algoritmus, ktorý tento problém rieši. V prvom rade sa snažte, aby bolo vaše riešenie korektné, teda aby pre každý možný vstup dal váš algoritmus správnu odpoveď. Až v druhom sa snažte aby bol váš algoritmus čo najrýchlejší a spotreboval čo najmenej pamäte.

Aby sme aj my, vedúci, vedeli, ako sa vám podarilo úlohu vyriešiť, odovzdávate na našej stránke popis vášho riešenia a tiež program. Neskôr si povieme, čo to ten popis a program je. Správnosť vášho programu sa vyhodnotí chvíľku po odovzdaní, zatiaľ čo popis opravíme (okomentujeme a obodujeme) až po skončení kola. Vďaka tomu sa aj vy sami dozviete, ako dobre ste úlohu vyriešili, dostanete spätnú väzbu, niečo nové sa naučíte a so získanými bodmi môžete súťažiť s vašimi rovesníkmi.

Čo je popis riešenia?

Popis je vami napísaný text, z ktorého by malo byť jasné ako ste úlohu vyriešili. Tento text by mal obsahovať nasledovné:

  • Vysvetlenie myšlienky, na ktorej je algoritmus založený. Vysvetlite, prečo zadanú úlohu riešite práve vaším algoritmom. Napríklad: "Všimneme si, že ak má reťazec (malých písmen anglickej abecedy) viac ako 2600 znakov, tak sa určite nejaké z písmen vyskytuje v reťazci viac ako stokrát. Výskyty tohto písmena tvoria palindróm. Preto v prípade, že vstupný reťazec je dosť dlhý, stačí nájsť písmeno, ktoré sa v ňom vyskytuje aspoň stokrát."
    Z takéhoto popisu je jasné, že algoritmus, ktorý nájde najčastejšie sa vyskytujúce písmeno a vypíše ho stokrát, bude správne riešiť prípady, kedy je vstupný reťazec dosť dlhý. Ďalšia časť popisu slúži na to, aby ste popísali, ako nájdete to najčastejšie vyskytujúce sa písmeno.

  • Popis algoritmu, po prečítaní ktorého by malo byť jasné, ako by ste svoje riešenie naprogrmaovali. Netreba rozpisovať zbytočné technické detaily, skôr konkretizovať a doplniť abstraktné pojmy z hlavnej myšlienky. Napríklad "na uloženie čísel použijeme takúto štruktúru", "aby bol algoritmus rýchly namiesto obyčajného triedenia použijeme radix-sort, ktorý ...", "prehľadávanie do hĺbky implementujeme rekurziou" a podobne.
    V prípade, že chceme popísať, ako naprogramovať nájdenie najčastejšieho písmena v reťazci, spomínanom v predošlej odrážke, môžeme to popísať takto: "Postupne prejdeme reťazec a budeme si v poli dĺžky 26 počítať výskyty každého písmena. Nakoniec nájdeme najväčší prvok v tomto poli. Pozícia tohto prvku nám udáva najčastejšie písmeno v reťazci."

  • Zdôvodnenie správnosti vášho riešenia a algoritmu. Nemusíte písať žiadne formálne dôkazy, ale mali by ste zdôvodniť, prečo váš algoritmus nájde správne riešenie.

  • Odhad časovej a pamäťovej zložitosti (pozri nižšie). Ak nie je na prvý pohľad jasné, prečo má algoritmus danú zložitosť je potrebné ju zdôvodniť. (Netreba zdôvodňovať, že zložitosť algoritmu, ktorý má jeden cyklus dlžky $n$ je $O(n)$.)

    Niekoľko slov o odhade zložitosti

    Pod odhadom časovej zložitosti rozumieme odhad času, ktorý bude program trvať, v závislosti od vstupných premenných. Tento čas je priamo úmerný počtu elementárnych operácií, ktoré program vykonáva - priradenie jednoduchej premennej, porovnanie jednoduchých premenných, aritmetické operácie, atď. Väčšinou sa zaujímame o to, ako dlho beží program v priemernom, alebo najhoršom prípade (čiže si všímame priemerný, alebo maximálny čas vykonávania programu). Analogicky odhad pamäťovej zložitosti je odhad veľkosti použitej pamäti v bajtoch v závislosti od vstupných premenných.

    Väčšinou nás nezaujímajú presné hodnoty (niekto má rýchlejší počítač, na niektorých počítačoch má integer 2 a na iných 4 bajty a pod.), preto používame tzv. $O$-notáciu. Hovoríme, že funkcia $f(n)$ (napr. čas behu programu v milisekundách v závislosti od veľkosti vstupu $n$) je $O(g(n))$ ($g(n)$ je tiež funkcia), ak existuje taká konštanta $c$, že pre všetky dostatočne veľké $n~(n>n_0)$ je $f(n) \leq c \cdot g(n)$.

    Napríklad, ak program pre vstup veľkosti $n$ nebeží nikdy viac ako $T(n)=\frac{1}{2}n^3 + 5n\log(n) + 83$ mikrosekúnd, môžeme povedať, že má časovú zložitosť $O(n^3)$. Ak program potrebuje najviac $M(n) = 3n\log_2(n) + 150n + 15$ bajtov pamäti, povieme, že má pamäťovú zložitosť $O(n\log(n))$. (Poznamenávame, že ak je nejaká funkcia $O(n^2)$, tak je aj $O(n^3)$) atď. Vždy sa však snažíme nájsť čo najmenšie horné ohraničenie, t.j. funkciu, ktorá čo najpomalšie rastie.)

Samozrejme, váš popis nemusí byť takto presne rozčlenený na spomínané štyri časti. Niekedy je pohodlnejšie vysvetlenie myšlienky a popis algoritmu písať spolu, niekedy môžete pridať vlastné časti, či niektoré vynechať. Dôležitejšie ako zachovať správnu schému je zrozumiteľne vysvetliť, ako a prečo algoritmus správne rieši úlohu.

Čo netreba rozpisovať

Netrápte sa zbytočne technickými detailami, popis nemá byť prepis programu do slovenčiny. T.j. nemal by obsahovať vety typu: "Vytvoríme si premennú $x$ typu integer," "Vo for-cykle prejdeme celé pole $A$ a pre každý prvok $y$ z tohto poľa priradíme do premennej $x$ priradíme súčet premenných $x$ a $y$."

V popise netreba rozpisovať veci, ktoré nesúvisia so samotným algoritmom, ako napríklad načítavanie vstupu, formátovanie výstupu.

Tiež netreba rozpisovať, veci, ktoré sú triviálne v kontexte danej úlohy. T.j. keď riešime úlohu číslo 6, môžeme považovať nájdenie najčastiejšieho písmena v reťazci za dostatočne jednoduchý problém (napriklad v porovnaní s hľadaním najdlhšieho palindrómu)

Hranica medzi tým, čo už je jednoduché a čo už je dosť zložité na to aby to bolo treba rozpísať, sa nedá presne definovať. Zo začiatku sa snažte, veci rozpísovať detailnejšie, potom neskôr získate lepší odhad. Dôležité je, že ak niečo rozpíšete príliš do detailov, body nestratíte. Ak však niečo vysvetlíte neporiadne, môžete ich stratiť.

Ukážka dobrého popisu 1

Ukážeme si, ako by mohol vyzerať dobrý popis na úlohe Zaujímavé poháre z 32. ročníka. Úloha vraví, že máme $n$ pohárov s objemami $1$ až $n$ decilitrov, a všetky okrem jedného sú plné vody. Na vstupe máme dané $n$ a celkový objem vody v pohároch. Máme zistiť, ktorý z pohárov je prázdny.

Dobrý popis k úlohe Zaujímavé poháre

Vieme zistiť, koľko vody by bolo v pohároch, keby boli všetky plné. Je to $1+2+\dots+n$ čo je $\frac{n(n+1)}{2}$. Tento vzorec platí, pretože súčet $(1+n) + (2+n-1) + (3+n-2) +$ $\dots$ $+ (n+1)$ je zároveň $2(1+2+3+\dots+n)$ a zároveň $n(n+1)$.

Riešenie úlohy, čiže objem pohára, ktorý je prázdny je rozdiel tohto čísla a objemu vody na vstupe.

Časová zložitosť riešenia je $O(1)$, pretože súčet čísel od $1$ po $n$ dokážeme spočítať horeuvedeným vzorcom v tomto čase. Pamäťová zložitosť je tiež $O(1)$, pretože používame len konštantný počet číselných premenných.

Zlý popis k úlohe Zaujímavé poháre

Program načíta čísla zo vstupu do premenných $n$ a $v$. Následne do premennej $p$ priradí $s - (n(n-1))/2$ a hodnotu premennej $p$ vypíše.

Časová zložitosť je lineárna.

Tento popis nie je popis riešenia ale len prepis kódu z programovacieho jazyka do slovenčiny. Problémom je tiež, že chýba vysvetlenie, kde sa vzal spomínaný vzorec resp. aká je súvislosť medzi vzorcom a zadaním.

Odhad časovej zložitosti je nesprávny (časová zložitosť je konštantntá) a tiež neúplný, lebo nie je napísané, že lineárna vzhľadom od čoho (od počtu pohárov? od s? od objemu?).

Ukážka dobrého popisu 2

Podobne si ukážeme riešenie úlohy Opatera zvieratiek z 32. ročníka. Našou úlohou je vybrať takú podpostupnosť vstupného reťazca, že tvorí palindróm. Táto podpostupnosť navyše nemusí byť súvislá a dokonca ani najdlhšia možná, stačí ak bude obsahovať 100 znakov (poprípade, ak tam nie je takých 100 znakov, tak musíme nájsť tú najdlhšiu). Vstupný režazec obsahuje len malé písmena anglickej abecedy a až z. Palindróm je taký režazec, ktorý sa odpredu aj odzadu číta rovnako. Napríklad "jelenovipivonelej" alebo "napisaasipan" prípadne "aaaaaaaa".

Dobrý popis k úlohe

Všimneme si, že ak má reťazec (malých písmen anglickej abecedy) viac ako $2600$ znakov, tak sa určite nejaké z písmen vyskytuje v reťazci aspoň $100-$krát. (Ak by sa žiadne písmeno nevyskytovalo 100 krát, tak môže mať reťazec najviac $26\cdot 99 = 2574$ znakov, čo je menej ako $2600$.) Výskyty tohto písmena tvoria palindrómovú podpostupnosť dĺžky aspoň 100. Preto v prípade, že vstupný reťazec je dosť dlhý, stačí nájsť písmeno, ktoré sa v ňom vyskytuje aspoň 100 krát.

Čo však v pripade, že je vstupný reťazec kratší? V takom prípade budeme hľadať najdlhšiu palindromatickú podpostupnosť od pozície $0$ po pozíciu $n$. Ak nájdený palindróm bude dlhší ako 100 znakov, skrátime ho odstránením písmen zo stredu.

Budeme postupovať rekurzívne. V každom momente sa snažíme nájsť najdlhší palndróm od nejakej pozície $a$ po nejakú poziciu $b$. Pokiaľ $a$-te a $b$-te písmeno vstupu sú rôzne, tak nemôžu byť obe v najdlhšej palindromatickej podpostupnoti. V takom prípade je najdlhšia podpostupnosť buď od znaku $a+1$ po $b$ alebo od $a$ po $b-1$. Vyskúšame preto obe možnosti. Pokiaľ $a$-te a $b$-te písmeno vstupného reťazca sú rovnaké, nájdeme najdlhší palindróm v časti od $a+1$ po $b-1$ a pridáme toto písmeno na kraj výsledku.

Pre každú dvojicu $(a,b)$ hľadáme najdlhší palindróm v časti vstupu od $a$-teho po $b$-te písmeno vstupu len raz. Potom si výsledok zapamätáme do dvojrozmerného poľa, aby sme to nabudúce nemuseli počítať znova (memoizácia). Keďže, až na rekurzívne volanie, potrebujeme na výpočet odpovede pre jednu dvojicu $(a,b)$ konštantný čas, celková časová zložitosť tejto časti riešenia je $O(n^2)$, kde $n$ je dĺžka vstupného reťazca. Toto sa však deje, len pokiaľ je $n$ dosť malé, menšie ako konštanta $2600$. Vo všeobecnosti je časová zložitoť riešenia $O(n)$.

Prečo sa oplatí písať dobré popisy?

  • V prvom rade cieľom popisu je zrozumiteľne vysvetliť opravovateľovi, ako ste úlohu riešili. Pokiaľ to opravovateľ z vášho popisu nezistí, nemôže vám dať body za správne riešenie.

  • V druhom rade sa hodnotí aj samotná kvalia a úplnosť popisu. Teda za správne riešenie, ktoré ste zrozumiteľne odkomunikovali opravovateľovi, dostanete len časť bodov. Časť bodov sa získava za správne zdôvodnenie správnosti, správny odhad časovej zložitosti a tiež čitateľnosť popisu.

  • Pri písaní myslite na to, že opravovateľ vám nevie čítať myšlienky. Ak napriklad do popisu úlohy 1 napíšete, že algoritmus z poľa vyberie $k$-ty najmenší prvok, ale neuvediete, ako ho algoritmus nájde, tak opravovateľ nemá ako zistiť, ako to spraví. V horšom prípade (ak vám chýba podstatná časť riešenia) vám opravovateľ riešenie neuzná, v lepšom prípade si nejaký spôsob domyslí, obvykle ten najjednoduchší. Lenže ak ten spôsob čo si domyslí bude pomalší ako váš, bude vaše riešenie považované za pomalšie ako tvrdíte.

  • Často sa stane, že vymyslíte riešenie, ktoré v nejakých prípadoch nemusí nájsť správnu odpoveď. Preto je dôležité písať zdôvodnenie správnosti. Ak váš algoritmus nie je správny, môžete to odhaliť aj tým, že sa vám nedarí ukázať jeho správnosť. Vďaka tomu včas zistíte nesprávosť vášho riešenia, môžete ho opraviť a odovzdať správne riešenie.

Aby boli vaše popisy čo najlepšie, nechajte si na ich písanie dosť času. Popis, ktorý po sebe ani neprečítate, a tiež popis, ktorý je písaný v časovom strese, obvykle obsahuje veľa chýb.

Popis odporúčame písať až po tom, ako vymyslíte riešenie, ktoré chcete odovzdať, aby sa vám nestalo, že zbytočne napíšete prvé riešenie, ktoré vám napadne, a hneď potom vymyslíte lepšie riešenie. Stačí totiž odovzdať len najlepšie riešenie, ktoré ste vymysleli, ostatné netreba spisovať.

Popis môžete odovzdať aj bez toho, aby ste písali/odovzdávali program. Vždy je však lepšie program napísať a odovzdať aj keby nefungoval. Odovzdávaný program nie je potrebné dávať aj do popisu, vieme si ho nájsť medzi odovzdanými programami. Za chýbajúci program nebudete penalizovaní. Ak je popis dobrý a podrobný, môžete bez problémov získať plný počet bodov. Priloženie programu však väčšinou uľahčuje prácu opravovateľovi a vie si lepšie domyslieť, čo ste chceli vo vašom riešení spraviť.

V popise sa najviac hodnotia aj čiastkové myšlienky. Výraznú časť bodov teda viete dostať aj ak vaše riešenie nebolo úplne správne, išlo však správnym smerom. Naviac vám vedúci napíšu užitočné komentáre, ktoré vám do budúcna pomôžu sa zlepšiť. Preto odporúčame vždy odovzdať popis riešenia.

Ako odovzdať popis?

Popis môžete odovzdávať na stránke priamo pod zadaním úlohy. Mali by ste ho odovzdávať vo formáte PDF. Vďaka nemu si môžete byť istý, že riešenie vyzerá všade rovnako a naviac sa nám bude lepšie opravovať. Dokumenty vytvorené v editoroch ako Word, Openoffice sa dajú priamo v danom programe exportovať do PDF. Existuje takisto množstvo online PDF konvertorov.

Čo je program

Program je implementácia vášho algoritmu v nejakom konkrétnom programovacom jazyku. Obvykle program hodnotíme tak, že ho spustíme na niekoľkých konkrétnych vstupoch zoskupených do niekoľkých sád. Za každú sadu vstupov môžete dostať určitý počet bodov (obvykle rovnaký pre všetky sady), pokiaľ správne vyriešite všetky vstupy v sade.

Jeden vstup vyriešite, pokiaľ váš program spustený na tomto vstupe vypíše správny výstup, v správnom formáte, stihne to v určenom časovom limite (ktorý je obvykle niekoľko sekúnd) a nespotrebuje pri tom príliš veľa pamäte (čo je obvykle 1GB).

Ako písať program

  • Aby bol program vyhodnotený ako správny, musí načítať vstup a vypísať výstup vo formáte popísanom v zadaní (v častiach Formát vstupu a Formát výstupu). Napríklad treba premenné vypísať v správnom poradí a nevypisovať nič navyše.
  • Napríklad, ak máte vypísať $n$ čisel oddelených medzerami, tak za posledným číslom medzera nemá byť.
  • Nezabudnite na konci výstupu (a na oddelovanie riadkov, ak má výstup viac riadkov) vypísať znak konca riadku '\n'. Niekedy váš programovací jazyk tento znak vypisuje automaticky (napríklad print() v Pythone).
  • Nevypisujte nič navyše. Ak máte vypísať číslo 42, vypíšte len číslo 42 a nie "Počet jabĺk je 42." a podobne.
  • Viac o tom, ako písať jazyky v konkrétynch jazykoch nájdete na tejto stránke.

Špeciálne úlohy

Nie vo všetkých úlohách sa odovzdáva popis a program. V niektorých úlohách sa odovzdáva len popis alebo len program. V takom prípade je za popis resp. za program 0 bodov.

Niekedy sa namiesto programu odovzdáva riešenie v ZIP archíve. Napríklad môže byť vašou úlohou odovzdať konkrétnych 5 súborov s riešením nejakých vstupov vo vnútri. Vtedy je dôležité zachovať názvy súborov tak ako popisuje zadanie a neschovávať súbory do nejakých vnútorných priečinkov. Obvykle v takýchto úlohách nemusíte odovzdať všetky súbory, napríklad odovzdáte len 3 z 5 výstupov a budete ohodnotení za ne.

Niektoré úlohy majú úplne iný formát, napríklad namiesto písania programu len klikáte na tlačidlá na obrazovke. V takýtchto netradičných úlohách je vždy v zadaní vysvetlené, ako sá úloha odovdzáva a ako sa hodnotí.

Čas poslednej úpravy: 11. september 2019 6:47