Kako organizirati natjecanje u doba korone

wallpaperflare.com_wallpaper

Kao što svi znate, uslijed epidemije nismo mogli održati Državno natjecanje na planirani način, ali to ne znači da ne razmišljamo o alternativnim mogućnostima.

Pojavio se prijedlog da se Državno održi online. Problem s tom idejom je mogućnost varanja u raznim oblicima i varijantama. Postoji, međutim, način da to varanje spriječimo. Mi ne možemo nadgledati natjecatelje za vrijeme online natjecanja, ali mogu ih nadgledati drugi natjecatelji – njihova konkurencija. 

Preciznije, svakom natjecatelju pridružit će se drugi natjecatelj koji će rješavati Državno natjecanje u istoj sobi i povremeno provjeravati dopisuje li se ovaj prvi s nekim i slično. To mu je u interesu jer su konkurencija. Naravno, provjera će biti obostrana. Na taj način nijedan od dvaju združenih natjecatelja neće smjeti varati jer će ga inače ovaj drugi prijaviti.

No prirodno se nameće očigledno pitanje – što ako obojica odluče varati, npr. pomagati jedan drugome, što im se u konačnici može isplatjeti? I to je rješiv problem, koji ćemo riješiti tako da im pridružimo trećeg natjecatelja, koji će rješavati u istoj sobi i paziti da ova dvojica ne varaju, a naravno da će i oni istovremeno nadgledati njega. Da bi se natjecatelji na prikladan način združili u trojke na odgovarajućim mjestima, svaki natjecatelj trebat će ispuniti obrazac (Google Form) u kojemu će napisati svoju adresu i veličinu svoje sobe u kvadratnim metrima.

Ako se krizni stožer ne složi s ovim prijedlogom, a možda i neće zbog opasnosti od širenja virusa među natjecateljima, pala mi je na pamet još jedna, pomalo neobična ali zapravo izvediva i inovativna mogućnost, koja će zbog svoje originalnosti (ako se ostvari) vjerojatno izazvati pažnju i domaćih i stranih medija. Smatra se da koronavirus ne može izdržati vrlo visoke temperature. Državno će se stoga moći bez problema održati u balonu na vrući zrak. To je nešto skuplja mogućnost, ali i dalje jeftinija od tjednog smještaja u hotelu. Veći baloni mogu ponijeti preko trideset ljudi, ovdje će zbog laptopa i potrebnog razmaka taj broj morati biti najviše dvadeset, pa će nam trebati nekoliko balona ili će se grupe izmjenjivati. 

U svakom slučaju, zaštitne maske i dalje će biti potrebne, ali one ne moraju biti obične kirurške maske kakvih ionako nedostaje na tržištu. Dovoljno učinkovite bit će i maske s fašnika (maskenbala) koje i više odgovaraju mlađahnim natjecateljima: Batman, Spiderman, James Bond, Severina, Mirko Fodor i drugi. Mogućnosti je i više nego dovoljno. Ok, toliko za sada, a službenu obavijest očekujte na neki drugi datum.

Iza kulisa HONI-ja

Voditelji ovogodišnjeg HONI-ja, Ivan Paljak i Marin Kišić, odlučili su javno objaviti repozitorij u kojem su rađeni zadatci. Evo ga ovdje:

https://github.com/mkisic/HONI-19-20

Za one koji to nikada nisu radili, ovo je dobra prilika da dobiju neki uvid u izradu zadataka za informatička natjecanja. Osim samih tekstova i rješenja, autori pišu generatore testnih primjera, razna polurješenja da bi provjerili nose li očekivani broj bodova ili konstruirali primjere koji ih ruše, kodiraju validatore koji provjeravaju zadovoljavaju li primjeri uvjete iz teksta zadatka i jesu li u dobrom formatu, pišu checkere za one zadatke gdje output nije jednoznačan itd. Kao primjer što se sve ponekad napravi za jedan zadatak, pogledajte direktorij za zadak Skandi (6. kolo).

