Zadatak dana: ABCD

Ovaj zadatak statistički je najpopularnija stvar koju sam ikad napravio, budući da ga je na Spoju riješilo gotovo 2000 korisnika (a pokušalo riješiti vjerojatno još toliko — ukupan broj slanja trenutačno je 11844) iako se ne radi o posve trivijalnom zadatku.

Jedan od uzroka popularnosti zadatka mogla bi biti činjenica da je jedan od prvih po abecedi, pa se pojavljuje kao prvi na listi riješenih zadataka mnogih korisnika (kao npr. ovdje). Argument u prilog toj uzročnoj vezi je i činjenica da je “abecedno sličan” zadatak ABCDEF, čiji je autor naša legenda Luka Kalinovčić, također jako (čak i dva-tri puta više) popularan na istoj stranici.

No svakako u prilog zadatku ide i ljepuškastost njegovog rješenja — kad god otvorim stranicu zadatka, vidim bar jedan komentar koji kaže da je zadatak predivan. S time biste se mogli složiti ako volite najveći mogući adhocness level, zadatke koji se rješavaju “na prevaru”. Dovoljno je spomenuti da je zadatak nastao dok sam vježbao za matematička natjecanja tumarajući po bespućima tadašnjeg MathLinksa (današnjeg AoPS-a) i vidio zadatak na nekom starom, možda poljskom natjecanju, gdje je trebalo dokazati postojanje rješenja.

Zadatak sam najprije bio složio za ZRS-ovu Informatijadu (za mlađu i stariju podskupinu), gdje mi je tadašnji natjecatelj Zvonimir Medić ukazao na to da je uspješno provukao neko greedy/heuristično rješenje koje ne bi trebalo raditi na određenim test podatcima, ali ga nisam imao na umu pri izradi zadatka. Poslije mi je poslao nekoliko test podataka koji ruše njegovo i nekoliko sličnih rješenja. Stoga mu pripada dio zasluge za kvalitetu zadatka (tj. njegovih testova) na Spoju, kao i za frustraciju određenog broja korisnika koji ne mogu progurati svoje heuristike.

Advertisements

Tip of the day: permutacija == ciklusi

Jeste li znali da permutacija nije ništa drugo nego skup ciklusa? To je objašnjeno u ovom zadatku, a nešto formalnije ovdje (sekcija Cycle notation).

Rješenja mnogih zadataka temelje se na ovom triku:

Cages (izvorno Zmije s Infokupa 2014. za 6. razred)

Korijen permutacije (Codeforces)

Sort (HIO 2011.)

Cycle sort (EJOI 2018., mnogo teža verzija prethodnog zadatka i motivacija za ovaj post)

Uživajte!

Tip of the day: tablica je bipartitan graf

Na EJOI 2018. pojavio se zadatak Chemical table. Do njegovog rješenja moguće je doći i bez trika koji ću ovdje pokazati, ali taj trik čini rješenje lakšim i očitijim.

Najprije primijetimo da zadatak nije dinamikast, nego grafast, jer poredak redova i stupaca u tablici nije važan: bilo kojom permutacijom redova i stupaca problem se ne mijenja. Iz perspektive redova i stupaca, važno je samo koji parovi (red, stupac) imaju zadano polje u svom presjeku.

Odatle se prirodno nameće pretvorba u graf: ako postoji element u presjeku reda R i stupca S, onda u grafu bridom povezujemo vrh R (koji predstavlja red) i vrh S (koji predstavlja stupac). Dobiveni graf je bipartitan: s jedne strane su vrhovi koji predstavljaju redove, a s druge strane vrhovi koji prestavljaju stupce. Poredak jednih i drugih ne igra nikakvu ulogu, tj. nije važno kojim redom crtamo vrhove dok god čuvamo informaciju o tome koji su međusobno povezani.

Nacrtajmo u dobivenom grafu situaciju iz zadatka, kada imamo tri elementa koja čine “skoro pravokutnik”: (R1, S1), (R2, S1) i (R2, S2). To znači da u bipartitnom grafu imamo tri brida koji zajedno čine put duljine tri: R1 –> S1 –> R2 –> S2. U tom slučaju možemo dodati i brid (R1, S2). To znači da put duljine tri možemo skratiti na put duljine jedan. Iz toga slijedi da možemo povezati svaka dva nasuprotna vrha u bipartitnom grafu ako među njima postoji ikakav put. Drugim riječima, da bismo mogli izravno povezati proizvoljan red s proizvoljnim stupcem (tj. dobiti traženi element u polju), dovoljno je da se odgovarajući vrhovi nalaze u istoj komponenti povezanosti.

