Komunikacijska složenost – ili – kako zakodirati partiju šaha

Na IOI-u 2010. prvi put smo se susreli s tipom zadatka u kojemu treba poslati neku informaciju u što manje bitova. Zadatak se zvao Saveit i trebalo je, za zadani graf, najkraće udaljenosti (između zadanih posebnih vrhova do svih ostalih) poslati kao bitovni niz iz jednog programa (encoder) u drugi program (decoder) koji će taj niz znati protumačiti, tj. iz binarnog niza rekonstruirati tražene udaljenosti. Trebalo je, naravno, napisati oba programa.

Naivno je rješenje svaku udaljenost poslati kao binaran broj, što rezultira prevelikim ukupnim brojem bitova. Ključna ideja bila je iskoristiti činjenicu da, ako su X i X’ susjedi u grafu, udaljenost(X, Y) razlikuje se od udaljenosti(X’, Y) najviše za 1. Zato je za ovu drugu udaljenost, pod pretpostavkom da smo već poslali prvu, dovoljno poslati samo razliku (-1, 0 ili 1) što možemo dvama bitovima. Ili, još bolje, konstruiramo ternarni niz koji prije slanja pretvorimo u binarni. Detalje ostavljamo čitateljici za vježbu, a cijelo rješenje imate npr. ovdje (napisala ga je moja malenkost, doduše poslije natjecanja).

Tako se na IOI-u pojavila nova tema, koju smo u Hrvatskoj ponekad zvali komunikacijskom složenošću jer se radi o veličini poruka između dvaju programa. Riječ je još i o zadatcima Parrots iz 2011., Supper iz 2012. i Stations iz 2020., a i na CEOI-u 2016. pojavio se zadatak Trick.

Ima to veze i s kompresijskim algoritmima, npr. onima koji smanje veličinu datoteka kad ih zipate, ali za razliku od tih algoritama koji su prilično generički (ne tumače sadržaj datoteka), u ovim problemima traži se kompresija specifična za dani problem. Tako mi je palo na pamet sljedeće pitanje: kako zakodirati partiju šaha, u smislu poteza koji su odigrani? Naravno, pitanje je prilično beskorisno budući da tekstualni zapis šahovske partije nije uopće velik, vjerojatno ste ga i vidjeli (riječ je o Portable Game Notation – PGN), primjerice:

1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3 O-O 9. h3 Nb8 10. d4 Nbd7 11. c4 c6 12. cxb5 axb5 13. Nc3 Bb7 14. Bg5 b4 15. Nb1 h6 16. Bh4 c5 17. dxe5 Nxe4 18. Bxe7 Qxe7 19. exd6 Qf6 20. Nbd2 Nxd6 21. Nc4 Nxc4 22. Bxc4 Nb6 23. Ne5 Rae8 24. Bxf7+ Rxf7 25. Nxf7 Rxe1+ 26. Qxe1 Kxf7 27. Qe3 Qg5 28. Qxg5 hxg5 29. b3 Ke6 30. a3 Kd6 31. axb4 cxb4 32. Ra5 Nd5 33. f3 Bc8 34. Kf2 Bf5 35. Ra7 g6 36. Ra6+ Kc5 37. Ke1 Nf4 38. g3 Nxh3 39. Kd2 Kb5 40. Rd6 Kc5 41. Ra6 Nf2 42. g4 Bd3 43. Re6 1/2-1/2

Ali čemu tražiti svrhu, ni većina drugih informatičkih zadataka nije u ovom smislu korisna. Najbolje stvari su beskorisne. Razmislimo onda kako bismo zakodirali ovakav niz poteza u što manju (binarnu ili tekstualnu) datoteku. Želite li se sami zabaviti razmišljajući o tome, slobodno ovdje prestanite čitati…

Na prvi pogled nije lako jako nadmašiti gornji PGN zapis, ali neke redukcije možemo smisliti relativno brzo. Primjerice: nema potrebe navoditi redni broj poteza; moguće je izostaviti i razmake; ne trebaju nam znakovi x (za jedenje) i + (za šah). Moguća su i sitnija poboljšanja: rezultat na kraju može se zapisati samo jednim znakom, a ponekad (npr. u slučaju mata ili pata) on nije ni potreban jer slijedi iz pozicije; rokadu je moguće prikazati jednim znakom; neka jedenja od strane pješaka (npr. hxg5) dovoljno je pisati kao običan potez (g5) ako ne može doći do zabune, tj. ako u tom trenutku ne postoje dva pješaka koji mogu jesti na g5. Tu ideju možemo proširiti i na druge figure pa pisati npr. e1 umjesto Ke1 ako u tom trenutku samo kralj može odigrati na e1. Nisu ta poboljšanja nimalo loša, ali… zasad smo još uvijek vrlo bliski PGN formatu; i dalje nam trebaju 2-3 znaka po potezu. Ako je jedan znak jedan bajt, riječ je o približno 20 bitova po prosječnom potezu. To je nekoliko puta manje od originalnog PGN zapisa, ali može i bolje!

