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.

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

Digresija: potapanje brodova

Prije više od deset godina, točnije davne 2007. godine, sunce je sjalo, ruže su mirisale, Hrvatska se pripremala za organizaciju IOI-a, a državno se zvalo DMIH i održavalo se u hotelu Porin u čudnom manje poznatom dijelu Zagreba. (Taj je hotel nedavno bio korišten kao prihvatilište za migrante.) Bio je organiziran neki autobus u neko određeno vrijeme, ali bilo je ljepše i poetičnije na državno natjecanje ići tramvajem do Zapruđa pa pola sata pješice, ili u Zapruđu uhvatiti neki od rijetkih polugradskih autobusa. Isprobati malo divljine i života na rubu. To je ok, štedjelo se za IOI.

Autori zadataka tada su bili legende Lovro Pužar i Luka Kalinovčić, pomagao im je sistemski majstor Marko Ivanković (ono što je danas Matej), a natjecanjima je potpuno dominirao Goran Žužić, i u smislu rezultata i u smislu energije i šarma. Dok su naši kolege prije natjecanja pričali nešto o clockanju (brut/heuristika i nakon 0.9 sekundi ispiši najbolje pronađeno rješenje), Goran je zabacio kosu i komentirao: “Ja sam prva podskupina, nemam ja tu kaj clockat.” Lijepo je to bilo vrijeme, rezultatima je dominirala moja V. gimnazija, koja je do danas potpuno utihnula, izgleda da su prešli na zen budizam.

Na probnom natjecanju tada se pojavio interaktivni zadatak s potapanjem brodova. Trebalo je napisati program koji igra potapanje brodova, tj. pogađa sve protivnikove brodove na 10 x 10 ploči u što manje pokušaja, pri čemu nakon svakog pokušaja program sazna je li brod pogođen. Ima sličnih zadataka online, primjerice:

CodeChef verzija

TopCoder verzija –> Analiza rješenja

THE Analiza

Ono što me zapravo motiviralo da napišem ovaj post jest rješenje Gorana Žužića koje nam je ispričao nakon probnog natjecanja. Za razliku od većine nas koji smo, nakon što bismo prvi put pogodili dio nekog broda, odmah nastavili gađati oko pogođenog polja da bismo pogodili cijeli brod, Goran je radio malo drugačije. On je na početku napravio 20 ili 30 potpuno slučajnih hitaca po cijeloj ploči, neovisno o tome je li neki od njih bio uspješan. Tek potom gledao je koji su hici bili uspješni i prema tome gađao gdje su čitavi brodovi.

Vjerojatno se on toga više i ne sjeća. Nije važno je li to najbolja strategija – ovaj je post ionako digresija. No meni se takva strategija jako svidjela, više u psihološkom nego u matematičkom smislu. Ima taj duh robusnosti, ne lijepi se za prvi pogodak, nego u prvoj fazi decidirano i pomalo nemarno isprobava 30 slučajnih stvari prije nego što se u sljedećoj fazi počne fokusirati. Životna lekcija, eto što je to.

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:

Izvor svih zadataka

Veliki američki pjesnik Walt Whitman napisao je sljedeći stih:

Stop this day and night with me

and you shall possess the origin of all poems.

Bilo bi divno imati origin of all poems, izvor svih pjesama. Ali mene zanima izvor svih zadataka – matematičkih i informatičkih, primjerice. Ne mislim na izvor kao arhivu zadataka, web stranicu ili knjigu. Nego, kao Walt Whitman, mislim na ono mjesto u glavi – možda je bolje reći stanje – iz kojeg u naletu inspiracije izviru svi prošli i budući zadatci, kao i njihova rješenja. Bio bi to ultimativni doseg svakog rješavača ili autora zadataka. U ovoj objavi ukratko bilježim svoja dosadašnja nastojanja u navedenom smjeru.

