Kamo ide Blogaritam?

Došlo mi je da napišem nešto i o njegovu životu.

Mali Blogaritam ima tri i pol godine. Rođen je u Zagrebu, u knjižnici jednog FER-ovog zavoda na trećem katu, na jednom sivom laptopu, na prvi april 2018. godine. Negdje sam već napisao da je naš svemir, prema nekim izračunima i proračunima, također nastao na prvi april. On je Božja neslana šala. Ali Blogaritam, on je na taj prvi april rođen sasvim slučajno, nismo planirali, nismo pazili. Dogodilo se.

Blogaritam je od rođenja pokazivao čudne sklonosti: pisao je objave za informatičke natjecatelje, rješavao zadatke. Kako je rastao, tako je sve više pisao i o matematici, natjecanjima općenito, o mojim sjećanjima i osobnim promišljajima, zajebavao se, očijukao i koketirao s filozofijom – ili onim što on zove filozofijom – i njezinim prijateljicama. Trenutačno se nešto dopisuje s poezijom i glazbom, šalje im smajliće i srčeka. Svašta ga privlači, orijentacija mu varira, nije nimalo tradicionalan. Da ima konzervativne roditelje, dobio bi već po nosu.

Još je u fazi istraživanja, a tako i treba biti, tek je počeo živjeti. Jako ga volim, kupujem mu poklone. Nije imao ni pet mjeseci kad je dobio domenu (blogaritam.com). Bojim se da ga ne razmazim. Sad me moljaka da mu kupim šminku. Kakvu šminku, pitam ga. “Pa želim biti lijep!” kaže mi i traži boje, logotip, ikonicu, svašta nešto. Ja sam minimalist, ali njega čitaju i još neki ljudi – nema ih mnogo, ali su mu dragi – i želi se srediti. Ne znam što ću s tim. Razmislit ću, možda ga iznenadim i razveselim. Život je pred njim i pun je energije. Neka uživa, neka ide na tretmane ljepote, neka se maže maskom za lice, ide na masažu i u saunu. Za peti rođendan kupit ću mu bicikl, a za petnaesti motor. Od osamnaste neka radi što hoće, baš me briga, ali neka mi se javi tu i tamo, brinem.

Kategorizacija blogaritamskih objava

(Ovaj je blog pun digresija; u skladu s time, evo jedne digresije i na početku ove objave – koja, zapravo, ne bi trebala sadržavati digresije jer je njezin smisao u tome da ljudi vide gdje je što. Svejedno, odvucimo i ovdje malo pažnje u nepovrat! Dakle: dosad sam pisao riječ post (u kontekstu blog posta), znajući da je riječ objava pomalo neobična i sadrži (ovdje sasvim nepotrebne) religijske asocijacije. Sad ću ipak u duhu jezika pisati objava, ljepše je. Valjda me i ono malo čitatelja neće zbog toga napustiti.)

Blog sam pokrenuo na prvi april 2018. godine (je li taj datum bio slučajan ili nije, valjda je vrijeme već pokazalo). Krenuo sam pišući o konkretnim zadatcima s informatičkih natjecanja i savjetima za njihovo rješavanje pa su tako nastale kategorije objava poput Tip of the day, Tema dana, Zadatak dana i slično. S vremenom su se pojavile i općenitije objave pa sam napravio i kategorije Razno, Matematika i Natjecanja. Na blogu je sve manje bilo korisnih, stručnih savjeta, a sve više metasavjeta, svakakvih zanimljivosti, filozofije i zajebancije; blog se pretvarao u ispušni ventil mojih misli, kao i svaka dobra umjetnost. (Da, ovo zadnje je šala.) Postojeće kategorije postale su nekako neprikladne: često nema bitne razlike između Teme dana, Zadatka dana i Tip of the day (koji pokriva svašta, od stručnih do metasavjeta), dok su više filozofske objave rasute po kategorijama koje ih dobro ne opisuju.

