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.

IOI, IPSC i nestandardni zadatci

Ovoga tjedna u Japanu se održava IOI 2018., najprestižnije natjecanje srednjoškolaca u programiranju. Pratimo trenutačne rezultate; nakon jučerašnjeg prvog dana natjecanja najbolja iz našeg tima je Paula Vidas – svaka čast!

Nisam gledao jučerašnje zadatke, ali IOI zadatci uglavnom su vrlo kvalitetni, zbog važnosti natjecanja i vremena koje majstori iz ISC-a (International Scientific Committee) ulože u izradu zadataka. Ponekad se pojavi novi tip zadatka kakav do tada nije bio uobičajen. Naime, u IOI Syllabusu – dokumentu koji navodi teme koje se mogu pojaviti – postoji kategorija Outside of focus koja sadrži sve teme koje nisu spomenute u dokumentu, dakle, beskonačno mnogo njih. Za njih vrijedi: “This does not prevent the inclusion of a competition task that is related to a particular topic from this category. The ISC may wish to include such a competition task in order to broaden the scope of the IOI.”

Primjeri nestandardnih zadataka s prethodnih IOI:

  • Languages (IOI 2010.), prepoznavanje jezika; kao i Art Class (IOI 2013.), prepoznavanje stila slike – koketiranje s umjetnom inteligencijom i strojnim učenjem.
  • Saveit (IOI 2010.), treba napisati dva odvojena programa od kojih prvi šalje informaciju drugome koristeći što manje bitova – “komunikacijska složenost”, čuo sam da je bilo i još takvih zadataka.
  • Odometer (IOI 2012.), svojim programom generiramo drugi (traženi) program.

Naravno, nestandardnih i mnogo luđih zadataka na manje ozbiljnim natjecanjima (kao što je CF April Fools Contest) ima mnogo više.

To nas dovodi do online natjecanja IPSC koje se održava za mjesec dana i koje se temelji na neobičnim zadatcima: “Internet Problem Solving Contest pushes the boundary of what is possible in programming competitions.” Natjecanje je jako popularno i preporučujem svima da se na njemu zabave u timovima do troje ljudi.

Za kraj bih naveo nekoliko “ludih” zadataka s naših natjecanja:

  • Šetnja (Državno 2014.) – prvo pojavljivanje “challenge” zadatka u osnovnim školama,
  • Esej (HONI 2015.) – lagan, ali netipičan zadatak,
  • Janje aka Vesela bojanka (HONI 2015.) – genijalan zadatak Ivana Paljka na tri stranice.

Poluosvrt na EJOI 2018.

Jučer smo se iz Innopolisa vratili u Zagreb. Rezultati hrvatskog tima standardno su izvrsni, iako su nade bile i veće, npr. za Patrika. Moja je prognoza prije natjecanja bila zlato, srebro i dvije bronce.

Ono što olimpijadama daje posebnu draž su i svi oni dani i sati kada nema natjecanja: druženje, izleti, boravak u novom i zanimljivom okruženju. Upoznao sam Slovenca Žigu Željka koji mi je detaljno pokazao trikove kojima je prevario grader na IOI 2015. S Patrikom, Dorijanom, Franom i Bernardom bilo je pravo zadovoljstvo družiti se i zaje šaliti. Naučio sam da s ovim genijalcima nije nimalo lako igrati mafiju (točnije, bolju verziju mafije koja se zove Resistance ili Avalon) jer ih je teže prokužiti. Kombinatorika Patrika i Bernarda u toj igri, u smislu složenih logičkih implikacija koje su predlagali, bila je impresivna. Šteta što nisu malo bolje kombinirali na natjecanju, no sve je to razumljivo, jer iskustvo velikog broja natjecatelja neumoljivo kaže…

Pravilo natjecateljskog programiranja #2: Natjecanje sjebeš.

Preciznije, riješiš lošije nego što bi riješio u optimalnim okolnostima, i to možda dva od tri puta. Natjecanje ne pokazuje definitivno tko je koliko dobar, tko je bolji ili lošiji, nego daje aproksimaciju toga, kao kad radite anketu na malom uzorku populacije. Od dvaju podjednako dobrih natjecatelja bolji će ispasti onaj koji manje sjebe. Tek nakon velikog broja natjecanja procjena je precizna.

Iako smo prije EJOI-a bili predložili da na njega uvedu Python, to se još nije dogodilo. Kao veliki pobornik Pythona, savjetovao sam njegovo uvođenje potencijalnoj organizatorici sljedećeg EJOI-a, srpskoj leaderici Jeleni, koja ima sličan stav. Spominjala je zasebne time limite, s čime se ne slažem jer postoje drugi načini rješavanja problema sporosti Pythona (npr. biranje C++a u zadatcima gdje Python ne prolazi), ali to je sada manje važno, bitno je da se Python uvede. O njemu ću više pisati neki drugi put.

