HONI je bio odličan

U utorak navečer pitam nešto brata. On odgovara da nema vremena, mora završiti primjere za HONI. Kakav HONI, pa utorak je, kažem ja njemu. Ne ne, vremena se mijenjaju i rokovi se mijenjaju. Zadatci se više ne rade u zadnji čas, u sitne noćne sate s petka na subotu, kako je to ponekad znalo biti. Zato je i ispalo sve odlično, koliko čujem. Dobri tekstovi i sličice u tekstovima, kao i sami zadatci. I svaki je bio riješen.

Možda je neobično što su zadnja tri zadatka bila poredana obrnuto po težini. Zapravo su poredani po abecedi, a razlog je sljedeći – citiram Paljka:

Ova priča oko nizanja zadataka po abecedi je nastala zbog zamjedbe da naši olimpijci (i veliki i mali) imaju problema s procjenom težine zadataka. Njima se ovo isto činilo kao super ideja i dosta su vokalno to podržali. Moguće da smo zabrijali i da se eksperiment pokaže kao promašaj. Svejedno, mislim da se isplati probati.

Pod palicama Kileta i Paljka čak istoga dana objavljena su rješenja, važan dio cijele priče. Čitajte rješenja, iz njih se uči. Koliko sam vidio, ovaj put su napisana vrlo lijepo i opširno, a objavljeni su i kodovi nekih brutforsa. (Šteta je što za neka prijašnja natjecanja još uvijek nedostaju rješenja, uključujući prošlogodišnja HONI kola i neka osnovnoškolska natjecanja.)

U nedjelju nas čeka Studentsko gdje se priča okreće – dvojica malih zadat će zadatke velikima. Uz malu pomoć nas još većih. (Većih samo u starosnom smislu.) Tim malcima radoznalcima, izvanserijskim genijalcima, mi moramo još dvije-tri godine smišljati zadatke, a bolji su od većine nas autora. Tako ti je to kad želiš da natjecatelji budu izvrsni! Srećom, još uvijek smo u golemoj prednosti. Mi autori ne moramo skodirati rješenje za pet sati, možemo i za petnaest. Za ideje imamo pristup neograničenoj količini inspiracije iz opskurnih članaka na ruskom, kineskom i tadžikistanskom. Bolje im je da odu u školu stranih jezika. Pripremaju se za unaprijed izgubljenu bitku. Mwahahahaha.

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

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.

Dva analogna zadatka

“Matematičar je osoba koja vidi analogiju između teorema, još veći je onaj koji vidi analogiju između dokaza raznih teorema; još je veći onaj koji vidi analogiju između teorija. A možemo zamisliti i onoga, koji vidi analogiju među analogijama.” –– Stefan Banach

Budući da nisam veliki matematičar, ja samo vidim analogiju među informatičkim zadatcima. U ovom slučaju to su zadatak NLO sa subotnjeg HONI natjecanja, te nešto lakši zadatak Vandal s Državnog 2007., čija rješenja dijele sličan trik u načinu razmišljanja.

U zadatku Vandal riječ je o matrici-šahovnici velikih dimenzija u kojoj su pokriveni jedan red, jedan stupac, neka dijagonala u jednom smjeru i neka dijagonala u drugom smjeru. Zadana je samo dimenzija matrice i oznake pokrivenog retka, stupca i dijagonala, a treba izračunati koliko je bijelih, a koliko sivih polja šahovnice barem jednom pokriveno.

Budući da je na ulazu samo pet brojeva, većina nas je to rješavala “matematički”, hrpom formula i ifova. To je u teoriji izvedivo, ali je jako komplicirano i teško izvesti bez greške za sve slučajeve. (Kad počnete crtati slučajeve, što se sa čime siječe ili ne siječe, bit će vam jasnije.) Takvo rješenje radi u konstantnoj složenosti (bez petlje), što je za informatički zadatak rijetkost: zadatak s takvim rješenjem bio bi loš, tj. zapravo matematički. Srećom, u ovom zadatku to nije očekivano rješenje.

Na suprotnom ekstremu nalazi se jednostavno brute-force rješenje koje za svako polje laganim formulama provjerava je li pokriveno. Ono je sporo jer matrica ima N x N polja za N ≤ 107 pa ne stignemo proći po svim poljima.