Odlučio sam stoga napraviti bolju kategorizaciju i podijeliti objave prema novim kategorijama kao u donjem popisu, gdje su objave u svakoj kategoriji poredane kronološki. Podjela, naravno, nije savršena i neke objave su na rubu, tj. mogle su biti i tamo i vamo. Nove kategorije u trenutku pisanja ovog teksta još nisu implementirane u sam blog u svrhu filtriranja objava i slično, ali vjerojatno će biti u nekom trenutku, a i ovaj popis možda ću povremeno ažurirati poveznicama na nove objave. Ako neka poveznica slučajno ne radi ili vodi na krivu objavu, slobodno mi javite, bit ću jako zahvalan.

Algoritmi i zadatci
Put među permutacijama
Tip of the day: Odaberi srednji
Nepotpuno stablo
Kružni intervali
Zadatak dana: Cow School
Tip of the day: disjunktne maske
Tip of the day: logaritamska++
Tema dana: pseudošuma
Zadatak dana: kineski poštar
Zadatak dana: GTA
Tema dana: (m)nogometni problemset
Tip of the day: tablica je bipartitan graf
Tip of the day: permutacija == ciklusi
Zadatak dana: ABCD
Tema dana: podijeli pa vladaj
Tema dana: duguljaste matrice
Tip of the day: if manji if veći
Tema dana: mravlji problemset
Zadatci sa studentskog 2018.
HONI i rješenje kao niz zamjedbi
Dva analogna zadatka
Tip of the day: granice intervala
Tema dana: konstrukcijski zadatci
Dvije stablaste fore
Tip of the day: AB prebrojavanje
Logaritamska struktura i tournament stablo
Tip of the day: broj najkraćih putova i Dijkstrin DAG
Svako stoblo je stablo, ali nije svako stablo stoblo
Kaj su rješavali naši stari
Tema dana: glazbeni problemset
Tema dana: teorija brojeva
Pandemijski problemset
Tema dana: neočekivani graf
Neočekivani graf u još dva zadatka sa stringovima
Tema dana: riješi offline
Tema dana: skakanje po neboderima (ili: Ne pokušavajte ovo kod kuće)

Natjecateljsko programiranje i produktivnost
Uvodni post
Tip of the day: upsolving
Adhocness level
Tip of the day: Codeforces blogovi
Tip of the day: pravilno tipkanje
Tema dana: clear thinking
Tip of the day: CSES Problem Set
Tip of the day: atomske navike
Tip of the day: code review
Tip of the day: YouTube kanali o natjecateljskom programiranju
Kako efikasno vježbati?
Tip of the day: Stjepanovi snippeti
Nabrijavanje za HONI, prvi dio
Nabrijavanje za HONI, drugi dio
Top pet novogodišnjih optimizacija
Algoritmi u Pythonu
Tip of the day: Linux
Iza kulisa HONI-ja
Tip of the day: testiranje zadataka sa HSIN-a
Tip of the day: testiranje na pythonovski
Tip of the day: testiranje
Tip of the day: stari bilteni
Kako vježbati?
Top dvije novogodišnje optimizacije produktivnosti

Iskustva s natjecanja i ostala sjećanja
EJOI 2018. počinje!
Poluosvrt na EJOI 2018.
IOI, IPSC i nestandardni zadatci
Izvor svih zadataka
Digresija: potapanje brodova
Poluosvrt na izborna natjecanja
HONI je bio odličan
Informatika i dopamini
Kako organizirati natjecanje u doba korone
Poluosvrt na vrijeme kada je natjecanje bilo offline
Kako to ide
Doživjeti stotu
Natjecanje je više od natjecanja
Državno i tako dalje

Matematičke, algoritamske i slične zanimljivosti
Matematika i (neki) matematičari
Digresija: Dedekindovi brojevi
Dokaz ostavljamo čitateljici za vježbu
Izazov godine: kvinijska križaljka
Zadatak dana: kazaljke sata – ili – kad se sve poklopi
Tip of the day: svi su oni isti
AISports i zaigrani botovi
Zadatak dana: Easter eggs ili Čudnovate permutacije uskršnjih jaja
Kampovske igre – članak iz 2011.
Digresija: taksi dijalog
Znanost i algoritmi
Matura, rang liste i College Admissions Problem
Digresija: matematičko-književne preporuke
Ljetna poslastica: dvadeset i jedan (“židovski”) matematički zadatak
Statistika i (neki) statističari
Everybody’s gangsta until you invert
Znanost i algoritmi, drugi dio
Komunikacijska složenost – ili – kako zakodirati partiju šaha
Refreshaj koliko hoćeš
Koliko sam dobro trčao (prvi dio)

