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.

Neočekivani graf u još dva zadatka sa stringovima

Javlja mi Kišić da se jučer na Open Cupu pojavio super zadatak za temu iz prethodnog posta. Zadatak možete pronaći ovdje, vrlo je lijep, i još jedan dokaz proročke snage Blogaritma.

A sjetio sam se onda i jednog svog zadatka iz iste “kategorije”, također sa stringovima, koji se neočekivano svodi na graf i koji sam začudo zaboravio u prethodnom postu. To je zadatak Wordplay sa Spoja, meni je dobar, a i ljudima se svidio.

Kad smo već kod Spoja, znate li što informatičar radi u subotu navečer? Pa na Spoju je! — A znate li što radi kad dobije WA (Wrong Answer)? Radi ovo.

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.)

Kaj su rješavali naši stari

(Naslov je prilagođen iz imena poznate vrbovačke turističke manifestacije “Kaj su jeli naši stari”.)

Stare Lukine materijale već sam dijelio ovdje i ovdje. Podijelit ću sada i preostala dva dokumenta koja imam:

Luka Kalinovčić: Sweep

Luka Kalinovčić: Dinamičko programiranje

Iz potonjih je zadataka Goran Žužić (naš najuspješniji srednjoškolski natjecatelj dosad) nekad davno naučio dinamiku.

A podijelio bih i članak o FUI koji je Frane Kurtović prije deset godina napisao za časopis PlayMath koji smo tada objavljivali mi, učenici V. gimnazije:

Frane Kurtović: Formula uključivanja i isključivanja

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.

Tip of the day: broj najkraćih putova i Dijkstrin DAG

Nakon guglanja o tome kaže li se putovi ili putevi, još uvijek nisam siguran što je ovdje ispravno. Kažu da su putovi konkretni, a putevi apstraktni. Za putove u našem smislu, tj. u smislu teorije grafova, može se reći i jedno i drugo. Sigurno su apstraktniji od šumskih putova, ali i konkretniji od, recimo, puteva mudrosti. Odlučio sam se za “konkretnu” varijantu: putovi. (Za one koji se zgražaju nad ovim jezičnim pseudoproblemima: nevažno je, naravno, ali je zabavno, i stvar estetike – shvatite to kao formatiranje teksta.) Dakle: putovi.

Floyd-Warshallov algoritam jedan je od najljepših algoritama koje znam jer u svojih samo 5-6 redaka koda krije mnogo mudrosti (puteva mudrosti, jel). Kao što učinak samog algoritma nije nimalo očit, tako možda nije očito ni da se algoritam može jednostavno nadopuniti tako da izračuna i koliko ima najkraćih putova između svakih dvaju vrhova.

Probajte to sami smisliti. Nije teško, ali je malo tricky. Recimo, prvi odgovor (označen zelenom kvačicom) na Stack Overflowu nije ispravan. Točno rješenje dano je u odgovoru ispod njega (kod počinje s procedure FloydWarshallWithCount ()).

Naravno, mana Floyd-Warshalla je složenost od O(N^3) i zato, osim za guste grafove, prednost ipak ima Dijkstrin algoritam koji se također može nadopuniti tako da računa i broj najkraćih putova.

Evo zadatka gdje to možete isprobati: Šetnja2 (IBT 2010.).

Korišteni bridovi koji se nalaze na najkraćim putovima iz nekog fiksnog vrha čine tzv. Dijkstrin DAG. (Ako su najkraći putovi jedinstveni, riječ je o stablu.) On ima glavnu ulogu u zadatku Najkraći (zadatak dana!) s HONI-ja 2008. (Ako vam je dosad promaklo, rješenja svih HONI-ja možete pronaći ovdje.) Update: još dva zadatka predložio je Marin u komentaru dolje.

Tip of the day: AB prebrojavanje

Jučer se na Hrvatskoj informatičkoj olimpijadi pojavio zadatak Ljepotica autora Ivana Paljka. U zadatku se traži zbroj velikih brojeva s određenim svojstvom, koji se nalaze između dvaju velikih brojeva A i B (koji imaju do 1000 znamenaka). Zadatke koji odgovaraju navedenom kalupu obično rješavamo tzv. AB prebrojavanjem.

Riječ je naprosto o dinamičkom programiranju koje je zbog pojavljivanja u ovom specifičnom obliku dobilo posebno ime. Zamišljamo da veliki broj gradimo znamenku po znamenku te nas u nekom trenutku zanima na koliko načina možemo napisati broj do kraja (ili zbroj tih mogućnosti, ili nešto drugo, ovisno o zadatku). Poanta je da nam za odgovor na to pitanje nisu bitne sve dosad odabrane znamenke, tj. stanje je moguće opisati manjim brojem parametara, od kojih je jedan redovito pozicija na kojoj se nalazimo (tj. redni broj trenutačne znamenke), a drugi ovisi o zadatku, tj. o traženom svojstvu broja koji konstruiramo (npr. pamtimo broj preostalih promjena u zadatku Ljepotica).

Da bismo se ograničili na brojeve iz intervala [A, B], treba nam još jedan parametar: jesmo li dosad odabranim znamenkama već osigurali da će broj koji konstruiramo biti strogo manji od B, ili on još uvijek može biti jednak B, tj. podudaraju li se dosadašnje znamenke sa znamenkama broja B. U stanja gdje bismo premašili B nećemo ni ući, a to osiguravamo upravo iz navedenog parametra, znajući moramo li pri odabiru trenutačne znamenke paziti da ne premašimo istu znamenku u broju B (ako smo dosad birali iste znamenke kao u broju B).

Takva dinamika ne vodi računa o donjoj granici A, ali poslije samo provedemo isti algoritam s tom granicom da bismo oduzeli brojeve manje od A koje smo prethodno ubrojili. Drugim riječima, računamo koliko ih ima do B, minus koliko ih ima do A – 1, čime dobivamo koliko ih ima od A do B.

Osim ovih generičkih ideja, svaki zadatak ovog tipa može biti na svoj način osobit i ponekad je potrebna još neka specifična dosjetka, kao npr. u zadatku Umnožak koji se također pojavio na HIO, desetak godina prije. Otprilike u to vrijeme i na HONI-ju se pojavio zadatak Trešnja ovoga tipa. Priču je moguće i malo okrenuti, pa tražiti N-ti broj koji zadovoljava neko svojstvo, kao u zadatku Sretni s IBT-a.

Tipičan zadatak za početnike bio bi npr. Sum of Digits – ovakve zadatke lako je debugirati jer je lako skodirati brutfors i izmišljati testne primjere. Još mnogo objašnjenja i zadataka dostupno je na webu ako tražite Digit DP. Primjerice: