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.

Tema dana: konstrukcijski zadatci

Ad hoc zadatke (kojima je adhocness level 4-5) teško je uvježbati. Oni su s jedne strane dobri za informatička natjecanja jer su originalni, ali s druge strane ponekad favoriziraju matematičare i one koji su manje iskusni u znanju/kodiranju (ali su zato bistriji). Je li to dobro ili loše, ne znam, no ispalo je da su zadatci koji su meni kao autoru tijekom godina padali na pamet često bili konstrukcijski ad hoc. Ovdje sam takve odlučio sabrati, ne kao nekakvu lekciju – jer takvi zadatci nisu osobito poučni – nego iz čistoga gušta. Podijelio sam ih u kategorije s obzirom na veličinu inputa.

– Ulaz je niz i slično:

– Ulaz su dva broja:

– Što mislite koliko je (netrivijalnih) konstrukcijskih zadataka moguće napraviti tako da im je ulaz jedan jedini broj? Quite a lot, as it turns out. Izgleda da sam od početka nesvjesno prihvatio taj izazov jer sam ih dosad složio (barem) osam, a možda sam neki i zaboravio:

Tema dana: clear thinking

Prije više od deset godina, na nekom starom ZRS-ovom forumu koji je odavno ugašen, postojala je tema koja se zvala “Najbolji zadatak” ili nešto slično. Ondje je (legenda) Goran Žužić linkao nekoliko zadataka koje smatra odličnima. Ako se dobro sjećam, za jedan od tih zadataka Goran je napisao otprilike ovo: “Svi ga mogu riješiti, ali prvo si morate neke stvari u glavi raščistiti“.

Rješavajući zadatak bilo mi je jasno što je Goran mislio. Zadatak nije težak, osnovna ideja brzo se uviđa, ali ne možete ga odmah na brzinu isprogramirati. Morate razmisliti te pažljivo i što elegantnije pokriti sve detalje i slučajeve. To ne možete ako vam “stvari u glavi nisu raščišćene”. I bit će vam teško bez papira i olovke.

To vrijedi za gotovo sve “tehničke zadatke” čiji je adhocness level jednak 2. Ako je baratanje slučajevima važan i prirodan dio rješenja kao u gore spomenutom zadatku (a ne da je riječ o simulaciji u kojoj je nabrojeno deset pravila), to su odlični zadatci. Umjetnost njihovog rješavanja uključuje pametno i smisleno kategoriziranje slučajeva te smišljanje rješenja koje ih pokriva elegantno, sa što manje muke (ifova i slično), te nije bug-prone tj. napisano je tako da minimizira vjerojatnost pogreške. Takvi zadatci rade razliku između “urednih” i “neurednih” programera, između onih koji su sustavni, pažljivi, temeljiti te onih drugih, koji su možda genijalni ali im nedostaje malo koderske discipline i sistematičnosti jer su im stvari u glavi više razbacane nego složene. Vježbanje takvih zadataka čini način razmišljanja ljepšim i čišćim.