Dakle, graf moramo učiniti povezanim, za što je dovoljno broj_komponenata_povezanosti – 1 novih bridova (polja) jer svaki novi brid povezuje dvije komponente i tako smanjuje broj komponenata za jedan.

Još jedan zadatak koji koristi ovaj trik možete riješiti ovdje. Update: pogledajte i Marinov komentar ispod!

Postoji još jedna, drugačija transformacija tablice u bipartitni graf. Ona se javlja u jednom klasičnom zadatku (online inačica je ovdje kao što mi je ukazao abeker):

Dana je M x N tablica (M, N ≤ 300) koja se sastoji od praznih polja i prepreka. Potrebno je tablicu (tj. samo njezina prazna polja) na bilo koji način potpuno popločati dominama (1 x 2 i 2 x 1) ili odgovoriti da to nije moguće.

Ovdje je trik primijetiti da, obojimo li polja tablice crno i bijelo kao na šahovnici, svaka domina pokriva jedno crno i jedno bijelo polje. Budući da polje smije najviše jednom biti pokriveno, zadatak se svodi na maksimalni matching u bipartitnom grafu koji s jedne strane ima crna, a s druge strane bijela polja tablice, ne uključujući prepreke, a susjedna polja povezana su bridom — potencijalnom dominom.

Primijetite da je ovo potpuno drugačija transformacija tablice u bipartitni graf od one s EJOI zadatka: ondje su vrhovi grafa bili redovi i stupci tablice (specijalno, dobiveni graf može biti gust), dok u ovoj vrhovi grafa odgovaraju poljima tablice (svaki vrh ima najviše četiri brida). Teži zadatak na sličnu foru bio je Alliances sa CEOI 2010., a opis rješenja možete pronaći ovdje.

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!

Zadatak dana: GTA

Izvor: Izborne pripreme 2014., prvi izborni ispit

Ovaj zadatak ima zanimljivu “backstage” priču koju sam odlučio ovdje podijeliti. Na početku napomena — post je relativno dug, a ni zadatak nije jednostavan, pa ako nemate neki miran chunk slobodnog vremena, ostavite ovo za poslije.

Inspiracija za zadatak

Autor zadatka je moja malenkost. Ideja je potekla od znatno lakšeg zadatka iz knjige Zgode i mozgalice družbe Matkači autora P. Mladinića, izvorno objavljenog na poleđini časopisa Matka. Bio je zadan u obliku stripa, a ukratko bi glasio otprilike ovako:

Jurica je izmislio novi jezik čije su riječi sastavljene od slova A, B i C. Različite riječi mogu označavati isti pojam: to su sinonimi. Vrijedi: ako dvama sinonimima dopišemo s iste strane ista slova, ponovno dobivamo dva sinonima. Poznati su sljedeći parovi sinonima: AB i C, BC i A, te CA i B. Riječi AB i BA nisu sinonimi. Koliko pojmova ima Juričin jezik?

Pokušajte najprije sami otkriti sličnost ovoga zadatka i zadatka GTA, ili čak riješiti ovaj zadatak, a onda čitajte dalje.

Sljedeća je opservacija ključna za rješenje zadatka iz Matke: ako u nekoj riječi zamijenimo blok AB slovom C ili obrnuto (te analogno za zamjene BC – A i CA – B), dobivamo njezin sinonim. To vrijedi zato što, počevši od sinonima AB i C, dodavanjem istih slova slijeva i zdesna ponovno dobivamo sinonime, a upravo tako mogu nastati dvije riječi koje veže spomenuta zamjena blokova AB i C.

Tu vidimo sličnost ovoga zadatka sa zadatkom GTA. Kada bi u zadatku GTA molekule bile sastavljene od znakova A, B i C, kada bi tri dozvoljene mutacije bile AB – C, BC – A i CA – B te kada bismo molekule koje dobivamo jednu iz druge zvali sinonimima, zadatak bi bio praktički isti: pitanje “je li moguće jednu molekulu dobiti iz druge” svodi se na “jesu li ove riječi sinonimi, tj. odgovaraju li istome pojmu”.

