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.

Put među permutacijama

[Osvrt na ovosezonske zadatke – 1. dio]

Na Školskom natjecanju 2018. postavljena su dva zadatka vrijedna spomena, zadatak Dwight u P1 (1. i 2. razred) i zadatak Trans u P2 (3. i 4. razred). Oba zadatka su na istu temu: jednu zadanu permutaciju brojeva {1, 2, …, N} treba pretvoriti u drugu zadanu permutaciju koristeći minimalan broj dozvoljenih transformacija. Zanimljivo je što je zadatak za P1 u suštini bio teži od zadatka za P2.

U zadatku Dwight, dozvoljena transformacija bila je odabrati neki element permutacije, sve manje elemente povećati za 1, a odabrani element postaviti na 1. Veličina permutacija bila je N ≤ 10.

U zadatku Trans, dozvoljena transformacija bila je odabrati neki K iz skupa {2, 3, …, N, N+1} i potom svaki element permutacije manji od K promijeniti (istodobno) iz X u K – X. Veličina permutacija bila je N ≤ 8.

Prije komentara o rješenjima ovih zadataka, ubacimo “u igru” još dva zadatka istog tipa, koja se razlikuju samo po vrsti dozvoljenih transformacija:

U zadatku Knjige s natjecanja HONI 2010. dozvoljena transformacija bila je premještanje nekog elementa na početak permutacije. Veličina permutacije bila je N ≤ 300 000.

U zadatku Posloži s natjecanja HONI 2009.  bio je zadan skup dozvoljenih transformacija oblika “zamijeni elemente na pozicijama p1 i p2”, a veličina permutacije bila je N ≤ 12.

U ovom trenutku bilo bi poželjno da pauzirate čitanje i razmislite kako biste riješili ove zadatke (ako još niste) te ih po mogućnosti skodirate. Zadatke s honija možete testirati ovdje i ovdje.

A sada nekoliko zamjedbi. (Htio sam napisati opservacija, ali volio bih da riječ “zamjedba” uđe u širu uporabu.)

Zadatci Dwight i Knjige u suštini su isti. Zašto? U Knjigama premještamo element na poziciju 1, a elementima koji su bili ispred njega povećavamo poziciju za 1. U Dwightu radimo isto, ali ne s pozicijama nego s vrijednostima elemenata. Međutim, lako je promijeniti perspektivu iz pozicija u vrijednosti i obrnuto. Konkretno, napravimo novu permutaciju u kojoj je X-ta vrijednost jednaka poziciji broja X u originalnoj permutaciji (npr. [2, 4, 1, 3] <—> [3, 1, 4, 2]). Čitateljima ostavljam da zaključe koja je perspektiva u ovom zadatku bolja, tj. koji je zadatak “lakši”.

Kako god okrenemo, te zadatke moguće je riješiti u O(N), što se iz ograničenja za Knjige (N ≤ 300 000) moglo i naslutiti. Zadatak Dwight nastao je “drugačijim pakovanjem” zadatka Knjige i besramnim spuštanjem ograničenja na N ≤ 10. Je li to spuštanje pomoglo ili odmoglo, teško je reći. S jedne strane je teže skužiti da postoji linearno rješenje. S druge strane, cilj je bio da brutfors rješenje (BFS po prostoru permutacija) dobije velik broj bodova. On je prolazio na 9/10 primjera.

To nas dovodi do zadatka Trans koji je lakši jer zbog malog ograničenja (N ≤ 8) dopušta upravo takvo rješenje velike složenosti, BFS po grafu čiji su vrhovi permutacije a bridovi transformacije. Zadatak je stavljen u P2 jer takvo rješenje ipak traži više znanja od rješenja Dwighta koje može smisliti i netko tko ne zna ništa o grafovima. (Kad smo već kod zadatka Trans, u službenom Python rješenju koristio sam strukturu queue.Queue koja služi za višedretveno programiranje i za ovu je namjenu (BFS) vrlo neefikasna. Umjesto toga preporučujem uporabu collections.deque.)

Broj pretraženih permutacija u rješenju za Trans iznosi O(ND) gdje je D rješenje. Koliki je najveći mogući D s obzirom na N? Za N = 8 on iznosi 9, tj. najudaljenije dvije permutacije (dijametar grafa) udaljene su za 9 transformacija. A općenito? Nitko ne zna! Naime, ako u zadatku Trans napravimo gore opisanu promjenu perspektive iz vrijednosti u pozicije, dobivamo poznati Palačinkin problem na koji mi je jednom ukazao Patrik Pavić i tako inspirirao ovaj brut-zadatak. Formula za N-ti palačinkin broj je otvoreni problem i još nitko nije izračunao ni dvadeseti. Evo vam prilike da se upišete u povijest matematike.

Je li moguće ubrzati eksponencijalna rješenja u zadatcima Dwight i Posloži tako da dobiju sve bodove, tj. tako da rade za N = 10 u Dwightu odnosno N = 12 u Posloži? Moguće je! U zadatku Posloži to je bila i poanta, koristiti neku od naprednijih metoda pretraživanja grafa: dvosmjerni BFS (istodobno se širimo iz početnog i odredišnog stanja) čime se eksponent smanjuje na D/2, ili algoritam A*. Rješenja svih navedenih zadataka možete pronaći ovdje ili ovdje.