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.