(Primjer početničkog bug-prone rješenja: širenje na osam susjednih polja u matrici možete napraviti koristeći osam ifova, u svakom navodeći susjeda (x-1, y-1) ili (x-1, y) ili (x-1, y+1) ili (x, y-1) ili (x, y+1) ili (x+1, y-1) ili (x+1, y) ili (x+1, y+1) – eto vidite, već sam pogriješio – i  pišući poseban kod za svaki od tih parova, što još umnaža mogućnost pogreške. Ili lijepo kažete ovako:

for i in range(8):
    susjed_x = x + [-1, -1, -1, 0, 0, 1, 1, 1][i]
    susjed_y = y + [-1, 0, 1, -1, 1, -1, 0, 1][i]
    # provjera samo jednom

Ne samo u takvim zadatcima, nego gotovo uvijek, za urednost misli pomažu papir i olovka. Na papiru slobodno riječima pišite natuknice pa i pune rečenice: tako će vam i misli biti jasnije i dorečene te ćete ih lakše pretočiti u kod. Ne žurite, niste na Codeforcesu. (Osim kad ste na Codeforcesu. Ali ni tada, jer kao što već znate, sigurno ćete pogriješiti.)

Mali slučajevasti problemset, ugrubo po težini:

  1. The Longest Chain of Domino Tiles
  2. The Next Palindrome
  3. Zgodan
  4. Lights, Snakes and Cages
  5. Zmaj
  6. Vandal
  7. Poduzeće
  8. Best Friends

Tema dana: mravlji problemset

Budući da je danas Međunarodni dan mrava i mravlje kiseline, vrijeme je da se prisjetimo dobrih starih hrvatskih zadataka u kojima glavnu ulogu imaju mravi. Zato sam složio ovaj lijepi mravlji problemset. Zadatci su ugrubo poredani po težini.

  1. Zadatak Kolone
  2. Zadatak Mravojed
  3. Zadatak Mravi
  4. Zadatak Mrav
  5. Zadatak Mrav
  6. Zadatak Mravi
  7. Zadatak Mravi
  8. Zadatak Ludi
  9. Zadatak Mravi
  10. Zadatak Mravi
  11. Zadatak Mravograd

CX9HaVD

Tema dana: duguljaste matrice

Dok sam bio srednjoškolski natjecatelj, netko mi je poslao zip s desetak tekstualnih dokumenata u kojima je (legenda) Luka Kalinovčić, tada mentor u ZRS-u i HSIN-u, opisao nekoliko algoritama i riješio nekoliko zadataka. Budući da su neki od tih tekstova vrlo poučni, odlučio sam ih podijeliti u ovoj i nekim budućim objavama.

Jedna od tema u toj mapi bila je i “Exponential time DP”, tj. dinamičko programiranje s eksponencijalnom složenosti. Takva složenost obično nastaje kada u stanju dinamike držimo “masku”, najčešće binarni broj čije nam znamenke 0-1 kazuju koje smo od N objekata dosad odabrali/iskoristili a koje nismo, pa je broj mogućih stanja (npr. 2N) eksponencijalan.

Naravno, to ima smisla samo ako je N iz gornjeg odlomka relativno malen. Ako je taj N jedna dimenzija neke matrice, koja dakle ima malen broj redaka (ili stupaca), govorimo o “duguljastoj matrici”. Promotrimo, primjerice, sljedeći zadatak:

Na koliko načina možemo popločiti sobu dimenzija R x S pločicama oblika kao na slici? (2 R ≤ 100, 2 ≤ S ≤ 10). Rješenje ispišite modulo 220.

tri

Primjeri:

ulaz: 2 3

izlaz: 2

ulaz: 4 3

izlaz: 4

ulaz: 9 8

izlaz: 204184

ulaz: 47 9

izlaz: 6656

Dakle, zadani broj stupaca je najviše 10, dok broj redaka može biti do 100, pa je matrica “duguljasta”. Za veći broj stupaca zadatak bi bio daleko teži (ako bi uopće bio rješiv). Rješenje zadatka i njegovu implementaciju dao je Luka Kalinovčić u već spomenutoj prastaroj mapi, a odgovarajući dokument nalazi se ovdje.

Drugi Lukin primjer nalazi se u ovom dokumentu gdje se rješava zagonetka kakva se redovito nalazi u našim novinama.

Zadatci za vježbu:

  • Tiling a grid with dominoes – najlakši zadatak ovog tipa.
  • Star – nije baš matrica :), na prvu može uplašiti, ali nakon malo razmišljanja…
  • Pattern transformation – mnogo smjerova, ali jako male dimenzije, u prijelazu možemo birati cijelu masku sljedećeg retka!
  • EEPROM – Izborne pripreme 2007.
  • Tiles – praktički isti zadatak kao Bugs Integrated, Inc. sa CEOI 2002. – dakle, ova je stvar bila korištena i prije 16 godina, ali samo troje ljudi je tada riješilo zadatak na CEOI-u.
  • Poligoni – Izborne pripreme 2013., jedan od težih zadataka iz moje radionice.