Najprije, što je uopće repozitorij? Riječ je o folderu u kojemu više suradnika zajedno radi, a sve promjene prate se putem tzv. version control sustava (kao što je git) koji omogućava praćenje tko je i kada što dodao, promijenio i slično. Ljudi drže takve repozitorije (što javne, što privatne) na stranicama kao što su GitHub, Bitbucket i Gitlab. Version control sustavi su norma u svijetu programiranja i koristi ih svaki iole ozbiljan projekt jer inače nastane kaos. Korisni su čak i kad samo jedna osoba radi na projektu, jer imaju mogućnost undo-a tj. vraćanja na prethodnu verziju bilo koje datoteke. Sram me to priznati, ali za Državno 2018. (pod mojom palicom) koristili smo Google Drive. Ručni upload, ručni download, živi užas, ne znam što mi je bilo. Jednom i nikad više. Ovdje sve ide lijepo glatko iz komandne linije, naravno, na Linuxu.

Još jedan od važnih ovdje korištenih alata je LaTeX za tekstove zadataka. On omogućava automatizaciju mnogih stvari, npr. probni primjeri ne moraju se pisati na dva mjesta (u tekstu i u datotekama) nego se automatski kopiraju u tekst, svaki je zadatak u svojoj .tex datoteci čime se lakše prate promjene i slično. Ove godine i školsko i županijsko bili su u LaTeX-u (priznajem, prethodne dvije godine bio je Word u igri). Evo primjera glavne .tex datoteke za 6. kolo koja, kao što vidite, uključuje po jednu datoteku za svaki zadatak (npr. Trener). To se onda pretvara (“kompajlira”) u PDF naredbom pdflatex. Matematičari već znaju da je LaTeX nezaobilazan, ali to zapravo vrijedi i za računarstvo i većinu stručnih/znanstvenih disciplina.

Onda su tu generatori testnih primjera koji se najčešće pišu u Pythonu (jer je najlakše) i nastoji se izgenerirati sve primjere u jednom pokretanju generatora. Ovdje je primjer generatora za zadatak Trener. Također u Pythonu piše se i validator primjera (npr. ovaj) koji mora napisati druga osoba; on provjerava da su primjeri u ispravnom formatu (uključujući i razmake) i da zadovoljavaju sva ograničenja, uključujući i ona iz sekcije Bodovanje (npr. N < 100 u 50% primjera). Kao što se može uočiti, za generatore i validatore postoje templateovi koji pomažu da se oni brže napišu. Validator je uglavnom lako napisati, ali ponekad se moraju provjeriti i netrivijalni uvjeti poput zahtjeva da je graf povezan ili još težih uvjeta.

I naravno, tu su brutforsi, alternativna rješenja, rješenja za parcijale iz bodovanja, “prevare” (greedyji, heuristike) i ostala rješenja za koje se mora provjeriti koje primjere osvajaju. Za one zadatke gdje natjecateljev output treba programski provjeriti (jer nije jedinstven) pišu se checkeri (npr. ovaj) koji provjeravaju je li output točan. Oni su poseban izazov jer se ne smiju srušiti i moraju raditi za sve neočekivane slučajeve (pogrešan format, manjak ili višak ispisa, očekuje broj a dobije string i sve ostalo).

Previše posla? Ne uvijek. Za većinu zadataka (pogotovo one lakše) ne pojavljuju se baš svi od navedenih izazova. Nekad tekst zadatka može biti kratak i jednostavan, nekad je lako generirati primjere (baciš neki random i bok), nekad ih je lako validirati, nekad je lako napisati brutforse, checker često nije potreban itd. Na kraju, ako je dovoljno zainteresiranih ljudi i ako počnu raditi na vrijeme, ispadne OK i, naravno, bude jako zabavno.

Tip of the day: svi su oni isti

Na jednom EJOI-u prije nekoliko godina, juniori (možda Nežmah i Pavić) ispričali su mi zanimljiv matematički zadatak. Ovdje ga pišem po sjećanju pa možda nije identičan originalu.