Dobra je ideja odustati od tekstualnog zapisa, od znakova, jer 8 bitova za jedan znak nije dobar deal. Ono što zapravo zapisujemo polja su šahovske ploče, a njih je 64 = 26, što znači da je za zapis jednog polja dovoljno samo 6 bitova. Zapisujemo li potez kao par (početno polje, završno polje), dovoljno je 12 bitova po potezu – mnogo bolje od tekstualnog zapisa! Ipak, postoje i posebni potezi koje nije moguće tako zapisati: mala/velika rokada, završetak partije (kao predaja bijelog/crnog ili dogovoreni remi) ili izvlačenje nove figure gdje treba precizirati izvlači li se kraljica ili nešto drugo. Srećom, možemo se izvući tako da svaki od tih nekoliko posebnih poteza zapišemo kao neki potez koji je inače nemoguć. Recimo, mala rokada može biti zapisana kao da je riječ o potezu a1-b8, velika kao a1-c8, predaja bijelog kao a1-d8, itd. I dalje smo na 12 bitova po potezu!

Slijedi zamjedba da je umjesto početnog polja (6 bitova) bolje zakodirati figuru koja odigrava potez, jer budući da igrač ima samo 16 figura, svaka može biti određena 4-bitnim kodom. Posebne poteze i ovdje možemo zakodirati kao poteze koji su inače nemogući (npr. za bijelog pješak na a1, b1…, a za crnog pješak na a8, b8…). Već smo na 10 bitova po potezu!

Prethodni odlomci navode nas na pomisao da kompresija još uvijek nije optimalna jer postoji nemogući potezi. Ali ne samo potezi koji su uvijek nemogući, poput bijelog pješaka na prvi red ploče ili bjelopoljnog lovca na crno polje, nego i mnoštvo poteza koji su nemogući u danom trenutku partije. Pozicija na ploči, u bilo kojem trenutku, dopušta samo vrlo ograničen skup poteza i nema potrebe koristiti cijeli skup od 210 šahovskih poteza da bismo zapisali što je u tom trenutku odigrano. Drugim riječima, većina kodova uopće ne opisuje dozvoljene poteze i to je očit znak da smo još uvijek rastrošni. To je pogotovo jasno, recimo, na početku partije kada se mogu micati samo pješaci i skakači, ili u završnici kad većine figura više i nema na ploči. Ako je u nekom trenutku samo desetak dozvoljenih poteza, ne bi li nam četiri bita trebala biti dovoljna?

Kako ostvariti tu ideju? Evo kako. Za trenutačnu poziciju odredimo sve dopuštene poteze, sortiramo ih “abecedno” (ili bilo kojim drugim kriterijem), pronađemo onaj indeks u tom nizu na kojem se nalazi potez koji je zaista odigran, i zakodiramo taj indeks. Našao sam na webu podatak (dobiven empirijski) da je prosječan broj dopuštenih poteza u nekoj poziciji približno 31. To znači da bi prosječno 5 bitova trebalo biti dovoljno. Na prvi pogled može biti nejasno kako to iskoristiti jer broj dopuštenih poteza može, naravno, biti i veći – poznata je pozicija iz stvarne partije gdje je taj broj bio 79, a teoretski se on može popeti i do 218 pa nam može zatrebati i 8 bitova. Treba li nam onda neki “separator” koji će dijeliti broj s manje bitova od onog s više bitova? Ne, jer dekoder u svakom trenutku – ako prati poziciju – može znati koliko je dopuštenih poteza, a time i koliko idućih bitova treba pročitati da bi odredio indeks odigranog poteza u tom nizu. Na primjer, ako je 14 dopuštenih poteza, pročitat će četiri iduća bita da otkrije indeks odigranog (makar on bio i 0000).

Dakle, prosječno samo 5 bitova po potezu! Mana je ovog rješenja što i enkoder i dekoder moraju biti programi koji znaju igrati šah, ili barem znaju njegova pravila, jer moraju znati odrediti dopuštene poteze (te ih sortirati po istom kriteriju). Ali čini se da bolje rješenje ne postoji: uočite da svaki proizvoljno dug niz bitova (bio on i slučajan), osim pri samom kraju gdje mu može “nedostajati” bitova, opisuje neku legalnu partiju – što za prijašnja rješenja ni izdaleka ne vrijedi. Ne može bolje! Ili?

