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

Komentiraj

Popunite niže tražene podatke ili kliknite na neku od ikona za prijavu:

WordPress.com Logo

Ovaj komentar pišete koristeći vaš WordPress.com račun. Odjava /  Izmijeni )

Google+ photo

Ovaj komentar pišete koristeći vaš Google+ račun. Odjava /  Izmijeni )

Twitter picture

Ovaj komentar pišete koristeći vaš Twitter račun. Odjava /  Izmijeni )

Facebook slika

Ovaj komentar pišete koristeći vaš Facebook račun. Odjava /  Izmijeni )

Spajanje na %s