Tema dana: neočekivani graf

Sanjao sam sfingu koja daje proročanstva i mogao sam postaviti jedno pitanje. Pitao sam: kada će Blogaritam ponovno biti o algoritmima? Sfinga je odgovorila: hokus pokus, bogovi su odlučili, to će biti danas!

Pa evo onda neka bude.

Znamo da se grafovi prirodno pojavljuju u mnogim zadacima, npr. kad je riječ o gradovima i cestama, poznanstvima, širenju virusa i slično. No postoji značajan broj zadataka koji se svode na graf a da to nije očito, nego se graf konstruira na netrivijalan i dosjetljiv način. Ti su zadatci često vrlo lijepi i vrijedi im posvetiti temu dana. O jednom takvom zadatku već sam pisao u postu Zadatak dana: kineski poštar.

Krenemo li od očitijeg prema manje očitom, počet ćemo od zadataka gdje treba pronaći najmanji broj nekakvih operacija da bismo nešto učinili. Shvatimo li operaciju kao prijelaz iz jednog stanja u drugo, prirodno se nameće graf čiji su vrhovi stanja, a bridovi operacije. Ovaj graf ne treba eksplicitno konstruirati, tj. pohraniti sve njegove
bridove, što možda ne bi bilo ni lako učiniti (možda ih je previše, a trebalo bi i nekako numerirati stanja). Dovoljno je pustiti npr. BFS i za pamćenje posjećenih vrhova koristiti npr. set:

U idućim zadatcima naivan BFS nije dovoljno efikasan pa je potrebna dodatna dosjetka:

I još jedan ovog tipa (preporuka Marina Kišića):

Drugu kategoriju čine zadatci gdje graf izvire iz neke tablice. O nekima od njih pisao sam u postu Tip of the day: tablica je bipartitan graf, gdje sam opisao dvije različite transformacije tablice u bipartitni graf. A malo drugačiji zadatak dao mi je Marin Kišić: Sorting a Grid.

Treću kategoriju čine zadatci gdje se konstruira graf na kojemu je rješenje neki flow. Lakši takav zadatak je A (Blokada) – Studentsko 2016., a teži je zadatak Orders (CEOI 2008.) – rješenje i testne primjere možete naći ovdje.

Naravno, najbolji su oni zadatci koji se ne mogu lako kategorizirati. Odlični zadatci s neočitim graf rješenjem pojavili su se u zadnjoj sezoni HONI-ja:

… kao i na zadnjem VRSIH-u:

Jedan teški za kraj (preporuka Patrika Pavića): Subset with zero sum. Ima ih još mnogo, slobodno dopišite u komentar.

Tip of the day: testiranje

Nekada na važnim natjecanjima nije bilo full feedbacka pa smo nervozno čekali rezultate tumarajući po hodnicima, koji su uglavnom dolazili isprintani (rezultati, ne hodnici) za svakog natjecatelja posebno – ishodi po pojedinim primjerima. I danas je slična situacija na županijskom i na HONI-ju gdje nema feedbacka, ali nekada je tako bilo i na državnom (koje se zvalo DMIH), na HIO-u, IOI-u i svugdje. Full feedback pojavio se, ako se ne varam, na IOI-u 2010. Na CEOI-u 2013. u Primoštenu još uvijek ga nije bilo, a na državnom je uveden 2015. gdje je ključnu ulogu odigrao Ante Đerek, između ostalog motiviran e-mail prepiskom nakon žalbi sa županijskog. U jednom od tih mailova Stjepan Glavina napisao je poznatu rečenicu: “Tradicionalni tip natjecanja mora nestati.”

Ovakvi incidenti su razlog zašto mislim da tradicionalni tip natjecanja (HONI, državno, CEOI, IOI prije 2010.) mora nestati. A nisam jedini koji tako misli [1]. Bodovanje je vrlo nepravedno. “Manje” kriva rješenja znaju dobivat više bodova od “više” krivih. Zna se desit i da točna rješenja s malim bugom dobiju manje bodova od potpuno krivih, ili čak nula bodova. Faktor (ne)sreće je prevelik. Drame s bugovima se događaju na svakom takvom natjecanju.