Imam i nedovršenu ideju za bolje rješenje. Dosjetka je u tome da, iako pozicija nudi 30ak mogućih poteza, nisu svi jednako vjerojatni: postoje dobri i loši potezi te, što je potez bolji, veća je vjerojatnost da je odigran. To vrijedi i za partije potpunih amatera: u svakoj poziciji postoji značajan broj zbilja besmislenih poteza koje nitko normalan neće odigrati. Kako to iskoristiti? Ovdje nam, nažalost, nije dovoljno da enkoder i dekoder znaju igrati šah. Za ovo rješenje oni bi morali dobro igrati šah, procjenjujući (na jednak način) koliko je koji potez dobar. Pa dobro, to nije neostvarivo, mogu koristiti isti šahovski engine. No što dalje? Umjesto da sortiramo dopuštene poteze po abecedi, sortirat ćemo ih po kvaliteti poteza. Tako će bolji potezi (koji se češće igraju) imati manji indeks pa će za njihov zapis trebati manje bitova. Tako, as a side effect, kvalitetu igrača možemo mjeriti duljinom zapisa njegovih poteza.

No ovdje se javlja problem koji sam natuknuo u jednom od prethodnih odlomaka. Ako postoje, recimo, 32 dopuštena poteza (5 bitova), a odigran je šesti potez po kvaliteti, želimo iskoristiti činjenicu da je indeks mali i zapisati ga koristeći 3 bita. Ali kako će dekoder znati da treba pročitati samo iduća 3 bita, a ne 5? Treba nam, možda, neki separator, ali i on mora biti binaran, i ne smije zauzeti previše bitova… Ako netko ima pametnu ideju kako ovo riješiti, neka napiše u komentar.

Tema dana: skakanje po neboderima (ili: Ne pokušavajte ovo kod kuće)

Prije petnaest godina, na jednom od prvih “težih” državnih natjecanja za osnovne škole (koje bi za današnje standarde bilo relativno lagano) pojavio se zadatak Spiderman u kojemu glavni lik (koji se zove “Spiderman”) skače po nizu nebodera zadanih visina.

Sedam godina poslije na HIO-u sam zadao nešto teži zadatak Trampolin sa sličnom tematikom skakanja po nizu nebodera, ali modernijim i suvremenijim glavnim likom. Riječ je o solidnom zadatku adhocness levela 2 koji je dobar za clear thinking jer treba pažljivo i što elegantnije pokriti sve slučajeve, a i rezultati pokazuju da to nije bilo baš lako – doduše, tada nije bilo feedbacka za vrijeme natjecanja.

Nakon još četiri godine bilo je dosta single junaka pa smo, po uzoru na najnovije filmove Batman v Superman ili Justice League, odlučili da po neboderima ima skakati više junaka. Tako je za JHIO 2016. nastao zadatak Superjunaci prema ideji Mislava Balunovića.

Zanimljivo je da su ove godine autori HONI-ja potpuno zaboravili na trendove i evoluciju tematike koju smo godinama predano razvijali, pa su ponovno zadali zadatak sa zastarjelim Spidermanom. Što reći? Neki bi zauvijek ostali u kamenom dobu.

Kad smo već kod kamenog doba, postoji još jedan moj zadatak u kojemu se umjesto niza nebodera skače po nizu stabala: Jane and Tarzan (o njemu je bilo riječi i u ovom postu). Naravno, Jane i Tarzan u zadatku koriste mobitele.

Tema dana: riješi offline

U zadatcima u kojima trebamo odgovarati na nekakve upite (queries) ponekad je moguće na svaki upit efikasno odgovoriti čim se on pojavi, pa kažemo da ga rješavamo online. Ponekad to nije moguće, nego zadatak rješavamo tako da najprije učitamo sve upite, sortiramo ih na odgovarajući način i odgovore na njih računamo u redoslijedu koji nama odgovara (offline), da bismo tek na kraju ispisali te odgovore redom kojim smo dobili upite.

Na primjer, pokušajte riješiti zadatak K-query (prije nego što pročitate rješenje odmah ispod).

Upit se ovdje sastoji od triju brojeva: granice intervala i veličina broja. Već imamo “hint” da treba rješavati offline, tj. da treba naći redoslijed u kojemu možemo efikasno odgovarati na upite. Kako ih sortirati: po lijevoj granici intervala, po desnoj, ili možda po veličini broja? Ako još ne znate rješenje, razmislite o svakoj od ovih mogućnosti.

