Savjeti iskusnih za one malo manje iskusne

Savjet 1 – Vaš cilj na natjecanju nije riješiti što veći broj zadatka, vaš je cilj skupiti što je više moguće bodova.

Kao jednom od voditelja HONI-ja cilj mi je na svakom zadatku predložiti zanimljive parcijale. Ponekad te parcijale budu samo brut, ponekad vas svaka sljedeća parcijala navodi sve više k rješenju, a ponekad su tamo samo jer su zanimljive i vrijedne pridijeljenih bodova.

Ono što je pomalo razočaravajuće za mene jest to da su parcijale bile jako slabo riješene na zadnja dva kola HONI-ja. Bilo je tu raznih parcijala, od nekih trivijalnih, do nekih stvarno teških jer su bile gotovo cijela rješenja nekih zadataka, ali sve su više-manje bile slabo riješene. 20 bodova je zapravo jako mnogo, pogotovo u osnovnoj školi gdje s 20 bodova više možeš lako biti u top 10 u državi. Meni kao natjecatelju su govorili da umnožak mojih bodova po zadacima na natjecanju ne smije biti 0, tj. da na svakom zadatku trebam rješiti barem najlakšu parcijalu. Većinom sam to uspio, nekad nisam, ali nema veze, uvijek bih razmislio o svakom zadatku barem na toj osnovnoj razini da shvatim što zadatak traži od mene i što svaka parcijala traži od mene.

Pogledajmo sada neke parcijale s prethodnih dvaju kola.

  1. 20 bodova na zadatku ACM moglo se osvojiti tako da samo ispišemo indeks retka u kojem je prvi string jednak “NijeZivotJedanACM”. Dakle, N puta trebalo je učitati M+1 stringova i provjeriti je li prvi string traženi string. Siguran sam da mnogo od ~200 učenika koji su na tom zadatku osvojili manje od 10 bodova zna to nakodirati.
  2. 20 bodova na zadatku Zvijezda moglo se osvojiti samo poznavanjem ccw funkcije. Osim inputa i outputa koji su jako jednostavni na ovom zadatku, nema ni 10 linija koda budući da je ccw samo formula. Pretpostavljam da je gotovo svaki srednjoškolac koji konkurira za prolaz na HIO čuo za tu funkciju, međutim samo je jedan to nakodirao na natjecanju.
  3. Zadatak Slagalica imao je mnogo parcijala, najlakša je bila rješiva samo s par if-ova i težine je zadatka za 5. razred osnovne škole. Sigurno dosta učenika od ~240 njih koji su imali 0 na ovom zadatku znaju napisati te if-ove. Druga parcijala na tom zadataku bila je ona na kojoj je trebalo isprobati sve permutacije zadanog skupa. To je obično najlakši brut na srednjoškolskim zadacima s kojim se bez previše muke mogu osigurati barem neki bodovi na tom zadatku.
  4. 20 bodova na zadatku Trobojnica bilo je moguće ostvariti s rješenjem koje isproba za svaku triangulaciju svako moguće bojenje i provjeri je li to bojenje dobro. Nitko to nije nakodirao, a i to je još jedan veoma klasičan brut za srednjoškolski zadatak.

Zaključimo, dobro pročitajte sve zadatke i pogotovo sekciju bodovanje jer se možda baš na zadnjem zadataku krije jako laganih 20, 30, 50 bodova.

Drugo što bih volio spomenuti jest problem koji je vidljiv na sljedećim podacima.

——————————————————————————————————
Zadatak LIJEPI
Zadatak nije ni pokusalo rijesiti 15 ucenika.
 14 ucenika je osvojilo   0 bodova.
  1  ucenik je  osvojio  10 bodova.
  1  ucenik je  osvojio  16 bodova.
 18 ucenika je osvojilo  18 bodova.
  5 ucenika je osvojilo  22 bodova.
  4 ucenika je osvojilo  24 bodova.
 66 ucenika je osvojilo  26 bodova.
 10 ucenika je osvojilo  28 bodova.
182 ucenika je osvojilo  30 bodova.
Prosjecan broj bodova na ovom zadatku je 27/30, odnosno 90%.
——————————————————————————————————
Zadatak RADIO
Zadatak nije ni pokusalo rijesiti 10 ucenika.
 10 ucenika je osvojilo   0 bodova.
 14 ucenika je osvojilo  15 bodova.
 84 ucenika je osvojilo  20 bodova.
  1  ucenik je  osvojio  25 bodova.
176 ucenika je osvojilo  30 bodova.
Prosjecan broj bodova na ovom zadatku je 25/30, odnosno 83%.
——————————————————————————————————

Ovo su drugi zadaci s prvih dvaju kola ovogodišnjeg HONI-ja. Na zadatku Lijepi 66 učenika koji su osvojili 26 bodova zaboravili su long long u rješenju. Kad sam prvi put vidio tu statististiku, rekao sam da ćemo na drugo kolo staviti opet zadatak na kojem će jedino trebati paziti na long long i htio sam da bude lakši nego u prvom kolu samo zato da vidimo čitaju li učenici rješenja koja objavimo i uče li iz svojih grešaka. U vrijeme pisanja ovog teksta napravio sam istu statistiku za Radio i vidio poražavajuć podatak, a to je da otprilike isti broj učenika (ovaj put zapravo i više – 84) opet nema long long. Probajte pogoditi na što će trebati paziti na drugom zadatku u sljedećem kolu 😉

Sljedeći zadatak na kojem je vidljiv problem je Checker. Svako tko je pročitao i shvatio rješenje zadataka Trobojnica mogao je riješiti barem najlakšu parcijalu na zadatku Checker. Tu parcijalu riješila je samo jedna učenica.

Savjet 2 – Pročitajte opise algoritama nakon svakog natjecanja.

Čitajte rješenja. O ovome je već bilo govora na Blogaritmu (https://blogaritam.com/2018/05/25/tip-of-the-day-upsolving/) pa pročitajte taj post ako još niste ili se podsjetite (ako ste zaboravili) pravila koje će vam jednom donijeti medalje s olimpijada 🙂

Za kraj, zahvalio bih Adrianu što mi je dao prostor na Blogaritmu i svima koji su mi pomogli oko ovog posta. Sretno na idućim HONI-jima!

Marin Kišić

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