Prije full feedbacka, testiranje rješenja “s brutforsom i generatorom” bila je standardna stvar koju su jači natjecatelji tijekom natjecanja radili na svim zadatcima gdje je to imalo smisla. Jednom sam komentirao da nerado testiram jer volim misliti da sam riješio zadatak, barem tih nekoliko sati, umjesto da si testiranjem srušim rješenje. “Kurdija, to je i ideja”, odgovorio mi je Žužić odmahujući glavom u nevjerici.

Full feedback ima i određenih mana. Neki misle da je njime djelomično izgubljen važan dio natjecanja – spomenuto testiranje, te da rezultati dobiveni odmah “na pladnju” nisu nešto što je inače realno. S organizacijske strane ima više posla – zadatci moraju biti teži nego inače (jer natjecatelji zbog feedbacka troše manje vremena i manje griješe), s više parcijala da se dobije dobra disperzija bodova (koja se prije lakše dobivala zbog raznih neotkrivenih bugova), a greška u evaluaciji ili testnim primjerima košta više nego prije jer utječe na tijek natjecanja.

Osim na onim natjecanjima gdje još uvijek nema feedbacka (mislim da i Codeforces ulazi u tu kategoriju), danas testiranje koristimo i onda kada nam evaluator kaže da rješenje ne valja, ali ne znamo zašto pa moramo naći primjer na kojemu pada. Errichto dobro objašnjava kako se to radi:


Ugrubo i sažeto, evo bash skripte kakvu sam nekada koristio (njegova je malo drugačija):

echo > o1  # napravi prazan prvi output
echo > o2  # napravi prazan drugi output
while diff o1 o2; do     # dok su outputi jednaki
    ./gen.py > t         # generiraj random primjer t
    ./test.exe < t > o1  # o1 = rjesenje(t)
    ./brute.exe < t > o2 # o2 = brutfors(t)
    printf '.'           # ispisi tocku za svaki testirani primjer
done

Poziva se iz Linux terminala:

bash testiraj.sh

… ili (nakon postavljanja chmod +x testiraj.sh):

./testiraj.sh

Update: sad uočavam da sam riječ testiranje u dvama nedavnim postovima (ovom i ovom) koristio u značenju evaluacija tj. isprobavanje na službenim testnim primjerima, dok se u ovom postu testiranje odnosi na stress-testing rješenja za vrijeme natjecanja kada službeni testni primjeri još nisu dostupni. Tu dvoznačnost mogao bih otkloniti tako da u prethodnim postovima svugdje napišem evaluirati umjesto testirati, ali to mi se ne da i vjerojatno je i ovako jasno o čemu se radi.

Tip of the day: testiranje na pythonovski

Kao nastavak prethodnog posta Tip of the day: testiranje zadataka sa HSIN-a, ovdje ću testiranje rješenja napisati u Pythonu (a ne u Bashu), i to s dodatnim funkcionalnostima kao što su automatsko preuzimanje testnih primjera, mjerenje vremena izvođenja i paralelizacija. Ipak preporučujem da najprije pročitate navedeni post radi razumijevanja načina pozivanja programa, preusmjeravanja inputa/outputa i diff-anja, što ćemo koristiti i ovdje. Osim samih skripti, ideja je i pokazati neke mogućnosti Pythona.

Želimo, za početak, zaobići ručno preuzimanje zip datoteke i ručno extractanje odgovarajućih testnih primjera iz nje. Nema problema! Evo skripte download.py, koja kao argumente prima ime zadatka i URL zip datoteke s njegovim testnim primjerima:

#!/usr/bin/python3
from io import BytesIO
from zipfile import ZipFile
from urllib.request import urlopen
from sys import argv

ime_zadatka = argv[1]
url = argv[2]

resp = urlopen(url)
zipfile = ZipFile(BytesIO(resp.read()))
for filename in zipfile.namelist():
    if filename.startswith(ime_zadatka):
        zipfile.extract(filename, '.')