Koliko je pojmova?

Igrajući se sa zadatkom iz Matke, možemo dobiti da je AA = ABC = CC i AA = BCA = BB, dakle: AA = BB = CC. Čini se da zasad imamo pojmove A, B, C, AA, AC, BA i CB. Nadalje, od svih riječi s tri slova samo je ACB novi pojam. Ostale su riječi sinonimi ovih osam pojmova. Primjerice, ACB = BCCB = BAAB = BAC, BAA = BCC = AC. Nadalje, lako se pokaže da je svaka riječ od četiri slova sinonim neke kraće riječi. To znači da među četveroslovnim riječima nema novih pojmova, a isto vrijedi i za riječi s još više slova jer ih lako “kratimo” zamjenom bilo kojeg četveroslovnog bloka njegovim kraćim sinonimom. Ukratko, Juričin jezik ima samo 8 pojmova.

Zadatak GTA nastao je iz sljedećeg pitanja: što ako se Juričin jezik proširi na četiri slova — A, B, C, D — sa sličnim pravilima? “Slična pravila” mogla su biti A – BC, B – CD, C – DA, D – AB (slovo se zamjenjuje blokom od “sljedeća dva” slova), ili pak A – DB, B – AC, C – BD, D – CA (slovo se zamjenjuje blokom od “okolnih” slova).

Za svaku od ovih varijanti napisao sam program koji broji pojmove jezika. Preciznije, za svaku riječ kraću od 8 znakova tražio sam njezine sinonime širenjem na njoj “susjedne” riječi (one koje nastaju zamjenom, tj. mutacijom), s pomoću DFS ili BFS algoritma. U tom kontekstu, “pojam” odgovara komponenti povezanosti, tj. sve riječi koje je moguće dosegnuti širenjem iz neke riječi čine isti pojam. Otkrivši malen broj pojmova za prvu varijantu (ne sjećam se koliko — isprobajte pa otkrijte!) i 24 pojma za drugu varijantu, odlučio sam se za drugu.

Primijetite da je lakše baratati sa slovima A, B, C i D, što ćemo i u nastavku teksta činiti. Slova A, C, G, T odabrana su u kasnijoj fazi izrade zadatka, kad sam uočio da su četiri slova i njihove zamjene zgodna podloga za priču o DNK i mutacijama.

Varijante zadatka i njegovog rješenja

Zadatak je isprva glasio: za dvije zadane (velike) riječi, je li moguće dobiti jednu iz druge? Očekivano rješenje bilo je sljedeće:

  1. napravimo flood-fill (širenje) za male duljine riječi da otkrijemo pojmove, tj. komponente povezanosti,
  2. odatle uočimo da se svaka riječ od 5 slova može skratiti na najviše 4 slova,
  3. kratimo ulazne riječi mijenjajući njihove peteroslovne blokove unaprijed pronađenim pokratama,
  4. na koncu za dobivene dvije kratke riječi pogledamo jesu li u istoj komponenti.

Luki Kalinovčiću, kolegi u izradi zadataka, nije trebalo računalo da uoči mogućnost kraćenja velikih riječi: on je “na papiru”, koristeći dozvoljene zamjene, dokazao da se svaka riječ može skratiti na najviše 6 znakova, uz komentar da bi na natjecanju uz pomoć računala tražio najkraću duljinu takvu da se bilo koja riječ te duljine može skratiti.

Luka je predložio da se ulazni podatak sastoji od N riječi (a ne samo dvije) te da za svaki par tih riječi treba ispisati može li se jedna dobiti iz druge. Prijedlog je prošao, a motiv je bio sljedeći: budući da je rješenje koje promatra svake dvije od N riječi (bez prethodnoga kraćenja) presporo, natjecatelju se sugerira ideja da se najprije svaka riječ skrati i/ili svrsta u pripadnu klasu.

