UPJŠ ŠVK 2008: Programátorská súťaž

Keďže sa už asi o ŠVK všelikde veľa hovorilo, pridávam doplňujúce informácie pre tých, ktorí sa súťaže rozhodnú zúčastniť.

Do súťaže sa treba prihlásiť, viac informácií nájdete tu: http://www.ics.upjs.sk/~krajci/skola/ine/SVK/SVK.html

V princípe treba doc. Stanovi Krajčimu zaslať e-mailom meno, priezvisko, ročník a správu, že sa chcete zúčastniť programátorskej súťaže organizovanej počas ŠVK. Na stránke uvedený termín je dobré dodržať (výnimočne sa dá prihlásiť aj neskôr). Úlohy z minulých rokov nájdete v systéme Palma - takže, ak máte chuť, môžete aj trénovať.

Extra bonusy (prémiové body k cvičeniam):

3 body za účasť

7 bodov za každú vyriešenú úlohu

Pripomínam, že v prípade vyriešenia aspoň 2 úloh máte "uznanú" praktickú časť skúšky z PAZ1b.

Na uvod sa chcem podakovat vsetkym, ktori sa zucastnili programatorskej sutaze SVK. Verim, ze to bola pre Vas zaujimava a poucna skusenost.

Zial, nie vsetkym sa podarilo vyriesit 2 ulohy potrebne na akceptovanie praktickej casti skusky z PAZ1b. Z vysledkov vsak netreba byt sklamany. Je to len programatorska sutaz, kde neraz klucovym faktorom uspechu su bohate skusenosti z riesenia uloh podobneho typu. A istotne pre vacsinu z vas to bola prva skusenost s programatorskou sutazou. Tiez treba povedat, ze realny zivot programatora s riesenim takychto uloh v "casovej tiesni" nema vela spolocneho (i ked ludia zdatni v rieseni tychto uloh hravo zvladaju aj "realne" programovanie ...).

Vzhladom na iste posutazne reakcie, mozno by bolo zaujimave na tomto fore (ci niektorom cviceni) prediskutovat mozne riesenia uloh: pochvalit sa so svojimi rieseniami, zistit preco odoslane riesenia nepresli, ake idey islo pouzit na tu-ktoru ulohu ...

(Niektoré) vzorové riešenia:
C - Zbierka: http://mo.mff.cuni.cz/p/57/reseni-3b.html
D - Obojsmerný text: http://www.ioinformatics.org/locations/ ... andout.txt
E - Pluky: http://www.ksp.sk/mop/archiv/2005/sl-2005-1-vzo.pdf

D - popis približne môjho riešenia (trochu iné ako na vyššie uvedenom linku, ale tiež dynamické programovanie):
Išlo o dynamické programovanie. Teda označme si "vstup" reťazec zo vstupu a nech X[a][b] je minimálny počet znakov, ktoré musíme doplniť do podreťazca vstupu začínajúceho na vstup[a] a končiacom na vstup[b], aby z neho vznikol palindróm. Zjavne nás zaujíma X[0][vstup.length-1]. Potrebujeme "kúzelný vzorec", ako spočítať X[a][b], keď poznáme X[a][b] pre všetky menšie podreťazce. A to takto:

1. ak b-a <= 1 (jeden znak alebo nič), tak už máme palindróm, takže X[a][b] = 0
2. ak vstup[a] == vstup[b] (na začiatku aj na konci je ten istý znak), tak tieto dva znaky už sú "v poriadku" a potrebujeme získať palindróm medzi nimi. Teda X[a][b] = X[a+1][b-1]
3. inak: Potrebujeme, aby na začiatku aj na konci bol ten istý znak. To môžeme dosiahnuť tak, že
   
   1. pridáme nejaký rovnaký znak na začiatok aj na koniec, čiže dokopy pridáme dva znaky.
   2. znak zo začiatku pridáme aj na koniec, teda tieto dva znaky už sú v poriadku a opäť nás zaujíma to, čo je medzi nimi. Teda X[a][b] = 1 + X[a+1][b]
   3. analogicky, znak z konca pridáme na začiatok, teda X[a][b] = 1 + X[a][b-1]
   Možnosť a zjavne nebude dobrá, keďže pridávame dva znaky, zatiaľ čo v ostatných len jeden, okrem toho, ďalej by sme hľadali to isté X[a][b] a tak by to šlo donekonečna. Výsledkom teda bude lepšia z možností b a c, teda X[a][b] = min(1 + X[a+1][b], 1 + X[a][b-1])

a ja som si myslel, ze su to uplne nove vymyslene ulohy...

Pokial viem, tak ulohy A a B, ktore mal na starosti Jano Katrenic, by mali byt uplne nove.

Pokial viem, tak ulohy A a B, ktore mal na starosti Jano Katrenic, by mali byt uplne nove.

tak aspon daco:)

ja som sa snazil riesit prvu a druhu ulohu
druhu som vyriesil, aj ked to vyzera ze to trvalo dlho, ale riesenie som mal pomerne skoro...

k vyrieseniu druhej ulohy mi chybalo asi este 5min casu

Ano prve dve ulohy boli nove, zvysne boli prevzate.

Ja si myslim ze to nebolo az take tazke, tu zbierku som ani neskusal robit ale napr. tie pluky a strelec boli lahke a aj ten obdlznik ktory som nestihol lebo som sa dost zdrzal pri tom retazci ktory mi aj siel pre ten priklad aj pre ine co som si vymyslel, ale asi niekde som mal chybu, lebo celkovo to slo zle. ku obdlzniku mi stacila uz iba jedna podmienka a bolo by to hotove. skoda ze upozornil na cas 2 minuty pred koncom. cas som vobec nevnimal. rano som tu podmienku doplnil a poslal a co cert nechcel, islo to. chcel som urobit 2 ulohy co sa podarilo ale dalo sa v pohode aj viac. Dobra skusenost zo sutaze.