Primjer preuzimanja testnih primjera za zadatak Modulo s 1. kola HONI-ja 2006.:

./download.py modulo https://hsin.hr/honi/arhiva/2006_2007/kolo1_testpodaci.zip

Ishod će biti stvaranje datoteka modulo/modulo.in.1, modulo/modulo.out.1 i tako dalje, gledajući iz direktorija u kojem je skripta pokrenuta. Izmjenu skripte po vlastitim željama ostavljamo čitateljici za vježbu.

Ako se nalazimo unutar direktorija u kojemu je naše rješenje i testni primjeri, skripta koja testira sve primjere, usput mjereći vrijeme izvođenja za svaki primjer, izgledala bi primjerice ovako:

#!/usr/bin/python3
from os import listdir, popen
from time import time
from sys import argv

ime_zadatka = argv[1]
rjesenje = argv[2]

for filename in listdir('.'):
    if '.in.' in filename:
        print('\nTestiram {}...'.format(filename))
        start_time = time()
        popen('./{} < {} > tmp.out'.format(rjesenje, filename)).read()
        print('Vrijeme = {:.3f} sekundi'.format(time() - start_time))
        p = popen('diff -w tmp.out {}'.format(filename.replace('.in.', '.out.')))
        print(p.read() or '---------- OK ----------\n')

Dakle, za svaku *.in.* datoteku (ulazni primjer),  unutar popen-a kao novi proces pokrećemo naše rješenje, preusmjeravamo taj primjer na ulaz, a naš izlaz u datoteku tmp.out koju potom uspoređujemo (diff) sa službenim *.out.* izlazom. Ako je diff prazan, ispisujemo OK. Za mjerenje izvođenja ključna je funkcija time.time() koja daje trenutačno vrijeme u sekundama. Poziv skripte za zadatak Herman izgledao bi npr. ovako:

./test.py herman herman.exe

Nedostatci? Primjeri se neće nužno izvesti prirodnim redoslijedom i možda je moguće usporedno provjeravati više primjera (na više jezgri procesora) radi bržeg testiranja. Obje stvari možemo riješiti tako da napravimo četiri procesa (multiprocessing.Pool(4)) od kojih svaki paralelno testira svoj dio testnih primjera i vraća ishod kao string (npr. “Primjer 1OK, 0.1 sekundi“), koje onda na kraju možemo sortirati abecedno pa će primjer 1 biti prvi.

#!/usr/bin/python3
from os import listdir, popen
from time import time
from sys import argv
from multiprocessing import Pool

ime_zadatka = argv[1]
rjesenje = argv[2]

def testiraj(filename):
    output = '\nTestiram {}...\n'.format(filename)
    ekstenzija = filename.split('.')[-1]
    start_time = time()
    popen('./{} < {} > tmp{}.out'.format(rjesenje, filename, ekstenzija)).read()
    output += 'Vrijeme = {:.3f} sekundi\n'.format(time() - start_time)
    p = popen('diff -w tmp{}.out {}'.format(ekstenzija, filename.replace('.in.', '.out.')))
    output += p.read() or '---------- OK ----------\n'
    return output

with Pool(4) as p:
    ishodi = p.map(testiraj, [filename for filename in listdir('.') if '.in.' in filename])
for i in sorted(ishodi):
    print(i)

I ovdje se neke stvari mogu doraditi, može se dodati timeout tj. ograničiti vrijeme izvođenja, a moguće se i pobrinuti da herman.in.10 ne dođe prije herman.in.2 iako je prije po abecedi. Sve to i mnogo više ostavljamo… znate već.

Kampovske igre – članak iz 2011.

U pretprošloj objavi bila je riječ o igrama botova i AISportsu. Ovdje se prisjećam HSIN-ove Zimske škole informatike u Krapini 2011. godine kada smo Ivica Kičić i ja organizirali jednu takvu igru. Nije to bio prvi put da se na kampu radi igra botova, Kalinovčić i ekipa organizirali su nešto slično na nekim još davnijim kampovima, mislim da je u pitanju bila neka inačica igre Achtung, die Kurve!. Naša je igra bila drugačija, jednostavnija i možda manje zanimljiva za gledanje sa strane. Na turniru je pobijedio Tomislav Tunković.