U ovom slučaju valja odgovarati na upite redom od najmanjeg do najvećeg k. Jer kad je k = 0, upit je trivijalan (cijeli interval zadovoljava uvjet), a ako je sljedeći npr. k = 5, znamo da brojeve manje od 5 treba zanemariti i to zauvijek (jer će u idućim upitima k biti samo još veći). Trebamo dakle efikasno podržati operaciju “ubijanja” elementa iz niza te upit oblika “koliko je živih elemenata u intervalu”. Ako živi element gledamo kao jedinicu, a ubijeni kao nulu, upit se svodi na običnu sumu intervala, uz ažuriranje pojedinih elementa (1 → 0) i to možemo riješiti najjednostavnijim tournamentom ili logaritamskom strukturom. Naravno, na početku i elemente niza valja sortirati da bismo znali kada kojega (i na kojem indeksu) “ubijamo”.

Još nekoliko zadataka, redom po težini:

(Ako se dobro sjećam, službeno rješenje za Nou nije offline, ali Pavić i Lendvaj su ga tako riješili i ispalo je jednostavnije, oni će bolje znati. O zadatcima Menza i Ghost Leg neke natuknice pisao sam ovdje.)

Na ovu temu ima hrpetina zadataka, ali moje je pamćenje (a i forma) na godišnjem pa ih slobodno dopišite u komentare.

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.

Tema dana: glazbeni problemset

Na današnji dan prije točno godinu dana ovdje je objavljen prezabavni mravlji problemset. U skladu sa započetom tradicijom domaćih tematskih problemsetova (objavljen je bio i jedan kraći o nogometu), evo još jedne izložbe iz prebogate riznice dobrih starih hrvatskih zadataka, ovaj put onih čiji se tekstovi bave glazbom.

  1. Zadatak Pjesma (Županijsko 2008.)
  2. Zadatak Melodija (Školsko 2018.)
  3. Zadatak Ljestvica (HONI 2013.)
  4. Zadatak Gitara (HONI 2009.)
  5. Zadatak Ljestve (IBT 2010.)
  6. Zadatak Bard (Županijsko 2007.)
  7. Zadatak Gitara (Županijsko 2017.)
  8. Zadatak Zidarska (DMIH 2004.)
  9. Zadatak Toplista (Županijsko 2006.)
  10. Zadatak Severina (Izborne pripreme 2006.)
  11. Zadatak Zvonimir (Studentsko 2013.)
  12. Zadatak Kolekcija (HIO 2008.)

Svako stoblo je stablo, ali nije svako stablo stoblo

[Tema dana: prefiksno stablo iliti STOBLO.]

Prije tjedan dana, na 2. izbornom ispitu pojavio se zadatak sa stablom prefiksa, koje služi da bismo efikasno… Ma skužit ćete iz zadataka.

Ponekad se na crtežu ove strukture slova zapisuju u vrhove stabla. To je pogrešno: slova su bridovi, a ne vrhovi stobla. Vrh nije slovo nego prefiks, tj. niz slova kojima smo došli do tog vrha. Što se tiče implementacije, gledajući rješenja s izbornog ispita, vidio sam da neki koriste pointere, a neki ono što i ja koristim: običnu cjelobrojnu tablicu dimenzija N x 26, gdje je N maksimalan broj vrhova stabla, u kojoj sljedbenik[X][slovo] = Y znači da nakon vrha broj X slijedi slovo kojim dolazimo do vrha broj Y. Ako je ta vrijednost 0 (default), znači da nema tog slova nakon prefiksa X. Dodavanje novog vrha svodi se na operaciju sljedbenik[X][slovo] = broj_vrhova++.

Engleski je trie, a etimologija je zanimljiva (s Wikipedije):

Tries were first described by René de la Briandais in 1959. The term trie was coined by Edward Fredkin, who pronounces it /ˈtr/ (as “tree”), after the middle syllable of retrieval. However, other authors pronounce it /ˈtr/ (as “try”), in an attempt to distinguish it verbally from “tree”.

E sad, u Lijepoj Našoj netko (možda Luka Kalinovčić ili netko prije njega) počeo je ovu strukturu zvati stoblom (logika je jasna: tree –> trie, stablo –> stoblo). Taj pojam i dalje koristimo kolokvijalno. Kraće je reći stoblo nego prefiksno stablo ili stablo prefiksa. Ali nemojte ga baš tako zvati u diplomskom radu, čudno će vas gledati.

