Poluosvrt na izborna natjecanja

Za razliku od prijašnjih godina kada se rješavao manji broj zadataka u nešto manjem vremenu, IP ove su godine bile simulacija IOI-a: dva dana po tri zadatka u pet sati. Mislim da su zadatci ispali dobro pogođenih težina i da su pokrili mnoga područja, sva najvažnija (K-ti – strukture podataka, Parking – dinamika, Pokvareni – konstrukcijski zadatak, Izazov – nerješivi zadatak, Sklonište – grafovi, Vezuv – stringovi). Slučajno je tako dobro ispalo, jer teško je to naštimati – dobri zadatci ne padaju s neba. Svaka čast Paljku, Tonku, Bradaču i Bradaču. Između ostalog i na obaranju hrvatskog rekorda za najveće vremensko ograničenje (zadatak Izazov – 15 sekundi), čime je srušen rekord koji su držali zadatci iz devedesetih, a iznosio je impresivnih 10 sekundi.

U rješenjima smo ovaj put (možda i prvi put na hrvatskim natjecanjima općenito?) stavili i folder s alternativnim i suboptimalnim rješenjima na koja se referiraju opisi algoritama. I iz njih se može nešto naučiti.

Još jedan novitet koji se pojavio već na Državnom, a vezan je za moju čudnu privrženost jeziku, jest unaprijeđena terminologija u tekstovima (PDF). Nisu više test podatci nego testni primjeri, a sampleovi/dummyji nisu više primjeri test podataka nego probni primjeri. Jer “test podatci” em je jezično manjkavo (test je imenica, ali je upotrijebljena kao pridjev?!), em je nelogično govoriti o test podatku ako on sadrži, recimo, milijun brojeva – zar nije to milijun podataka? Nego: testni primjeri i probni primjeri, kratko i jasno.

Sad ću možda malo pretjerivati, ali nije to jedino jezično poboljšanje. Naime, kao što nas je jedan lektor u nekom drugom kontekstu upozorio, u sekciji ulaznih podataka dosad smo stalno pisali “U prvom retku nalazi se cijeli broj N” ili “U drugom retku nalazi se N brojeva” itd. Jezik ne voli redundanciju pa ovo nalazi se nije potrebno, dovoljno je koristiti glagol biti. Tako sada (ako se sjetim ispraviti) pišemo “U prvom su retku prirodni brojevi N i M” ili “U drugom je retku N brojeva” itd. Ništa se ne nalazi, naprosto jest.

Možda ću poslije još pisati o samim zadatcima, tj. o nekom od njih. Ovo je ionako samo poluosvrt. Što god to značilo. Evo jedan life hack: ako želite zvučati skromno ili manje ozbiljno, dodajte prefiks polu- ispred toga što predstavljate. Na primjer, ako niste sigurni u svoju ideju, recite da imate poluideju, predložite polurješenje. Ako niste baš pravi matematičar, recite da ste polumatematičar. Nemojte reći ljudima da su nepismeni, nego možda polupismeni ili poluobrazovani. Ili da lonac nije razbijen nego polupan. Eto, toliko za danas.

Digresija: potapanje brodova

Prije više od deset godina, točnije davne 2007. godine, sunce je sjalo, ruže su mirisale, Hrvatska se pripremala za organizaciju IOI-a, a državno se zvalo DMIH i održavalo se u hotelu Porin u čudnom manje poznatom dijelu Zagreba. (Taj je hotel nedavno bio korišten kao prihvatilište za migrante.) Bio je organiziran neki autobus u neko određeno vrijeme, ali bilo je ljepše i poetičnije na državno natjecanje ići tramvajem do Zapruđa pa pola sata pješice, ili u Zapruđu uhvatiti neki od rijetkih polugradskih autobusa. Isprobati malo divljine i života na rubu. To je ok, štedjelo se za IOI.

Autori zadataka tada su bili legende Lovro Pužar i Luka Kalinovčić, pomagao im je sistemski majstor Marko Ivanković (ono što je danas Matej), a natjecanjima je potpuno dominirao Goran Žužić, i u smislu rezultata i u smislu energije i šarma. Dok su naši kolege prije natjecanja pričali nešto o clockanju (brut/heuristika i nakon 0.9 sekundi ispiši najbolje pronađeno rješenje), Goran je zabacio kosu i komentirao: “Ja sam prva podskupina, nemam ja tu kaj clockat.” Lijepo je to bilo vrijeme, rezultatima je dominirala moja V. gimnazija, koja je do danas potpuno utihnula, izgleda da su prešli na zen budizam.