O toj igri napisao sam članak za Matematičko-fizički list koji možete pronaći ovdje. Taj članak i nije naročito stručan jer tada nisam znao za teoriju igara, miješane strategije, strojno učenje i slično. Vjerojatno postoje i bolje strategije od navedenih.

Zadatak dana: Easter eggs ili Čudnovate permutacije uskršnjih jaja

Izvor: https://www.nsa.gov/News-Features/News-Stories/Article-View/Article/1627299/september-2015-puzzle-periodical/

Alice has a dozen cartons, arranged in a 3×4 grid, which for convenience we have labeled A through L:

A B C D
E F G H
I J K L

She has randomly chosen two of the cartons and hidden an Easter egg inside each of them, leaving the remaining ten cartons empty. She gives the dozen cartons to Bob, who opens them in the order A, B, C, D, E, F, G, H, I, J, K, L until he finds one of the Easter eggs, whereupon he stops. The number of cartons that he opens is his score. Alice then reseals the cartons, keeping the eggs where they are, and presents the cartons to Chris, who opens the cartons in the order A, E, I, B, F, J, C, G, K, D, H, L, again stopping as soon as one of the Easter eggs is found, and scoring the number of opened cartons. Whoever scores lower wins the game; if they score the same then it’s a tie.

For example, suppose Alice hides the Easter eggs in cartons H and K.
Then Bob will stop after reaching the egg in carton H and will score 8, while Chris will stop after reaching the egg in carton K and will score 9. So Bob wins in this case.

Who is more likely to win this game, Bob or Chris? Or are they equally likely to win?

Pokušajte riješiti zadatak, a tek onda čitajte dalje.

Rješenje možete naći na gornjoj poveznici, ili malo ljepše napisano na http://datagenetics.com/blog/march12017/index.html.

Rezultat je vrlo neobičan jer se protivi mojoj, a možda i vašoj intuiciji, koja kaže da poredak ne bi smio igrati nikakvu ulogu. Riječ je o običnim permutacijama; po čemu je ABCDEFGHIJKL bolja (i uopće drugačija) od AEIBFJCGKDHL? U čemu je fora?

Ovaj zadatak vidio sam kada ga je shareao docent Vedran Čačić s PMF-a na (bivšoj) društvenoj mreži Google+, gdje je dao i dobar uvid u odgovor na ovu neobičnost, te postavio dodatni zadatak koji će osobito informatičarima biti zanimljiv:

Of course, it’s completely obvious that there are no absolutely better/worse strategies, as long as you stick to bijections between [1..12] and [A..L] (after all, that’s why S12 is called the symmetry group), so there must be some intransitivity in the “order” of strategies. Can you find a permutation that beats Bob’s ABCDEFGHIJKL, yet is beaten by Charlie’s AEIBFJCGKDHL? 🙂

AISports i zaigrani botovi

Ovaj post napisan je u suradnji s mojim prijateljem Joelom Mislavom Kunstom.

Na Blogaritmu je uglavnom riječ o natjecateljskom programiranju koje se većinom orijentira na determinističke algoritamske zadatke. Ti su nam zadatci svima poznati i zabavni, ali postoje i drugi oblici programiranja koji su i kompetitivni i jako zabavni. Jedan je od njih natjecanje botova u igranju igara. Bot je samo drugo ime za program koji odrađuje neki zadatak automatski, umjesto čovjeka. Programiranje botova koji igraju igre razlikuje se od klasičnog natjecateljskog programiranja:

  • Programi koje isprogramiramo mogu se natjecati međusobno – protivnik nije statičan.
  • Uglavnom nema optimalnog ili očekivanog rješenja.
  • Program može krenuti jednostavno, te ga konstantno možemo poboljšavati dok se natječemo s drugima i dobivamo povratnu informaciju o tome koliko je dobar.

