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.

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