Zadatci su bili prvi dan dinamikasti, a drugi dan grafasti. Procjenjujući adhocness level, rekao bih da je na prvom danu Hills bio nivoa 1, AB-Strings nivoa 4, Passports nivoa 2; dok je na drugom danu Chemical Table bio nivoa 3, Prime Tree nivoa 4, a Cycle sort nivoa 3. Dakle, na prvom danu zadatcu su bili manje ad-hoc i stoga primjereniji, primjerice, koderski uvježbanijem Franu Babiću nego matematičaru Bernardu Inkretu, dok je na drugom danu bilo obrnuto – zadatci su bili manje babićasti a više inkretasti. U zadatcima se pojavilo nekoliko lijepih trikova o kojima ću napisati zasebne postove. Stay tuned!

Kružni intervali

[Osvrt na ovosezonske zadatke – 4. dio]

O većini zadataka s proteklog Državnog natjecanja 2018. nemam mnogo zanimljivog za napisati. Neke poluanegdote koje bih mogao spomenuti uključuju:

  • Graf iz najlakšeg zadatka Trek izravno je preuzet sa slike iz zadatka Jezero s DMIH-a 2008.
  • Zadatak Infokuhar predložio sam još 2015. godine kad se natjecanje zvalo Infokup, kao jedan od najtežih zadataka za osnovne škole. Zbog određenih manjkavosti (“previše matematički”) zadatak je tri godine bio rezerva sve dok ga ove godine nisam napokon (i sa zadovoljstvom) zadao.
  • Predikcija iz teksta zadatka Ikebana, ona o Paoli koja se priprema za IOI 2018. u Japanu, skoro je bila istinita (fulali smo jedno slovo).
  • Zadatak TurboExcel uopće nije toliko težak.

No, zadatak koji sam zapravo htio komentirati je Pjege (1. i 2. razred, 2. dan natjecanja). On je u potpunosti nastao večer prije samog natjecanja, nakon što smo odustali od jednog zadatka koji je trebao biti na njegovom mjestu. Tada smo odlučili da je, iako smo bili jako umorni, svakako mudrije odmah smisliti i pripremiti novi zadatak, nego to učiniti sljedeći dan (prije 14 sati kada je počinjalo natjecanje).

Iskoristili smo ideju iz zadatka Kugloboćanje koji je bio pripremljen za isto natjecanje za 3. i 4. razred. Kao dio rješenja tog zadatka trebalo je pronaći minimalan broj polupravaca iz ishodišta tako da svaki od zadanih kutnih intervala bude pogođen barem jednim polupravcem. Budući da u zadatku promatramo samo I. i II. kvadrant koordinatnog sustava, to se svodi na 1D problem gdje treba pronaći minimalan broj točaka tako da svaki od zadanih intervala sadrži barem jednu točku.

Rješenje je relativno jednostavno: uvijek se isplati kao točku odabrati prvi završetak intervala (dokažite!); točnije, interval koji prvi završava a da nije “riješen” prethodnom točkom. Problem nastaje ako intervali u uniji pokrivaju cijeli krug: tada problem postaje kružni i više ne znamo odakle početi. U zadatku Kugloboćanje to se nije moglo dogoditi, no tu mogućnost dopustili smo u novom zadatku Pjege koji je dobio drugačije “pakovanje”, prebačen je iz geometrije u drugu domenu i na prvi pogled nema mnogo sličnosti sa zadatkom Kugloboćanje.

No što je rješenje? Jedna je mogućnost provesti isti greedy postupak za svaki mogući odabir granice od koje ćemo redom promatrati intervale, pamteći onaj postupak koji je dao najbolje rješenje. To rješenje ima kvadratnu složenost i zato smo stavili manje ograničenje (N ≤ 1000). Dokaz točnosti temelji se na činjenici da optimalni odabir točaka sigurno sadrži takvu “granicu”, jednu za svaku od odabranih točaka.

Razmišljali smo, naravno, o rješenju koje bi bilo linearno (točnije loglinearno) kao i u zadatku Kugloboćanje. Neke ideje su sljedeće.

  • Heuristika koja na slučajan način bira 5, 10 ili 30 početaka i provodi spomenuti greedy postupak, pamteći najbolji rezultat. Tek sada, nakon dosta razmišljanja, mislim da znam kojim primjerom ju je moguće srušiti.
  • Kretanje od jednog, bilo kojeg početka i biranje točaka na spomenuti način. Nakon što napravimo dva puna kruga, dobili smo niz točaka koji je redundantan jer smo većinu intervala pokrili dvaput. U tom nizu odabiremo minimalni uzastopni podniz točaka koji pokriva više od punog kruga, te iz njega izbacujemo jednu točku. Ne znam je li točno.
  • Biranje točke koja upada u najveći broj još neriješenih intervala. Ne znam je li točno, a i ne znam može li se ostvariti u sub-kvadratnoj složenosti.

Iz ovoga je jasno zašto smo se odlučili za popustljivo ograničenje N ≤ 1000. Ograničenje N ≤ 100 000 imalo bi smisla samo kada bismo a) imali dokazano rješenje, b) znali koja su rješenja pogrešna i kako ih srušiti. No mene i dalje zanima može li netko dokazati ili kontraprimjerom opovrgnuti neko od gore navedenih rješenja.