U avion sa 100 sjedala ulazi 100 ljudi jedan po jedan, a svakome je dodijeljeno mjesto na koje treba sjesti. No prva osoba je pijanac koji ne gleda kamo sjeda, nego sjeda na slučajno odabrano mjesto i zaspi te počne glasno hrkati. Svaka sljedeća osoba sjeda na svoje mjesto ako je ono slobodno, a inače (ako je njeno mjesto zauzeto) sjeda na neko drugo, slučajno odabrano slobodno mjesto. Kolika je vjerojatnost da će posljednja osoba sjesti na svoje mjesto?

(Da me ne bi tko uhvatio u rodnoj diskriminaciji, odmah napominjem da pijanac nije nužno muškarac. Pažljiviji izraz bio bi “pijana osoba”.)

Zadatak ima vrlo kratko, jednostavno i lijepo rješenje kojega se nije lako dosjetiti. Kao hint preporučujem zadatak Mravi sa HIO 2004. u čijem se rješenju koristi donekle slična dosjetka. Drugi hint nalazi se u naslovu ovog posta, a rješenje ću za koji dan napisati u komentar.

Zadatak dana: kazaljke sata – ili Kad se sve poklopi

Sjećate li se prije godinu dana ugašene društvene mreže Google+? Ondje je nekad u 2017. godini Veky (docent Vedran Čačić s PMF-a) podijelio sljedeći zadatak:
 
Na analognom satu na kojem se sve tri (sat, minuta, sekunda) kazaljke pomiču kontinuirano, hoće li se ikad dogoditi da se sve tri nalaze unutar kuta od 1°?

Traži se vrijeme strogo između 0:0:1 i 11:59:59.

Kada se Google+ gasio, preuzeo sam arhivu svoje aktivnosti i tako došao i do tog zadatka i svojega rješenja koje sam bio napisao u komentarima. Evo tih komentara:
 
[Adrian]
3:16:16.3 i 8:43:43.7, dobiveno simulacijom po kutnim sekundama u Pythonu.
 
[Veky]
Hm, zanimljivo. 🙂 Ali nisam baš mislio na simulaciju, bar ne tako grubu. Probaj odgovoriti jesu li ikad unutar pola stupnja onda. 🙂
 
[Adrian]
1 kutna sekunda = 1/60 kutnih minuta = 1/3600 kutnih stupnjeva, što je vrlo fina simulacija. Poanta je da se može simulirati proizvoljno precizno, s brzinama kazaljki x, 12x i 12*60x.
 
[Veky]
Kad je već tako fina, odgovori na moje pitanje. 😀
 
(Ovdje sam bio zapeo. Programirao sam sve precizniju i precizniju simulaciju, kazaljke su se kretale beskonačno sporo, ali kut je uvijek ispadao mrvicu veći od pola stupnja. Vjerovao sam da je riječ o manjku preciznosti pri računanju realnim brojevima i da pravi kut iznosi točno pola stupnja, ali nisam bio dovoljno siguran da bih išta odgovorio. Sjetio sam se toga nakon više od godine dana pregledavajući history kad je Google+ upozorio da će se ugasiti.)
 
[Adrian]
Da odgovorim na ovo dok se Google+ ne ugasi 🙂 Simulacijom sam dobivao razliku toliko blizu 0.5 stupnjeva (ali ipak veću, nešto tipa 0.500x…) da sam mislio da se u stvarnosti postiže točno 0.5, ali da simulacija nikad ne može dobiti taj egzaktan položaj. Danas sam izguglao matematičko rješenje (manje je pametno nego što sam mislio) i vidio da najmanja razlika iznosi 360/719 = 0.5007 stupnjeva. Znači, simulacija je točno odgovarala na pitanje. Pouka: vjeruj kompjuteru čak i kad se čini da griješi.
 
Matematičko rješenje ostaje tajna – njega ostavljamo čitateljici za vježbu. Ali poruka je jasna.
 
Kao bonus, podijelit ću s vama dva članka o kazaljkama sata, objavljena prije mnogo godina u časopisu Matka. Prvi je članak Vladimira Devidéa iz 2000. godine o vjerojatnostima poklapanja kazaljki, a drugi je moj članak iz 2008. godine o pravilnim prikazima na digitalnom satu. Zanimljivo je da je vjerojatnost popuno različitih stvari u oba članka ispala jednaka – poklopila se. Slučajno ili ne?
 