Na sličnu situaciju nailazimo u zadatku NLO, gdje matricu pokriva nekoliko krugova. U geometriji je formulama moguće izračunati presjek/uniju dvaju krugova, možda čak i triju, no ovdje ih je 100 i osim toga to nisu pravi krugovi nego su diskretizirani na polja. Zato bilo kakvo rješenje čija bi složenost ovisila samo o broju krugova možemo zaboraviti.

S druge strane, mogli bismo za svako polje vrlo jednostavno provjeriti koji krugovi ga pokrivaju i izračunati koliko će na njemu trave narasti – kad to ne bi bilo presporo.

Rješenje se nalazi u sredini, između perspektiva “gledam krugove odjednom” i “gledam svako pojedino polje”. Nemamo vremena proći po poljima (N2), ali imamo vremena proći po redovima (N). Dovoljno je riješiti zadatak zasebno za svaki red matrice. Dakle, promatramo pojedini red, formulama izračunamo na kojim poljima ga sijeku krugovi (to su jedina polja gdje se mijenja stanje) i prolaskom po tim “zanimljivim” poljima usput zaključujemo što je s poljima koje preskačemo.

Ista je ideja u zadatku Vandal. Iako mi je bilo jasno da se zadatak može riješiti samo formulama i ifovima (iako ne znam je li to itko u potpunosti uspio), rečenica koju je Lovro Pužar izgovorio na prezentaciji rješenja bila mi je prosvjetljujuća: “N je do 107 – ako si možete priuštiti for petlju, priuštite si je.” Prođemo po redovima; za svaki red možemo relativno lako izračunati polja u kojima ga sijeku zadani stupac i zadane dijagonale; riječ je o najviše tri zanimljiva polja kojima lako odredimo boju.

HONI i rješenje kao niz zamjedbi

(Najprije sam napisao “niz opservacija”, i ekipa zaista koristi riječ “opservacija” dok “zamjedbu” ne koristi nitko, no evo, smatram da je ova riječ bolja i malo trendsettinga neće mi škoditi.)

Ako je zadatak dobar, proces smišljanja rješenja vjerojatno neće biti binaran – od “nemam pojma” do “aha, smislio sam” u jednom trenutku – nego će se sastojati od nekoliko stepenica od kojih ćemo na svakoj uočiti nešto što će nas dovesti malo bliže rješenju. (Zapnemo li na nekoj od njih, možda možemo skupiti djelomične bodove – “parcijalu” iz sekcije Bodovanje).

Kao primjere tih stepenica navest ću tijek svojih misli prilikom čitanja i razmišljanja o zadatcima 2-5 s jučerašnjeg HONI-ja (a možda i 6-7 u idućem postu). Ovo je i doprinos objavljivanju rješenja s tog natjecanja, koja je bolje objaviti što prije, jer interes za rješenjima eksponencijalno pada kako vrijeme od natjecanja prolazi.

Zadatak Glasovi

Zamjedba #1. U većini slučajeva, gljive su u istoj košari kad im je isti cjelobrojni količnik pri dijeljenju s K.

Zamjedba #2. Poseban slučaj: ako je gljiva djeljiva s K, ona zapravo pripada prethodnoj košari (s obzirom na svoj količnik).

Zamjedba #3. Poseban slučaj: ako je bilo koja od zadanih dviju gljiva u istoj košari kao posljednja (N-ta gljiva) i pritom N nije djeljiv s K, odgovor je NE.

Zadatak Magnus

Zamjedba #1. Znam tko je Magnus (a bome znam i tko je Kile).

Zamjedba #2. Sva slova koja nisu H, O, N, I možemo bez pardona odmah izbaciti (jer su beskorisna).

Zamjedba #3. Mogu izbaciti sva slova s početka riječi dok ne dođem do slova H (jer su beskorisna).

Zamjedba #4. Nakon što sam našao H, mogu izbaciti sva sljedeća slova dok ne dođem do slova O (jer su beskorisna).

Zamjedba #5. Mogu izbacivati sljedeća slova dok ne dođem do slova N i potom sljedeća dok ne dođem do I. Tako sam dobio jedan HONI-blok.

Zamjedba #6. Prethodne korake (pronalazak H, O, N, I) ponavljam dok god mogu i to je rješenje.

Zadatak Pismo

Zamjedba #1. Ne znam tko je Kasap.