Na probnom natjecanju tada se pojavio interaktivni zadatak s potapanjem brodova. Trebalo je napisati program koji igra potapanje brodova, tj. pogađa sve protivnikove brodove na 10 x 10 ploči u što manje pokušaja, pri čemu nakon svakog pokušaja program sazna je li brod pogođen. Ima sličnih zadataka online, primjerice:

CodeChef verzija

TopCoder verzija

THE Analiza

Ono što me zapravo motiviralo da napišem ovaj post jest rješenje Gorana Žužića koje nam je ispričao nakon probnog natjecanja. Za razliku od većine nas koji smo, nakon što bismo prvi put pogodili dio nekog broda, odmah nastavili gađati oko pogođenog polja da bismo pogodili cijeli brod, Goran je radio malo drugačije. On je na početku napravio 20 ili 30 potpuno slučajnih hitaca po cijeloj ploči, neovisno o tome je li neki od njih bio uspješan. Tek potom gledao je koji su hici bili uspješni i prema tome gađao gdje su čitavi brodovi.

Vjerojatno se on toga više i ne sjeća. Nije važno je li to najbolja strategija – ovaj je post ionako digresija. No meni se takva strategija jako svidjela, više u psihološkom nego u matematičkom smislu. Ima taj duh robusnosti, ne lijepi se za prvi pogodak, nego u prvoj fazi decidirano i pomalo nemarno isprobava trideset slučajnih stvari prije nego što se u sljedećoj fazi počne fokusirati. Životna lekcija, eto što je to.

Izvor svih zadataka

Veliki američki pjesnik Walt Whitman napisao je sljedeći stih:

Stop this day and night with me

and you shall possess the origin of all poems.

Bilo bi divno imati origin of all poems, izvor svih pjesama. Ali mene zanima izvor svih zadataka – matematičkih i informatičkih, primjerice. Ne mislim na izvor kao arhivu zadataka, web stranicu ili knjigu. Nego, kao Walt Whitman, mislim na ono mjesto u glavi – možda je bolje reći stanje – iz kojeg u naletu inspiracije izviru svi prošli i budući zadatci, kao i njihova rješenja. Bio bi to ultimativni doseg svakog rješavača ili autora zadataka. U ovoj objavi ukratko bilježim svoja dosadašnja nastojanja u navedenom smjeru.

Da bi se otkrio izvor svih zadataka, najprije treba analizirati svaku pojedinu riječ ove fraze: izvor, svih, zadataka. Jer svaka od njih je važna: izvor kao metaforičko ishodište koordinatnog sustava naše potrage, svih kao ključni logički kvantifikator (ne nekih, nego svih!), i zadataka kao objekt, a ujedno i subjekt naše potrage. Kao početna točka može nam poslužiti Hrvatski jezični portal, koji navedene riječi definira na sljedeći način:

Izvor m: 1. mjesto gdje voda (nafta, plin i sl.) izlazi na površinu zemlje [izvor rijekemineralni izvor]; vrelo, vrutak 2. pren. mjesto odakle što dolazi, potječe [izvori bliski vladi] 3. dokument, djelo ili pojava koji služe za znanstveno istraživanje.