Tip of the day: Linux

Većinu stvari u životu bolje je naučiti prije nego poslije.

Jedna od njih je pravilno tipanje. Nakon što naučite koji prst mora pritisnuti koju tipku da bi vam tipkanje bilo brže i ugodnije (a sami intuitivno nećete to skužiti), bit će vam žao što ste ikada tipkali pogrešno.

Druga i još važnija stvar je Linux, ako planirate jednom otići na međunarodno natjecanje ili se planirate baviti ikakvim programiranjem ikada u životu.

Preporučio bih i ostale Errichtove objave: https://www.youtube.com/channel/UCBr_Fu6q9iHYQCh13jmpbrg

(Naravno, postoji još stvari u životu koje je bolje naučiti prije nego poslije. Od ljubavi do meditacije. Izguglajte.)

Algoritmi u Pythonu

Vrijeme je, napokon, da i ovdje reklamiram knjigu koju smo Nikola i ja ljetos objavili. Riječ je o priručniku Algoritmi u Pythonu, namijenjenom darovitim osnovnoškolcima i onim srednjoškolcima koji tek uče algoritme. Evo linka:

https://shop.skolskaknjiga.hr/algoritmi-u-pythonu-prirucnik-za-ucenje-racunalnog-razmisljanja.html

Za zainteresirane, evo sadržaja:

Screenshot

Od ljudi koji su nam se javili, povratne informacije su izvrsne i čini se da knjiga jako dobro ispunjava svoju svrhu. Jako cijenimo svaki komentar, a pogotovo primjedbu, budući da se nadamo da će priručnik doživjeti još koje izdanje. Tko god je čitao ili bude čitao knjigu, pozivamo ga da nam javi što god mu zapne za oko, bilo pozitivno bilo negativno. Listu ispravaka uočenih pogrešaka održavamo ovdje.

Knjiga sadrži pristupne podatke za evaluator (Pythor) koji je napravio i održava Matej Ferenčević. On zasad sadrži samo zadatke s HONI natjecanja, ali plan je da se dodaju i svi zadatci s novijih službenih informatičkih natjecanja u Hrvatskoj, kao i neki zadatci koji se pojavljuju samo u knjizi Algoritmi u Pythonu.

Ako imate kakvih pitanja o knjizi, napišite u komentar, rado ću odgovoriti. Za kraj, riječ-dvije o mojoj motivaciji za pisanje priručnika, kao i za ovu objavu: cilj je napraviti dobru stvar i proširiti znanje na najbolji mogući način. “Zarada” od ovakvih knjiga je takva da se, s obzirom na uloženo vrijeme i trud, pisanje uopće ne isplati (ako razmišljate na taj način). No gledajući pozitivan učinak kod čitatelja, itekako se isplati.

Top pet novogodišnjih optimizacija

Hello friends. The year is almost over so I have prepared the top 10 optimizations of 2017 for your viewing pleasure. Without forthor ado, let us begin.

—bukefala, 7.7.2017.