Da bi se otkrio izvor svih zadataka, najprije treba analizirati svaku pojedinu riječ ove fraze: izvor, svih, zadataka. Jer svaka od njih je važna: izvor kao metaforičko ishodište koordinatnog sustava naše potrage, svih kao ključni logički kvantifikator (ne nekih, nego svih!), i zadataka kao objekt, a ujedno i subjekt naše potrage. Kao početna točka može nam poslužiti Hrvatski jezični portal, koji navedene riječi definira na sljedeći način:

Izvor m: 1. mjesto gdje voda (nafta, plin i sl.) izlazi na površinu zemlje [izvor rijekemineralni izvor]; vrelo, vrutak 2. pren. mjesto odakle što dolazi, potječe [izvori bliski vladi] 3. dokument, djelo ili pojava koji služe za znanstveno istraživanje.

Sav (svȁ ž, svȅ srzam. prid. 〈G svèga, A svèga/sȁv (za neživo), D svèmu, L svȅm/svèmu, I svȋm/svíme〉: 1. koji je bez iznimke [sav svijetsvi ljudisve plemstvo]; cjelokupan 2. cio, čitav shvaćen u cjelini [sve selo cijelo/čitavo] 3. cio, čitav shvaćen kao ukupnost svojstava [sva ta sirotinja, uza svu nevolju] 4. u raznim kontekstima u zn. jako, vrlo, u velikoj mjeri obuzet (sam) čime [sav sam očajansav sam rasprodanžarg. vrlo sam zauzet poslom, traže me na sve strane; sav (je) pozelenio zavidan je; (slika zelenila u licu kao znak zavisti i bolesnog stanja); sav (je) usplamtio, sav (je) uzdrhtao jako se uzbudio zbog čega; ob. od želje za čim, znatiželje, pohlepe, zavisti] 5. (sr) (kao objekt u rečenici) ukupna količina, potpuna cjelina bez ostatka [prodao sam sve].

Zadatak  m 〈G -tka, N mn -áci, G zàdātākā〉: 1. ono što se kome stavlja u dužnost da radi ili izvrši, ono što treba izvršiti; dužnost, cilj, program 2. ono što treba riješiti, problem koji treba dovesti do rješenja pravilnim postupkom.

Primijetite da svaka riječ ima više mogućih značenja, što nije nimalo slučajno. No ako nam ova jezična džungla ne pomogne u potrazi, iskustvo hoće. Jer u srednjoj školi često sam svog prijatelja iz razreda, Franu Kurtovića (također informatičara), tražio da mi ispriča neki dobar zadatak. On bi svaki zadatak znakovito započeo istom riječju i znao sam da ta riječ ima veze s izvorom svih zadataka. Frane bi, naime, svaki zadatak ispričao iz perspektive “imaš”. Na primjer: “Imaš niz brojeva…”, ili, “Imaš stablo…”, ili, “Imaš tablicu…”, ili, “Imaš N gradova…”, ili, “Imaš sto tisuća upita…”, ili, “Imaš maramicu?”, i slično. Frane je tako nehotice otkrio zajednički nazivnik svih zadataka.

Kad sam mu ukazao na zanimljivu činjenicu da svaki zadatak priča tako da najprije kaže “imaš”, Frane je malo promijenio spiku, pa njegovi zadatci više nisu izvirali iz iste riječi. Glasili su: “Dobiješ niz…”, “Dobiješ usmjereni graf…”, “Dobiješ matricu…”, i tako dalje. No ovo su tek početničke spoznaje. Poslije, bitna prekretnica u mom autorskom razvoju bila je spoznaja da zadatak ne mora početi sa “imaš” ili “dobiješ”. Tada se preda mnom otvorio cijeli svijet mogućnosti.

U želji da saznam najčešći izvor naših zadataka, tj. riječ kojom zadatak najčešće započinje, odlučio sam napisati program koji pronalazi tu riječ tako da parsira s weba sve hrvatske zadatke. Program sam odlučio podijeliti s vama. (Ključni dio, kao i ispis rezultata, prepustio sam strukturi bitset kao što možete vidjeti.)

Rezultati su zanimljivi i objavit ću ih u nekom od idućih postova. Ne mogu prvog travnja, mislili bi da je zajebancija.

Izazov godine: kvinijska križaljka

Dan prije američkih predsjedničkih izbora 1996., New York Times objavio je križaljku u kojoj je jedan od pojmova bio opisan kao sutrašnja glavna vijest: ******* ELECTED. Je li autor križaljke predvidio izbornog pobjednika?

Genijalnost je bila u tome da se križaljka mogla riješiti na dva jednako ispravna načina: kao novi predsjednik mogao je stajati i CLINTON i BOB DOLE, a da ostali pojmovi i dalje odgovaraju svojim opisima. Npr. black halloween animal ispao je CAT u slučaju CLINTON, a BAT u slučaju BOB DOLE. I tako dalje. Križaljku je sastavio matematičar Jeremiah Farrell.

Best-crossword-puzzle-ever

Dva rješenja ove križaljke razlikuju se u jednom pojmu. Može li više?

U tome je uspio još jedan genijalac, filozof Daniel Dennett. Sastavio je križaljku u kojoj se dva rješenja razlikuju potpuno, dakle u svim pojmovima. Osoba A i osoba B mogu ispravno riješiti križaljku, a da im se, kada usporede rješenja, nijedna riječ (ili čak nijedno slovo) ne podudara, iako za svaki opis i A i B imaju dobar pojam na odgovarajućem mjestu. Križaljku je nazvao kvinijskom (Quinian crossword puzzle) jer ju je upotrijebio da bi ilustrirao zamisao filozofa W. V. O. Quinea o nejednoznačnosti prijevoda (što ovdje nije bitno).

Dennettova prva križaljka izgledala je ovako:

Screenshot_2019-03-09 kolo2_zadaci pdf

Across

  1. Suck the resources out of
  2. Epoch
  3. Sleep furniture
Down

  1. Retentive membrane
  2. Earlier
  3. For some kids, a best friend

Nije baš lagana, pogotovo nama čiji je vokabular engleskog jezika ograničen. Meni je trebalo dosta guglanja da bih pronašao oba moguća rješenja, a pomogao je i rječnik sinonima. Otkrit ću vam da retentive membrane (1 okomito) može biti web ili sac.

Poslije je unaprijedio svoju kvinijsku križaljku, tj. sastavio bolju:

Screenshot_2019-03-09 Intuition Pumps And Other Tools for Thinking - Dennett - Intuition Pumps pdf

Across

1. Dirty stuff
5. A great human need
6. To make smooth
7. Movie actor

Down

  1. Vehicle dependent on H2O
  2. We usually want this
  3. Just above
  4. U.S. state (abbrev.)

(Oba) rješenja poslije ću otkriti u komentaru. No glavni je cilj ovog posta zadati jedan mnogo teži i ozbiljniji izazov. Vjerojatno ste ga dosad i naslutili.

Sastavimo prvu hrvatsku kvinijsku križaljku.

Sastaviti običnu 3 x 3 ili 4 x 4 križaljku nije naročito teško. No zahtijevamo li da križaljka ima još jedno rješenje, u pojmovima različito ali također ispravno tj. u skladu sa zadanim opisima, problem postaje brutalan. No Dennett ga je riješio, pa valjda možemo i mi. Hrvatski jezik, zbog pravilnije izmjene samoglasnika i suglasnika, pogodniji je od engleskog za sastavljanje križaljki – što možete uočiti i uspoređujući broj “crnih” (neiskorištenih) polja u prosječnoj hrvatskoj i prosječnoj engleskoj križaljci.

Rješenje će sigurno uključivati mnogo mašte u povezivanju naizgled nepovezanih pojmova istim opisom, ali problem ne bih spominjao na ovom mjestu kad ne bih mislio da može imati veze i s programiranjem. Imam neke ideje o smjerovima u kojima bi se moglo ići, ali zasad je bolje da ne utječem ni na koga. Bit će još koji post o tome, a do tada možda netko pametniji od mene ovo i uspije.

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.