Filozofija?
Digresija: i nula je broj
Digresija: Matematički radio
Može li računalo misliti?
Male tajne velikih brojeva
Jezik i umjetna inteligencija
Digresija: suvišnost matematike i jedna nova igra
Knjiga koja se čita godinama
Beskonačno mnogo vremena
Argument u prilog postojanju dobrog i lošeg ukusa
Slavko Kolar i različite varijante (ne)ispijanja ljubavnog napitka
Dilema istraživanja i iskorištavanja

Ovaj popis sadrži svih dosadašnjih 98 objava. Da, tek sad sam uočio da je ovo devedeset deveta objava. Bilo bi mnogo bolje da je stota. Jebiga.

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.

Zadatak dana: kazaljke sata – ili Kad se sve poklopi

Sjećate li se prije godinu dana ugašene društvene mreže Google+? Ondje je nekad u 2017. godini Veky (docent Vedran Čačić s PMF-a) podijelio sljedeći zadatak:
 
Na analognom satu na kojem se sve tri (sat, minuta, sekunda) kazaljke pomiču kontinuirano, hoće li se ikad dogoditi da se sve tri nalaze unutar kuta od 1°?

Traži se vrijeme strogo između 0:0:1 i 11:59:59.

Kada se Google+ gasio, preuzeo sam arhivu svoje aktivnosti i tako došao i do tog zadatka i svojega rješenja koje sam bio napisao u komentarima. Evo tih komentara:
 
[Adrian]
3:16:16.3 i 8:43:43.7, dobiveno simulacijom po kutnim sekundama u Pythonu.
 
[Veky]
Hm, zanimljivo. 🙂 Ali nisam baš mislio na simulaciju, bar ne tako grubu. Probaj odgovoriti jesu li ikad unutar pola stupnja onda. 🙂
 
[Adrian]
1 kutna sekunda = 1/60 kutnih minuta = 1/3600 kutnih stupnjeva, što je vrlo fina simulacija. Poanta je da se može simulirati proizvoljno precizno, s brzinama kazaljki x, 12x i 12*60x.
 
[Veky]
Kad je već tako fina, odgovori na moje pitanje. 😀
 
(Ovdje sam bio zapeo. Programirao sam sve precizniju i precizniju simulaciju, kazaljke su se kretale beskonačno sporo, ali kut je uvijek ispadao mrvicu veći od pola stupnja. Vjerovao sam da je riječ o manjku preciznosti pri računanju realnim brojevima i da pravi kut iznosi točno pola stupnja, ali nisam bio dovoljno siguran da bih išta odgovorio. Sjetio sam se toga nakon više od godine dana pregledavajući history kad je Google+ upozorio da će se ugasiti.)
 
[Adrian]
Da odgovorim na ovo dok se Google+ ne ugasi 🙂 Simulacijom sam dobivao razliku toliko blizu 0.5 stupnjeva (ali ipak veću, nešto tipa 0.500x…) da sam mislio da se u stvarnosti postiže točno 0.5, ali da simulacija nikad ne može dobiti taj egzaktan položaj. Danas sam izguglao matematičko rješenje (manje je pametno nego što sam mislio) i vidio da najmanja razlika iznosi 360/719 = 0.5007 stupnjeva. Znači, simulacija je točno odgovarala na pitanje. Pouka: vjeruj kompjuteru čak i kad se čini da griješi.
 
Matematičko rješenje ostaje tajna – njega ostavljamo čitateljici za vježbu. Ali poruka je jasna.
 
Kao bonus, podijelit ću s vama dva članka o kazaljkama sata, objavljena prije mnogo godina u časopisu Matka. Prvi je članak Vladimira Devidéa iz 2000. godine o vjerojatnostima poklapanja kazaljki, a drugi je moj članak iz 2008. godine o pravilnim prikazima na digitalnom satu. Zanimljivo je da je vjerojatnost popuno različitih stvari u oba članka ispala jednaka – poklopila se. Slučajno ili ne?
 

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