Takvi zadatci, koji su zapravo igre, mogu zahtijevati mnogo više vremena od standardnih zadataka s natjecanja, ali početna rješenja mogu se napraviti relativno brzo. Kod ovakvih se zadataka u manjoj ili većoj mjeri koriste algoritmi iz područja umjetne inteligencije. Oni su ponekad drugačiji od onih egzaktnih koje koristimo u zadatcima standardnog natjecateljskog programiranja, ali ne toliko koliko se može na prvi pogled činiti: ne postoji jasna granica između “umjetne inteligencije” i ostalih algoritama. U umjetnoj inteligenciji itekako vam može pomoći poznavanje pohlepnih algoritama, rekurzije i backtrackinga, dinamičkog programiranja, traženja što boljih putova u grafovima te ostalih optimizacijskih i heurističkih algoritama, iako će se ovdje naći i algoritama strojnog učenja koji vam možda još nisu poznati. Umjetna inteligencija široko je i zanimljivo područje i sve je veća potražnja za ljudima koji su u njemu vješti.

Neka od natjecanja ovog tipa organizira poznati Kaggle, ali on nije primarno posvećen natjecanju botova, nego više strojnom učenju. Poznata natjecanja botova koji igraju igre su studentsko timsko natjecanje u Starcraftu koji igraju botovi, Halite koji se održava jednom godišnje, te jedna od novijih platformi, AISports, koja najavljuje veći broj igara i konstantna natjecanja. OpenAI nudi mnogo starih igara s igraćih konzola za koje možete napraviti bota, no infrastruktura za natjecanja te jednostavan početak nisu na visokoj razini. 

Jedan od osnivača AISports-a moj je prijatelj Joel Mislav Kunst. Na toj platformi možete se baviti samo logikom svog bota, a infrastruktura za simulaciju, debugiranje i natjecanja napravljena je za vas. Postoji biblioteka za Python i Typescript, ali to je samo wrapper za vrlo jednostavan API, te možete koristiti bilo koji jezik. Kod se trenutačno izvršava lokalno na vašem računalu. Zasad je na raspolaganju jedna igra – dame tj. checkers – a u planu je dodavanje barem jedne nove igre mjesečno. Želite li malo začiniti svoj karantensko-natjecateljsko-programerski život, okušajte se u izradi bota koji pobjeđuje druge botova. Dojmove, ideje, primjedbe i komentare javite ekipi na Discordu, jako su pristupačni, pažljivo slušaju i trude se unaprijediti platformu.

(P.S. U jednom od idućih postova bit će riječ o igri botova koja se igrala na jednom davnom HSIN-ovom kampu.)

Tip of the day: testiranje zadataka sa HSIN-a

Mnogi od mojih postova sadrže poveznice na zadatke sa HSIN-a koji (barem zasad) ne postoje ni na kakvom evaluatoru. Zato je smanjena motivacija za njihovo rješavanje: nije moguće jednostavno submitati rješenje i odmah dobiti povratnu informaciju, nego je nužno pronaći i skinuti zipane testne primjere sa hsin.hr i lokalno ih isprobati.

Ovo “isprobati”, naravno, ima svoje nijanse. Mnogi znaju samo kopipejstati primjer u program, što je zbilja odvratno. Određen broj natjecatelja zna prosljeđivati jedan po jedan primjer u program koristeći komandnu liniju, te naredbom (diff ili fc) provjeriti podudaranje izlaza. Tek manji broj njih zna to učiniti za sve primjere odjednom, koristeći skriptu. Pokažimo kako se to radi!

Naprije na sporiji način. Dakle, nakon što smo zipane primjere pronašli negdje na https://hsin.hr/natjecanja.html ili na https://hsin.hr/honi/arhiva/ te ih otpakirali, potrebno je u terminalu navigirati do tog direktorija (npr. cd kodovi/herman ako se zadatak zove Herman). Ako smo rješenje kompajlirali tako da se program zove herman.exe, u terminalu ga pokrećemo na sljedeći način:

./herman.exe