Sav (svȁ ž, svȅ srzam. prid. 〈G svèga, A svèga/sȁv (za neživo), D svèmu, L svȅm/svèmu, I svȋm/svíme〉: 1. koji je bez iznimke [sav svijetsvi ljudisve plemstvo]; cjelokupan 2. cio, čitav shvaćen u cjelini [sve selo cijelo/čitavo] 3. cio, čitav shvaćen kao ukupnost svojstava [sva ta sirotinja, uza svu nevolju] 4. u raznim kontekstima u zn. jako, vrlo, u velikoj mjeri obuzet (sam) čime [sav sam očajansav sam rasprodanžarg. vrlo sam zauzet poslom, traže me na sve strane; sav (je) pozelenio zavidan je; (slika zelenila u licu kao znak zavisti i bolesnog stanja); sav (je) usplamtio, sav (je) uzdrhtao jako se uzbudio zbog čega; ob. od želje za čim, znatiželje, pohlepe, zavisti] 5. (sr) (kao objekt u rečenici) ukupna količina, potpuna cjelina bez ostatka [prodao sam sve].

Zadatak  m 〈G -tka, N mn -áci, G zàdātākā〉: 1. ono što se kome stavlja u dužnost da radi ili izvrši, ono što treba izvršiti; dužnost, cilj, program 2. ono što treba riješiti, problem koji treba dovesti do rješenja pravilnim postupkom.

Primijetite da svaka riječ ima više mogućih značenja, što nije nimalo slučajno. No ako nam ova jezična džungla ne pomogne u potrazi, iskustvo hoće. Jer u srednjoj školi često sam svog prijatelja iz razreda, Franu Kurtovića (također informatičara), tražio da mi ispriča neki dobar zadatak. On bi svaki zadatak znakovito započeo istom riječju i znao sam da ta riječ ima veze s izvorom svih zadataka. Frane bi, naime, svaki zadatak ispričao iz perspektive “imaš”. Na primjer: “Imaš niz brojeva…”, ili, “Imaš stablo…”, ili, “Imaš tablicu…”, ili, “Imaš N gradova…”, ili, “Imaš sto tisuća upita…”, ili, “Imaš maramicu?”, i slično. Frane je tako nehotice otkrio zajednički nazivnik svih zadataka.

Kad sam mu ukazao na zanimljivu činjenicu da svaki zadatak priča tako da najprije kaže “imaš”, Frane je malo promijenio spiku, pa njegovi zadatci više nisu izvirali iz iste riječi. Glasili su: “Dobiješ niz…”, “Dobiješ usmjereni graf…”, “Dobiješ matricu…”, i tako dalje. No ovo su tek početničke spoznaje. Poslije, bitna prekretnica u mom autorskom razvoju bila je spoznaja da zadatak ne mora početi sa “imaš” ili “dobiješ”. Tada se preda mnom otvorio cijeli svijet mogućnosti.

U želji da saznam najčešći izvor naših zadataka, tj. riječ kojom zadatak najčešće započinje, odlučio sam napisati program koji pronalazi tu riječ tako da parsira s weba sve hrvatske zadatke. Program sam odlučio podijeliti s vama. (Ključni dio, kao i ispis rezultata, prepustio sam strukturi bitset kao što možete vidjeti.)

string stranice[] = {
"http://hsin.hr/natjecanja.html",
"http://informatika.azoo.hr/",
"http://zatemas.zrs.hr/"
}
for (auto & stranica : stranice) {
vector<string> zadatci = std::parse_tasks(stranica);
for (auto & zadatak : zadatci) {
bitset<string> magic;
}
}
view raw scrape_tasks hosted with ❤ by GitHub

Rezultati su zanimljivi i objavit ću ih u nekom od idućih postova. Ne mogu prvog travnja, mislili bi da je zajebancija.

IOI, IPSC i nestandardni zadatci

Ovoga tjedna u Japanu se održava IOI 2018., najprestižnije natjecanje srednjoškolaca u programiranju. Pratimo trenutačne rezultate; nakon jučerašnjeg prvog dana natjecanja najbolja iz našeg tima je Paula Vidas – svaka čast!

Nisam gledao jučerašnje zadatke, ali IOI zadatci uglavnom su vrlo kvalitetni, zbog važnosti natjecanja i vremena koje majstori iz ISC-a (International Scientific Committee) ulože u izradu zadataka. Ponekad se pojavi novi tip zadatka kakav do tada nije bio uobičajen. Naime, u IOI Syllabusu – dokumentu koji navodi teme koje se mogu pojaviti – postoji kategorija Outside of focus koja sadrži sve teme koje nisu spomenute u dokumentu, dakle, beskonačno mnogo njih. Za njih vrijedi: “This does not prevent the inclusion of a competition task that is related to a particular topic from this category. The ISC may wish to include such a competition task in order to broaden the scope of the IOI.”

Primjeri nestandardnih zadataka s prethodnih IOI:

  • Languages (IOI 2010.), prepoznavanje jezika; kao i Art Class (IOI 2013.), prepoznavanje stila slike – koketiranje s umjetnom inteligencijom i strojnim učenjem.
  • Saveit (IOI 2010.), treba napisati dva odvojena programa od kojih prvi šalje informaciju drugome koristeći što manje bitova – “komunikacijska složenost”, čuo sam da je bilo i još takvih zadataka.
  • Odometer (IOI 2012.), svojim programom generiramo drugi (traženi) program.

Naravno, nestandardnih i mnogo luđih zadataka na manje ozbiljnim natjecanjima (kao što je CF April Fools Contest) ima mnogo više.

To nas dovodi do online natjecanja IPSC koje se održava za mjesec dana i koje se temelji na neobičnim zadatcima: “Internet Problem Solving Contest pushes the boundary of what is possible in programming competitions.” Natjecanje je jako popularno i preporučujem svima da se na njemu zabave u timovima do troje ljudi.

Za kraj bih naveo nekoliko “ludih” zadataka s naših natjecanja:

  • Šetnja (Državno 2014.) – prvo pojavljivanje “challenge” zadatka u osnovnim školama,
  • Esej (HONI 2015.) – lagan, ali netipičan zadatak,
  • Janje aka Vesela bojanka (HONI 2015.) – genijalan zadatak Ivana Paljka na tri stranice.

Poluosvrt na EJOI 2018.

Jučer smo se iz Innopolisa vratili u Zagreb. Rezultati hrvatskog tima standardno su izvrsni, iako su nade bile i veće, npr. za Patrika. Moja je prognoza prije natjecanja bila zlato, srebro i dvije bronce.

Ono što olimpijadama daje posebnu draž su i svi oni dani i sati kada nema natjecanja: druženje, izleti, boravak u novom i zanimljivom okruženju. Upoznao sam Slovenca Žigu Željka koji mi je detaljno pokazao trikove kojima je prevario grader na IOI 2015. S Patrikom, Dorijanom, Franom i Bernardom bilo je pravo zadovoljstvo družiti se i zaje šaliti. Naučio sam da s ovim genijalcima nije nimalo lako igrati mafiju (točnije, bolju verziju mafije koja se zove Resistance ili Avalon) jer ih je teže prokužiti. Kombinatorika Patrika i Bernarda u toj igri, u smislu složenih logičkih implikacija koje su predlagali, bila je impresivna. Šteta što nisu malo bolje kombinirali na natjecanju, no sve je to razumljivo, jer iskustvo velikog broja natjecatelja neumoljivo kaže…

Pravilo natjecateljskog programiranja #2: Natjecanje sjebeš.

Preciznije, riješiš lošije nego što bi riješio u optimalnim okolnostima, i to možda dva od tri puta. Natjecanje ne pokazuje definitivno tko je koliko dobar, tko je bolji ili lošiji, nego daje aproksimaciju toga, kao kad radite anketu na malom uzorku populacije. Od dvaju podjednako dobrih natjecatelja bolji će ispasti onaj koji manje sjebe. Tek nakon velikog broja natjecanja procjena je precizna.

Iako smo prije EJOI-a bili predložili da na njega uvedu Python, to se još nije dogodilo. Kao veliki pobornik Pythona, savjetovao sam njegovo uvođenje potencijalnoj organizatorici sljedećeg EJOI-a, srpskoj leaderici Jeleni, koja ima sličan stav. Spominjala je zasebne time limite, s čime se ne slažem jer postoje drugi načini rješavanja problema sporosti Pythona (npr. biranje C++a u zadatcima gdje Python ne prolazi), ali to je sada manje važno, bitno je da se Python uvede. O njemu ću više pisati neki drugi put.

Zadatci su bili prvi dan dinamikasti, a drugi dan grafasti. Procjenjujući adhocness level, rekao bih da je na prvom danu Hills bio nivoa 1, AB-Strings nivoa 4, Passports nivoa 2; dok je na drugom danu Chemical Table bio nivoa 3, Prime Tree nivoa 4, a Cycle sort nivoa 3. Dakle, na prvom danu zadatcu su bili manje ad-hoc i stoga primjereniji, primjerice, koderski uvježbanijem Franu Babiću nego matematičaru Bernardu Inkretu, dok je na drugom danu bilo obrnuto – zadatci su bili manje babićasti a više inkretasti. U zadatcima se pojavilo nekoliko lijepih trikova o kojima ću napisati zasebne postove. Stay tuned!