Luka je predložio i da zadatak bude tipa output-only (tj. da natjecatelji dobiju sve ulazne primjere i šalju samo odgovarajuće izlaze), vjerojatno u želji da motivira natjecatelje da kodiraju širenje za manje primjere i tako uoče rješenje. Goran Žužić, još jedan od tadašnjih autora za HIO/izborne, rekao je da je zadatak “u duši output-only”, ali da je još bolji kao standardni zadatak. Nisam se odlučio za output-only varijantu jer se njome gubi efekt iz prethodnog odlomka: teže bi bilo zaključiti da ne valja odmah gledati parove riječi jer bi vremensko (ne)ograničenje to dopustilo. Natjecatelj Dominik Gleich nakon natjecanja je komentirao da je odluka bila dobra: output-only varijanta možda bi pogrešno sugerirala da nema egzaktnog rješenja koje unutar sekunde rješava bilo koji primjer.

Motivaciju da naprave širenje za male primjere natjecatelji su imali u sekciji Bodovanje koja je opisivala čak šest malih primjera (s duljinama riječi od 2 do 6) koji su činili 60% bodova. Ipak, samo je Ivan Lazarić riješio te primjere. Zadatak se pokazao teškim: nitko ga nije riješio.

Je li rješenje točno?

Zanimljiva je činjenica da za vrijeme natjecanja nismo imali egzaktan dokaz točnosti rješenja.

Vjerojatno se pitate: što uopće treba dokazivati? Najprije primijetite da je drugi primjer iz teksta zadatka rješiv samo ako dopustimo širenje riječi na barem 8 slova. Jedini način da skratimo molekulu CGTAC jest da je najprije produljimo na 8 slova, a tek onda kratimo. Ako širenje ograničimo samo na riječi duljine do 7, dobit ćemo da su molekule C i CGTAC nepovezane, tj. da se nalaze u različitim komponentama. Nameće se sljedeće pitanje: kako znamo da je širenje do duljine 8 dovoljno da se spoje sve komponente koje se uopće mogu spojiti? Je li stvarni broj povezanih komponenti možda manji od 24? Kako znamo da npr. riječ A nije moguće dobiti iz riječi C? Što ako jedini “put” između njih ide po riječima od stotinjak slova pa ga širenjem po riječima duljine do desetak slova nije moguće otkriti?

Takve stvari obično se (npr. na matematičkim natjecanjima) dokazuju pronalaženjem invarijante. U našem slučaju trebalo bi svakoj riječi po nekom pravilu pridružiti matematički objekt (broj, niz ili nešto slično), tako da on ostaje isti prilikom mutacije riječi. Time će svim riječima iste komponente biti pridružen isti objekt. Ako su riječima A i B pridruženi različit objekti, jasno je da ne postoji put koji ih povezuje.

Na primjer, nije teško dokazati da postoje barem 3 različite komponente: ako slova A, B, C, D zamijenimo brojevima 1, 2, 1, 2, onda se zbroj slova u riječi, modulo 3, ne mijenja prilikom mutacije. To npr. dokazuje da od A nije moguće doći do B ili D, ali ne govori ništa npr. o tome postoji li put od A do C.

Na prezentaciji rješenja rekao sam da je ono “empirijski dokazano” jer sam uspio, uz napor, provjeriti da broj komponenti ostaje 24 i kada dopustimo širenje na riječi duljine do 12. Jer intuitivno je posve prihvatljivo da, ako između dviju riječi od 4 slova (a svaka komponenta sadrži takvu riječ) ne postoji put koji riječ smije širiti do duljine 12, onda između njih uopće ne postoji put.

Pitanje o tome je li moguće doći iz riječi A u riječi B, C ili D postavio sam na međunarodnom matematičkom forumu AoPS. Pet dana nakon natjecanja, jedan forumaš dokazao je da A, B, C i D pripadaju različitim komponentama, pronašavši invarijantu koja dokazuje da postoji barem 12 različitih komponenti, uz zahvalno objašnjenje svog načina razmišljanja. Ukratko, svakom slovu pridružio je permutaciju reda 4, a svakoj riječi kompoziciju permutacija njezinih slova.

A sljedećega dana — gotovo tjedan dana nakon natjecanja — rješenje je konačno bilo dokazano: Ante Đerek, inače voditelj izrade zadataka, uz pomoć računala pronašao je invarijantu koja daje 24 komponente, također permutacijsku. Možete je vidjeti u opisu službenog rješenja na stranicama HSIN-a.