Godina se bliži kraju. Po uzoru na nenadmašni post gospodina V. K. o najboljim optimizacijama 2017., ovdje objavljujemo top pet (n)ovogodišnjih optimizacija. No budući da je ovaj blog odavno zastranio u meta vode, riječ je nažalost samo o metaoptimizacijama, tj. optimizacijama informatičke produktivnosti. Jebiga. Bez daljnjeg odugovlačenja, počnimo.

  1. Zadatak dana. Izvrsna novogodišnja odluka: svaki dan riješiti jedan zadatak. Za motivaciju si naručite npr. dnevnik navika koji, između ostalog, ima mjesečnu stranicu u koju upisujete jedan redak za svaki dan tekućeg mjeseca (line per day). Naravno, tko bi pisao cijelu rečenicu – puna rečenica u ovo doba instant komunikacije krupan je zalogaj – ali dovoljno je da u redak zapišete ime zadatka koji ste toga dana riješili. Dakle, ne u neki elektronički dokument, nego pravom olovkom u pravu bilježnicu, u tome je ljepota. Vaša navika tako postaje materijalna i vaša vas draga bilježnica svakodnevno poziva da je ne ostavite neispunjenu.linePerDay
    ——–
  2. Never miss twice. Za praćenje navike rješavanja zadatka dnevno, ili bilo koje druge navike koju želimo usvojiti, možemo koristiti i jednostavniju stvar od line per day iz prethodne točke. Napravimo papirnatu tablicu (habit tracker) u koju za svaki dan stavljamo iksić ako smo toga dana odradili naviku. Cilj je ne prekinuti niz iksića ili, ako se on prekine (a hoće jer nismo savršeni), da onda to ne bude dva dana zaredom. Ja sam si svoje tri tablice (za tri navike, nije važno koje) za 2020. godinu već pripremio i jedva čekaju da ih počnem ispunjavati:imag0949
    Ponovno, važno je da ovo ispunjavate olovkom u bilježnicu, a ne na ekranu. Ako ne razumijete zašto, isprobajte jedno i drugo i bit će vam sasvim jasno koji iksić vam je veći gušt napisati.
    ——–
  3. Natjecateljski dnevnik. O upsolvingu već sam pisao, ali evo dodatnog savjeta: u bilježnici/dnevniku analizirajte svoj performans na svakom natjecanju (ili simulaciji) na kojemu se nađete. Znamo da su važna natjecanja blizu pa je ovo možda dobar čas za takav savjet. Ne mislim na dojmove tipa “bilo je teško, nisam imao koncentracije”, nego na preciznu, objektivnu analizu što ste i zašto napravili na kojem zadatku. To su olimpijci ispunjavali na IOI pripremama u online dokumentu nazvanom Dnevnik simulacija. Evo primjera jednog takvog zapisa (Adrian Beker na jednoj simulaciji 2017. godine):

    Procitao sam sve zadatke te krenuo od drugog jer mi se cinio najjednostavnijim. Nakon nekog vremena uspio sam smisliti cijelo rjesenje te sam ga bez vecih problema nakodirao, tako da je acc pao za nesto manje od sat vremena. Zatim sam presao na treci zadatak, smislio prve dvije parcijale i odlucio ih nakodirati. To se nepotrebno oduljilo zbog glupog buga, tako da mi je ostalo manje vremena nego sto sam predvidjao. Ucinilo mi se da je predzadnja parcijala dosta laksa od cijelog rjesenja pa sam ju pokusao smisliti, ali sam negdje u toku odlucio ipak nakodirati prve dvije parcijale na prvom jer su se cinile trivijalnima. Na kraju sam na tome dobio TLEove, vjerojatno zbog prevelike konstante. Zadnjih nesto manje od sat vremena proveo sam dovrsavajuci ideju za treci i kodirajuci rjesenje koje je trebalo dobiti 80%, no bilo je preruzno da bih stigao u tom vremenu.

    Poanta je u tome da razvijete natjecateljske metavještine: taktičnost, bistriji um i da u svakom trenutku točno znate što, kako i zašto rješavate. A i psihološki će vam biti lakše ako nakon neuspjeha precizno zapišete što, kako i u kojem trenutku je pošlo krivo, umjesto da ostanete u onom nejasnom, maglovitom i muljevitom osjećaju “sjebo sam, ne vrijedim” i tugaljivo bauljate hodnicima u potrazi za smislom života.

  4. Metaoptimizacije iz arhive Blogaritma. Svašta sam nadrobio u ove nepune dvije godine (od prvog aprila 2018. otkad blog postoji), od čega ima i korisnih stvari. (Iako su one druge, beskorisne stvari ono što me više veseli.) Na primjer, opširnije o navici zadatak dnevno govori ovaj post od prije godinu dana. Ako ste baš hard core, pročitajte i knjigu koju u njemu preporučujem.
    ——–
  5. Teina radna bilježnica za novogodišnje odluke. Zgodna i korisna poveznica s bloga koji toplo preporučujem. Inače, Tea je vrlo uspješna diplomirana FER-ovka koja je, tko bi rekao, programiranju “dala nogu” i odlučila raditi stvari koje više voli. Spomenimo za kraj, eto, i takvu novogodišnju mogućnost.