Logaritamska struktura i tournament stablo

Stare Lukine materijale počeo sam dijeliti u ovoj objavi, a sada nastavljam. Evo odakle smo (između ostalog) prije 10+ godina učili logaritamsku i tournament, kada su te stvari bile relativno nove, a dobri web materijali o njima rijetki ili nepostojeći:

Luka Kalinovčić: Logaritamska struktura i tournament stablo

Logaritamsku strukturu tako zovu samo u Hrvatskoj, vani je zovu Fenwick tree ili binary indexed tree. Nekad je to bio veliki hit (npr. u zadnjem zadatku na DMIH-u 2006.), a danas je uče već u osnovnoj školi. O naprednijim mogućnostima te strukture pisao sam u ovoj objavi.

Tournament stablo vani zovu segment treeViše o njemu, uključujući i operaciju ažuriranja intervala (lijeni tournament tj. tournament s propagacijom) kao i još neka proširenja možete naći npr. na sljedećim mjestima:

https://csacademy.com/lesson/segment_trees/

https://codeforces.com/blog/entry/15890

Kako efikasno vježbati?

Upitnik u naslovu je nužan. Kad bi naslov glasio “Kako efikasno vježbati”, bez upitnika, izgledalo bi kao da na to pitanje imam odgovor. Upitnik sugerira da možda i nemam.

Pitanje se, naravno, odnosi na vježbanje informatike (natjecateljskog programiranja), kao i recimo matematike, a ne na vježbanje tijela. Ali “kako efikasno vježbati tijelo” također je teško pitanje i odgovori na razne njegove varijante (ovisno o ciljevima) još uvijek se unapređuju, a odgovarajuća metodologija koja se zasniva na eksperimentima treba se primijeniti i na naše pitanje. Suvremenoj znanosti, a naravno i psihologiji o kojoj je ovdje donekle riječ, jasno je da malo što možemo zaključiti umovanjem. Treba uzeti sto ili tisuću ljudi i napraviti eksperiment.

U sportu nije nimalo svejedno kako točno izgleda trening pa za vrhunske sportaše velik broj stručnjaka važe i najsitnije detalje treninga. Zato su sportaši desetljećima sve bolji. No ni nama rekreativcima nije svejedno kako treniramo. Na primjer, u trčanju je efikasniji intervalni trening (mijenjanje brzine, hod + sprintevi) nego maratonsko trčanje konstantnom brzinom. U razvoju mišića, ovisno o ciljevima, nije svejedno koristimo li lakše ili teže utege, veći ili manji broj ponavljanja u seriji, veći ili manji broj serija, brze ili spore pokrete, dulje ili kraće pauze i tako dalje – a tu je i prehrana i sve ostalo.

Tako i ovdje, u matematici i informatici, vjerojatno nije svejedno na koji način vježbamo. Parametri su brojni kao i u sportu. Valja li vježbati pomalo svakodnevno, ili vikendom u većim blokovima vremena? Je li važno doba dana i radno okruženje? Iz kojih izvora rješavati zadatke, i kakve težine – rješive, umjerene ili teže? Koliko se dugo samostalno boriti sa zadatkom prije traženja pomoći ili čitanja rješenja? Dobro testirati lokalno ili odmah poslati na online judge? Simulacije natjecanja ili freestyle? Je li slučajan odabir zadataka za vježbu možda i najbolji jer sadrži najtočnije postotke pojedinih tema/područja? Ili je bolje čitati knjige, prolaziti tutorijale i rješavati zadatke po temama, tako da unaprijed znamo neke elemente rješenja? Koliko zadataka upsolvati i vrijedi li se mučiti sa zadatkom koji nam je pretežak? Nažalost, većina se ovih pitanja još i umnaža jer odgovori ovise i o nivou znanja, a možda i o osobnosti onoga koji vježba. Odgovori sigurno nisu isti za Peru Perića i Ivana Katanića.

Nemam pojma, ali nije baš svejedno, jer vrijeme je ograničeno. Moje, kao i svačije iskustvo u ovim pitanjima vrlo je usko jer je nemoguće isprobati više metoda na istom nivou znanja i onda razlikovati rezultate jedne ili druge metode. Kao što sportska znanost odgovore na analogna pitanja pronalazi desetljećima, trebalo bi možda stvoriti i granu psihologije koja bi se bavila problem-solvingom. Za početak bismo smjernice mogli potražiti u psihologiji učenja. Volio bih čuti vaša mišljenja u komentarima.