(na Windowsu mislim da je bez ovoga ./). Sada bi se primjer unio “s tipkovnice” ili kopipejstao, što ne želimo. Prosljeđivanje primjera (npr. herman.in.1) izravno u program činimo na sljedeći način:

./herman.exe < herman.in.1

… i odmah vidimo što nam program ispisuje. Želimo li ispis u datoteku, pišemo npr. ovako:

./herman.exe < herman.in.1 > izlaz.txt

Tu će datoteka izlaz.txt biti stvorena ako ne postoji, ili prepisana ako postoji. Usporedbu tog našeg ispisa sa službenim izlazom činimo na sljedeći način:

diff izlaz.txt herman.out.1

(Mislim da je na Windowsu fc umjesto diff). Želimo li zanemariti whitespace, dodajemo opciju -w. Ako diff ne ispiše ništa, znači da su datoteke jednake (rješenje je točno), a inače se ispiše razlika.

To bi valjalo ponoviti za svaki primjer, npr. za peti primjer:

./herman.exe < herman.in.5 > izlaz.txt
diff -w izlaz.txt herman.out.5

Mnogo bolje od kopipejstanja, ali i dalje naporno, pogotovo ako postoji 30 primjera ili ako imamo clustere pa primjeri imaju nastavke 1a, 1b, 1c, 2a… No evo skripte koja to radi sve odjednom, nazovimo je npr. test.sh:

for input in herman.in.*; do
    extension="${input##*.}"
    output=herman.out.${extension}
    ./herman.exe < $input > izlaz.txt
    diff -w izlaz.txt $output
done

(Za Windows nemam pojma.) Da bismo je mogli pokrenuti, treba joj dodati executable flag:

chmod +x test.sh

… i potom je pokrećemo kao što bismo pokrenuli i program:

./test.sh

Riječ je o ružnom jeziku Bash koji je dobar za jednostavno Unix/Linux skriptiranje i ni za što drugo. U njemu i razmaci rade probleme.

Unaprijedimo našu Bash skriptu s još nekoliko stvari. Recimo, želimo da nam ista skripta može poslužiti za svaki zadatak, a ne da svaki put moramo mijenjati ime zadatka u skripti (u ovom slučaju Herman). Rješenje je uvesti varijablu umjesto tog imena, a tu varijablu pišemo kao $1 jer je riječ o prvom argumentu koji ćemo napisati desno od imena skripte pri njezinom pokretanju:

./test.sh herman

A skripta onda izgleda ovako:

for input in $1.in.*; do
    extension="${input##*.}"
    output=$1.out.${extension}
    ./$1.exe < $input > izlaz.txt
    diff -w izlaz.txt $output
done

Ako želimo “customizirati” i naziv rješenja, za koji smo dosad pretpostavljali da je oblika imeZadatka.exe, možemo dodati još jedan argument $2:

for input in $1.in.*; do
    extension="${input##*.}"
    output=$1.out.${extension}
    ./$2 < $input > izlaz.txt
    diff -w izlaz.txt $output
done

… nakon čega je pokrećemo npr. ovako:

./test.sh herman herman.exe

Možemo napisati i varijantu s trećim argumentom – rednim brojem primjera – ako želimo testirati samo određeni primjer. Evo i varijante koja ispisuje koji su primjeri prošli te se zaustavlja na prvom primjeru koji je pao:

for input in $1.in.*; do
    extension="${input##*.}"
    output=$1.out.${extension}
    ./$2 < $input > izlaz.txt
    if diff -w izlaz.txt $output; then
        echo $input 'prosao'
    else
        echo $input 'pao'
        exit 0
    fi
done

Primjer outputa:

herman.in.1 prosao
herman.in.2 prosao
herman.in.3 prosao
1c1
< 0
---
> 565315
herman.in.4 pao

Ni ja ne znam Bash, većinu ovoga sam izguglao. Ako netko ima primjedbi ili prijedloga poboljšanja, neka napiše u komentarima. Za neki od idućih postova nastojat ću napisati Python skriptu koja radi isto, a i više od ovoga.

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.