Zamjedba #2. Ako uzmem cijeli niz kao interval, dobit ću najveću (a ne najmanju) razliku max – min.

Zamjedba #3. Uvijek se isplati smanjiti interval, tj. izbaciti neke brojeve iz njega, jer tako njegova razlika max – min može samo opasti, ne i narasti.

Zamjedba #4. Dovoljno je promatrati intervale koji se sastoje od samo dvaju susjednih brojeva.

Zadatak Sajam

Zamjedba #1. Redoslijed operacija nije važan.

Zamjedba #2. Ako dvaput napravimo istu operaciju, kao da je nismo ni napravili, tj. svaku ćemo napraviti 0 ili 1 puta.

Zamjedba #3. Prvo ću smisliti jednostavniji slučaj kad je K = 0, tj. flipam samo retke i stupce.

Zamjedba #4. Ako fiksiram prvi redak (s flipom ili bez njega), točno znam koje stupce moram flipati (a koje ne smijem) da bih ga cijeli pogasio. I onda samo provjerim ostale retke.

Zamjedba #5. Općenito, ako kažem da ću tek na kraju flipati stupce, zadatak se svodi na izjednačavanje redaka (bez flipanja stupaca).

Zamjedba #6. Ako postoji redak gdje se ne koristi posebno flipanje ćelije, dovoljno je njega fiksirati i provjeriti koliko mi treba operacija (više ili manje od K) da ostale retke s njim izjednačim.

Zamjedba #7. To je ipak sporo, ukupno O(N3).

Zamjedba #8. U drugom slučaju, ako je K = N i ako se u svakom retku posebno flipa jedna ćelija, dovoljno je za prvi redak odabrati i fiksirati ćeliju koju flipamo te napraviti istu provjeru.

Zamjedba #9. Pristupom iz prethodnih zamjedbi, na točan raspored flipanja možemo naići mnogo puta, fiksirajući bilo koji njegov redak koji ima nula ili jednu flip ćeliju.

Zamjedba #10. Takvih je redaka u svakom scenariju barem N/2, a jedan od njih pogodit ćemo u npr. 20 slučajnih odabira, što je daje složenost O(20 * N2).

Zadatci sa studentskog

Prije desetak dana održan je VRSIH 2018, mislim da su bili zgodni zadatci. Budući da su danas objavljena rješenja zadataka, može započeti njihov upsolving.

Zadatci su na natjecanju bili poredani po abecedi, a radi pristupačnosti ovdje ih redam po težini, uz neke usputne komentare. Izradu zadataka je vodio Ante Đerek, a sudjelovali smo i Ivan Paljak, Luka Kalinovčić, Mislav Balunović, Ivan Katanić, Gustav Matula i ja.

  1. Luka – preskočite osim ako ste početnik
  2. Flauta – koderski
  3. Menza – Ovaj zadatak nastao je tako što sam nekad davno morao smisliti kako efikasno provjeriti natjecateljsko rješenje na zadatku Pekar.
  4. Načitan – Ovo nije prvi (a vjerojatno ni posljednji) od mojih zadataka čiji je input jedan jedini broj. Zna li netko dokazati minimalnost rješenja za neparan N?
  5. Alloc – U tekstu možda nedostaje napomena da je dozvoljeno da se dvaput pozove malloc s istom varijablom, npr. “aaaa=malloc(10); aaaa=malloc(20);” pri čemu “free(aaaa)” oslobađa samo posljednji blok.
  6. Stablo u stablu – Poučna fora na stablu. Nekoliko sličnih zadataka: Path Union, Kingdom and its Cities
  7. Ploča – “matematički”, dobar za clear thinking, autor Luka Kalinovčić
  8. Hulja – geometrijski, autor Ivan Paljak
  9. Reality – odlična fora, autor Ivan Paljak
  10. Ghost leg – Meni je pao na pamet, Gustav Matula ga je riješio, a Luka Kalinovčić pripremio i napisao opis.

Kao što postoji zadatak dana, zadatak tjedna i zadatak mjeseca, tako postoji i zadatak natjecanja. U ovom slučaju to bi vjerojatno bio Ghost leg zbog lijepog i nestandardnog rješenja. Taj zadatak treba staviti na neki međunarodni judge poput Spoja; bilo bi super ako ima dobrovoljaca za to! A i za druge teže zadatke, kad se nađe vremena.