Informatika i dopamini

Postoji nekoliko razloga zašto se bolje baviti informatičkim natjecanjima nego bilo kojim drugima. (Ja sam jedne godine odustao od IMO-a, iako sam bio prošao, da bih se usredotočio na IOI.) Zabavnije je. Djeluje kao igrica, riješiš zadatak i dobiješ ACCEPTED. Dopamin fiks!

Malo ću pojasniti. Dopamin je hormon koji se javlja, između ostalog, kao osjećaj nagrade. Svi smo manje ili više ovisnici o njemu ako koristimo pametne telefone na kojima dobivamo notifikacije. Mobitel zavibrira, netko nam je poslao poruku! Ili nas je lajkao! Ili je objavljen novi post na Blogaritmu! Svaki taj signal ispušta malu količinu dopamina u mozgu. Pa onda počinjemo provjeravati mobitel i bez osobitog razloga, očekujući notifikaciju tj. “nagradu”. Kao rezultat, sve se teže usredotočiti na bilo što, teško je čitati dugu lektiru, teško je mirno pratiti predavanje od sat vremena. Sve je dosadno ako je sporo. A zapravo je sporost smisao života.

Rješavanje informatičkih zadataka na pozitivan način iskorištava našu želju za instant gratifikacijom. Najbolji natjecatelji mojega vremena – Goran Žužić, Stjepan Glavina i Ivan Katanić – imali su periode kada su tjednima toliko divljački rješavali zadatke na online judgevima (Goran na starom UVA judgeu, a ova dvojica na Spoju) da su nerado išli spavati. (Jeste li ikada vježbali toliko intenzivno da vam se u glavi totalno promijenio film i život kao da je postao nešto drugo? Slično zaljubljenosti nekakvoj.) Ovisnost o onom trenutku kad submission pozeleni donijela im je mnogo dobroga.

spojstatus

U matematici toga nema. Tamo ste doma riješili zadatak i to po defaultu nitko osim vas ne zna, a ni vi niste uvijek sigurni je li vam rješenje ispravno. Nema potvrde i nema zelene nagrade koja stimulira mozak i kemikalijom vas motivira da to ponavljate. Postoji i filozofska razlika. U matematici je nešto “ispravno” jer se pretpostavlja postojanje apsolutne istine (ovisne o aksiomima) do koje se dolazi zaključivanjem. U informatici, s druge strane, rješenje je ispravno ako daje rezultate koji se poklapaju s očekivanim rezultatima. To je sve, u evaluaciji nema zaključivanja, gledanja koda, nema nikakve suštine, esencije, sve je result-based. Tako je i u znanosti: teorija nije točna jer je netko do nje došao nekakvom mudrošću, nego je točna ako odgovara podatcima i mjerenjima. Ta razlika (racionalizam vs. empirizam, platonizam vs. pozitivizam) vidljiva je i u tipu ljudi koje sam, u svom vrlo ograničenom uzorku, upoznao na PMF-u (matematici) i na FER-u. Čini mi se da je među matematičarima veći postotak apstraktnih i religioznih duša nego među informatičarima.

Znam, ovo je još jedan meta post: ne govori ni o kakvom algoritmu ni zadatku, nego filozofira okolo. Rekli ste mi, znam, da bi bilo dobro objavljivati više tehničkih savjeta, a manje savjeta o savjetima. Slažem se: pozivam one koji divljački vježbaju da napišu post o, recimo, najboljem zadatku koji su riješili toga tjedna, poznatim ili nepoznatim algoritamskim trikovima, forama koje su koristili u nekom kodu, bilo što, pa da i ovaj blog postane “by Adrian i prijatelji”. Jer ja sam malo usporio s rješavanjem zadataka, ne fiksam se accovima u zadnje vrijeme. Kao što bi rekla stanovita pjevačica: plači zemljo!