Nabrijavanje za HONI, drugi dio

Nastavljamo s podsjećanjem na najteža HONI kola svih vremena na svijetu.

Evo jednoga od njih:

http://hsin.hr/honi/arhiva/2012_2013/kolo5_zadaci.pdf

(testni primjeri: http://hsin.hr/honi/arhiva/2012_2013/kolo5_testpodaci.zip)

Od zadnja četiri zadatka (5-8), samo dva su bila riješena na natjecanju, svaki od troje ljudi. Ipak, brutforsima su se mogli dobiti djelomični bodovi. I ovo je dobar trenutak da istaknemo…

Pravilo natjecateljskog programiranja #3: Zbrutaj.

Bez obzira radi li se o simulaciji ili pravom natjecanju. Na natjecanju brutfors redovito čini razliku između medalje većeg i manjeg (ili nikakvog) sjaja, a simulaciju čini boljom i ozbiljnijom. I poslije, naravno, ne zaboravimo upsolving.

(Jezikoslovci još nisu složni oko imperativa, a bome ni infinitiva glagola zbrutati. Neki bi rekli izbrutati, slično kao izbaciti ili ispričati. Nema jezičnog opravdanja za ispuštanje slova i, pa se glasovna promjena izbrutati -> zbrutati u pravopisu opravdava činjenicom da je ionako riječ o žargonu, da čak ni osnovni oblik brutati ne koristi nitko normalan i da će se na hrvatskoj televiziji prije izgovoriti Bolzano-Weierstrassov teorem o konvergenciji nego to, pa onda koga briga. Što se tiče imperativa, neki lingvisti protive se obliku zbrutaj i predlažu “simpatičniji” oblik brutni. No taj oblik dolazi od svršenog glagola brutnuti, a ne od nesvršenog brutati. Kao što nije isto skočiti i skakati. Rasprave još traju i nadam se da će novi pravopis biti jasan po tom pitanju.)

Nabrijavanje za HONI, prvi dio

Jučer sam dobio mail koji je započeo na sljedeći način:

Dragi svi,

“it’s the most wonderful time of the year”, odnosno, kreće nova sezona HONI-ja.

U potpisu su Paljak i Kile pod čijim će palicama nastajati ovosezonska kola.

Očekuju se manje promjene u strukturi i bodovanju zadataka na temelju zapažanja i povratnih informacija nekih natjecatelja. Ideja je da zadnja tri zadatka budu poredana po abecedi (a ne po težini) i da nose jednak broj bodova. Testni primjeri na zadnja četiri zadatka trebali bi biti podijeljeni u podzadatke kao na HIO-u. Težine zadataka trebale bi ostati iste kao dosad. Za svaki full score na nekom kolu, Paljak i Kile otplesat će pet minuta stepa na otvaranju državnog.

Ok, ovo zadnje nije iz provjerenih izvora.

A da nam još mjesec dana ne prođe u neistrpljivom iščekivanju prvoga kola, da ne gledate nervozno u datum na mobitelu i da ne lupate ljutito po zidnom kalendaru jer još nije HONI, imam nešto za vas.

Blogaritam ekskluzivno predstavlja Najteža HONI kola svih vremena na svijetu, a kao prvu simulaciju trebamo riješiti sljedeće kolo:

http://hsin.hr/honi/arhiva/2008_2009/kolo1_zadaci.pdf

(testni primjeri: http://hsin.hr/honi/arhiva/2008_2009/kolo1_testpodaci.zip)

To je kolo bilo toliko teško da zadnja tri (od šest) zadataka nisu bila uopće riješena na natjecanju, osim jednog od tih triju zadatka koji je uspio riješiti samo Goran Žužić, tada jedan od najboljih pet srednjoškolaca na svijetu.

Danas su natjecatelji nešto bolji pa će vjerojatno riješiti više. Rješavajte sve zadatke, pravite se kao da ste na natjecanju. (Bez glazbe i mobitela, od simulacije napravite mali ritual. To vrijedi i općenito: svakodnevne stvari, obroke, šetnje, sitne poslove, treba pretvoriti u rituale. Disciplina, urednost i briga o detaljima smanjuju rastresenost i povećavaju usredotočenost, čime bivamo sretniji.)

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

Tip of the day: Stjepanovi snippeti

Kad naučite Python i počnete ga koristiti u stručne ili znanstvene svrhe, više nikada nećete napisati nijedan algoritam: jednostavno ćete iskoristiti neki od desetak tisuća dostupnih modula. Sve je već napisano, čemu duplicirati kod? Malo pretjerujem, naravno, ali nije ovo daleko od istine. Proguglajte malo Python libraries. Naravno, na natjecanju je dostupna samo standardna Python biblioteka, ali natjecanja ćete ionako brzo prerasti.

A do tada, ako se za natjecanja pripremate u C++u, bacite oko na “module” Stjepana Glavine:

https://github.com/stjepang/snippets

Dosta korisno za razne online zadatke, čisto i jednostavno za ubaciti u kod (plug & play). Readme na dnu stranice sve objašnjava. Ako niste upoznati s namespaceovima, primjer korištenja možete vidjeti npr. u rješenju skloniste_flow.cxx u folderu suboptimalnih rješenja s Izbornih priprema (http://hsin.hr/pripreme2019/zadaci/rjesenja.zip).

Naravno, budući da ovo nemate na natjecanjima, ideja je i da vam posluži kao referenca da naučite kako što implementirati. Kad smo već kod toga, prilažem i jedan sličan, stariji dokument, tzv. Zagreb reference (implementacije raznih algoritama) autora Lovre Pužara.

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.

Poluosvrt na izborna natjecanja

Za razliku od prijašnjih godina kada se rješavao manji broj zadataka u nešto manjem vremenu, IP ove su godine bile simulacija IOI-a: dva dana po tri zadatka u pet sati. Mislim da su zadatci ispali dobro pogođenih težina i da su pokrili mnoga područja, sva najvažnija (K-ti – strukture podataka, Parking – dinamika, Pokvareni – konstrukcijski zadatak, Izazov – nerješivi zadatak, Sklonište – grafovi, Vezuv – stringovi). Slučajno je tako dobro ispalo, jer teško je to naštimati – dobri zadatci ne padaju s neba. Svaka čast Paljku, Tonku, Bradaču i Bradaču. Između ostalog i na obaranju hrvatskog rekorda za najveće vremensko ograničenje (zadatak Izazov – 15 sekundi), čime je srušen rekord koji su držali zadatci iz devedesetih, a iznosio je impresivnih 10 sekundi.

U rješenjima smo ovaj put (možda i prvi put na hrvatskim natjecanjima općenito?) stavili i folder s alternativnim i suboptimalnim rješenjima na koja se referiraju opisi algoritama. I iz njih se može nešto naučiti.

Još jedan novitet koji se pojavio već na Državnom, a vezan je za moju čudnu privrženost jeziku, jest unaprijeđena terminologija u tekstovima (PDF). Nisu više test podatci nego testni primjeri, a sampleovi/dummyji nisu više primjeri test podataka nego probni primjeri. Jer “test podatci” em je jezično manjkavo (test je imenica, ali je upotrijebljena kao pridjev?!), em je nelogično govoriti o test podatku ako on sadrži, recimo, milijun brojeva – zar nije to milijun podataka? Nego: testni primjeri i probni primjeri, kratko i jasno.

Sad ću možda malo pretjerivati, ali nije to jedino jezično poboljšanje. Naime, kao što nas je jedan lektor u nekom drugom kontekstu upozorio, u sekciji ulaznih podataka dosad smo stalno pisali “U prvom retku nalazi se cijeli broj N” ili “U drugom retku nalazi se N brojeva” itd. Jezik ne voli redundanciju pa ovo nalazi se nije potrebno, dovoljno je koristiti glagol biti. Tako sada (ako se sjetim ispraviti) pišemo “U prvom su retku prirodni brojevi N i M” ili “U drugom je retku N brojeva” itd. Ništa se ne nalazi, naprosto jest.

Možda ću poslije još pisati o samim zadatcima, tj. o nekom od njih. Ovo je ionako samo poluosvrt. Što god to značilo. Evo jedan life hack: ako želite zvučati skromno ili manje ozbiljno, dodajte prefiks polu- ispred toga što predstavljate. Na primjer, ako niste sigurni u svoju ideju, recite da imate poluideju, predložite polurješenje. Ako niste baš pravi matematičar, recite da ste polumatematičar. Nemojte reći ljudima da su nepismeni, nego možda polupismeni ili poluobrazovani. Ili da lonac nije razbijen nego polupan. Eto, toliko za danas.

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.