Izazov godine: kvinijska križaljka

Dan prije američkih predsjedničkih izbora 1996., New York Times objavio je križaljku u kojoj je jedan od pojmova bio opisan kao sutrašnja glavna vijest: ******* ELECTED. Je li autor križaljke predvidio izbornog pobjednika?

Genijalnost je bila u tome da se križaljka mogla riješiti na dva jednako ispravna načina: kao novi predsjednik mogao je stajati i CLINTON i BOB DOLE, a da ostali pojmovi i dalje odgovaraju svojim opisima. Npr. black halloween animal ispao je CAT u slučaju CLINTON, a BAT u slučaju BOB DOLE. I tako dalje. Križaljku je sastavio matematičar Jeremiah Farrell.

Best-crossword-puzzle-ever

Dva rješenja ove križaljke razlikuju se u jednom pojmu. Može li više?

U tome je uspio još jedan genijalac, filozof Daniel Dennett. Sastavio je križaljku u kojoj se dva rješenja razlikuju potpuno, dakle u svim pojmovima. Osoba A i osoba B mogu ispravno riješiti križaljku, a da im se, kada usporede rješenja, nijedna riječ (ili čak nijedno slovo) ne podudara, iako za svaki opis i A i B imaju dobar pojam na odgovarajućem mjestu. Križaljku je nazvao kvinijskom (Quinian crossword puzzle) jer ju je upotrijebio da bi ilustrirao zamisao filozofa W. V. O. Quinea o nejednoznačnosti prijevoda (što ovdje nije bitno).

Dennettova prva križaljka izgledala je ovako:

Screenshot_2019-03-09 kolo2_zadaci pdf

Across

  1. Suck the resources out of
  2. Epoch
  3. Sleep furniture
Down

  1. Retentive membrane
  2. Earlier
  3. For some kids, a best friend

Nije baš lagana, pogotovo nama čiji je vokabular engleskog jezika ograničen. Meni je trebalo dosta guglanja da bih pronašao oba moguća rješenja, a pomogao je i rječnik sinonima. Otkrit ću vam da retentive membrane (1 okomito) može biti web ili sac.

Poslije je unaprijedio svoju kvinijsku križaljku, tj. sastavio bolju:

Screenshot_2019-03-09 Intuition Pumps And Other Tools for Thinking - Dennett - Intuition Pumps pdf

Across

1. Dirty stuff
5. A great human need
6. To make smooth
7. Movie actor

Down

  1. Vehicle dependent on H2O
  2. We usually want this
  3. Just above
  4. U.S. state (abbrev.)

(Oba) rješenja poslije ću otkriti u komentaru. No glavni je cilj ovog posta zadati jedan mnogo teži i ozbiljniji izazov. Vjerojatno ste ga dosad i naslutili.

Sastavimo prvu hrvatsku kvinijsku križaljku.

Sastaviti običnu 3 x 3 ili 4 x 4 križaljku nije naročito teško. No zahtijevamo li da križaljka ima još jedno rješenje, u pojmovima različito ali također ispravno tj. u skladu sa zadanim opisima, problem postaje brutalan. No Dennett ga je riješio, pa valjda možemo i mi. Hrvatski jezik, zbog pravilnije izmjene samoglasnika i suglasnika, pogodniji je od engleskog za sastavljanje križaljki – što možete uočiti i uspoređujući broj “crnih” (neiskorištenih) polja u prosječnoj hrvatskoj i prosječnoj engleskoj križaljci.

Rješenje će sigurno uključivati mnogo mašte u povezivanju naizgled nepovezanih pojmova istim opisom, ali problem ne bih spominjao na ovom mjestu kad ne bih mislio da može imati veze i s programiranjem. Imam neke ideje o smjerovima u kojima bi se moglo ići, ali zasad je bolje da ne utječem ni na koga. Bit će još koji post o tome, a do tada možda netko pametniji od mene ovo i uspije.

Kako efikasno vježbati?

Upitnik u naslovu je nužan. Kad bi naslov glasio “Kako efikasno vježbati”, bez upitnika, izgledalo bi kao da na to pitanje imam odgovor. Upitnik sugerira da možda i nemam.

Pitanje se, naravno, odnosi na vježbanje informatike (natjecateljskog programiranja), kao i recimo matematike, a ne na vježbanje tijela. Ali “kako efikasno vježbati tijelo” također je teško pitanje i odgovori na razne njegove varijante (ovisno o ciljevima) još uvijek se unapređuju, a odgovarajuća metodologija koja se zasniva na eksperimentima treba se primijeniti i na naše pitanje. Suvremenoj znanosti, a naravno i psihologiji o kojoj je ovdje donekle riječ, jasno je da malo što možemo zaključiti umovanjem. Treba uzeti sto ili tisuću ljudi i napraviti eksperiment.

U sportu nije nimalo svejedno kako točno izgleda trening pa za vrhunske sportaše velik broj stručnjaka važe i najsitnije detalje treninga. Zato su sportaši desetljećima sve bolji. No ni nama rekreativcima nije svejedno kako treniramo. Na primjer, u trčanju je efikasniji intervalni trening (mijenjanje brzine, hod + sprintevi) nego maratonsko trčanje konstantnom brzinom. U razvoju mišića, ovisno o ciljevima, nije svejedno koristimo li lakše ili teže utege, veći ili manji broj ponavljanja u seriji, veći ili manji broj serija, brze ili spore pokrete, dulje ili kraće pauze i tako dalje – a tu je i prehrana i sve ostalo.

Tako i ovdje, u matematici i informatici, vjerojatno nije svejedno na koji način vježbamo. Parametri su brojni kao i u sportu. Valja li vježbati pomalo svakodnevno, ili vikendom u većim blokovima vremena? Je li važno doba dana i radno okruženje? Iz kojih izvora rješavati zadatke, i kakve težine – rješive, umjerene ili teže? Koliko se dugo samostalno boriti sa zadatkom prije traženja pomoći ili čitanja rješenja? Dobro testirati lokalno ili odmah poslati na online judge? Simulacije natjecanja ili freestyle? Je li slučajan odabir zadataka za vježbu možda i najbolji jer sadrži najtočnije postotke pojedinih tema/područja? Ili je bolje čitati knjige, prolaziti tutorijale i rješavati zadatke po temama, tako da unaprijed znamo neke elemente rješenja? Koliko zadataka upsolvati i vrijedi li se mučiti sa zadatkom koji nam je pretežak? Nažalost, većina se ovih pitanja još i umnaža jer odgovori ovise i o nivou znanja, a možda i o osobnosti onoga koji vježba. Odgovori sigurno nisu isti za Peru Perića i Ivana Katanića.

Nemam pojma, ali nije baš svejedno, jer vrijeme je ograničeno. Moje, kao i svačije iskustvo u ovim pitanjima vrlo je usko jer je nemoguće isprobati više metoda na istom nivou znanja i onda razlikovati rezultate jedne ili druge metode. Kao što sportska znanost odgovore na analogna pitanja pronalazi desetljećima, trebalo bi možda stvoriti i granu psihologije koja bi se bavila problem-solvingom. Za početak bismo smjernice mogli potražiti u psihologiji učenja. Volio bih čuti vaša mišljenja u komentarima.

Dokaz ostavljamo čitateljici za vježbu

U opisima algoritama, koji su dio objavljenih rješenja većine domaćih natjecanja, nerijetko se na kraju opisa rješenja pojedinog zadatka pojavljuje rečenica “Dokaz točnosti algoritma ostavljamo čitatelju za vježbu”. Ili čitateljici, da ne bi tko pomislio da autori imaju predrasude. Tako smo u rješenjima Studentskog 2018. u čak tri zadatka ostavili dokaz točnosti ili efikasnosti algoritma za vježbu upravo čitateljici.

Navedena rečenica nije karakteristična samo za opise algoritama, ona se često viđa i u matematici i sličnim znanostima. No koje je njezino pravo značenje?

Iz iskustva, rečenica može imati tri moguća značenja:

  1. Dokaz ostavljamo čitatelju za vježbu jer je točnost ili efikasnost algoritma, ako se on čita s razumijevanjem i ako se o njemu malo promisli, prilično očita i dokaz je bolje izostaviti da bi čitatelj malo zastao i razmislio o pročitanom. (Ovo je slučaj u zadatku Stablo u stablu sa spomenutog Studentskog.)
  2. Dokaz ostavljamo čitatelju za vježbu jer smo u se u točnost tvrdnje uvjerili intuitivno, a znali bismo je i dokazati, ali dokaz nije lako ukratko napisati i vjerojatno bi bio ružnjikav. (Ovo je slučaj u zadatku Ploča sa spomenutog Studentskog, kao i npr. u zadatku Sails – IOI 2007.)
  3. Dokaz ostavljamo čitatelju za vježbu jer tvrdnju ne znamo sami dokazati. (Ovo je slučaj u zadatku Načitan sa spomenutog Studentskog za neparan N, a skoro je bio slučaj i u zadatku GTA s Izbornih priprema 2014.)

Postoji i četvrti slučaj – autor rješenja izostavlja ne samo dokaz, nego i navedenu rečenicu, praveći se da je sve jasno, iako nije. Krunski primjer je zadatak Mravograd (Državno 2007.) koji je poznat po kratkom i lijepom rješenju za koje nije očita ni točnost, a pogotovo efikasnost tj. složenost algoritma. Do ključne zamjedbe dolazi se određenim koracima u razmišljanju koji su u službenom opisu izostavljeni. Drugim riječima, rješenje nije napisano metodički. No budući da se radi o zadatku za malo jaču publiku, autor (Luka Kalinovčić, ako se ne varam) nije nas podcijenio: čitatelji (i čitateljice, naravno) sposobni su sami ispuniti rupe u rješenju. A ta je rupa generiranje slučajnih primjera i promatranje u kojim se oblicima pojavljuju traženi “mokri trgovi”. Odatle se dolazi do tražene ideje.

U praksi je, dakle, i empirijski dokaz često dovoljan. Ionako u implementaciji griješimo češće nego u ideji. Testiranje rješenja usporedbom sa brute-forceom i generatorom slučajnih primjera u praksi je odličan dokaz. (To zaboravljaju neki natjecatelji naviknuti na online evaluatore i full feedback i onda griješe na županijskom ili HONI natjecanju.) Nedavno je Errichto pisao o jednom manje uobičajenom načinu testiranja. Ja sam je iskoristio nedavno, kada sam za zadatak Dionice (autora Domagoja Bradača) s ovogodišnjeg županijskog natjecanja pisao rješenje radi provjere. Nisam htio implementirati potpuno isti algoritam kao Domagoj (jer što ako je slučajno pogrešan), nego sam odlučio zadani niz gledati unatrag i primijeniti analogan algoritam u obrnutom smjeru. Dobio sam iste rezultate, što je empirijski potvrdilo točnost algoritma. Domagoj je doduše napisao dokaz, ali kao što ovaj odlomak sugerira, matematički dokaz nikad nije dovoljan jer ljudi griješe (zabrijavaju). U matematici se stvari dokazuju, a u drugim znanostima (kao i u životu) stvari se testiraju.

Dakle, pravo značenje rečenice “Dokaz ostavljamo čitatelju za vježbu” upravo je ono koje čitatelj svjesno ili nesvjesno percipira čim pročita tu rečenicu. Ono glasi: “Formalni dokaz nije bitan”. Bitno je da se čitatelj na ovaj ili onaj način uvjeri u istinitost tvrdnje. Primjerice, ako želimo podijeliti prirodne brojeve A i B tako da količnik zaokružimo na više, možemo ga dobiti kao (A + B – 1) div B. Na jednoj radionici nije mi se dalo objašnjavati zašto je tako pa sam rekao “dokažite za domaću zadaću”. Naravno, nisam očekivao da itko to formalno dokaže koristeći najveće cijelo i nejednakosti. U ovom slučaju dovoljno se uvjeriti na primjerima promatrajući nekoliko bitnih slučajeva. Dokazivanje je samo formalizacija intuicije, iako je taj stav općenito diskutabilan. Razmislite o njemu sami, za vježbu.

Dvije stablaste fore

Za neko ukorijenjeno stablo, poredajmo vrhove stabla u niz onim redom kojim ih dohvaćamo DFS obilaskom iz korijena. Taj niz ima svojstvo da svako podstablo čini interval, tj. uzastopni podniz. (Ako dva vrha pripadaju nekom podstablu, onda se između njih u nizu nalaze samo vrhovi iz istog podstabla.) Koristeći taj niz, neki upit na podstablu svodi se na upit na intervalu niza. Nekoliko zadataka koji koriste tu foru:

No posljednji zadatak mnogo je lakše riješiti koristeći manje-u-veće trik. Ako imamo neke skupove od ukupno N elemenata i želimo ih spajati jedan u drugi dok ih sve ne spojimo (spajanja čine stablo), i ako pri spajanju dvaju skupova pazimo da uvijek prebacujemo elemente iz manjeg skupa u veći, svaki element će biti pomaknut najviše log(N) puta jer svakim prijelazom dolazi u barem duplo veći skup. To možemo koristiti kad neke informacije dižemo iz listova prema korijenu stabla, u svakom čvoru spajajući skupove koje smo prethodno izračunali za njegovu djecu, kao u navedenom zadatku Distinct colors. Tim je trikom moguće riješiti i Stablo u stablu iz gornje liste – to je uspjelo Anti Đereku dok smo pripremali zadatak. Još jedan zadatak s tim trikom: Loza (HIO 2010.).

Još zadataka slobodno linkajte u komentarima.

Digresija: Dedekindovi brojevi

Na koliko načina možemo svakom broju iz skupa S = {1, 2, …, N} pridružiti 0 ili 1? Drugim riječima, koliko ima funkcija iz S u {0, 1}?

Well, that’s easy – dvije mogućnosti za 1, puta dvije mogućnosti za 2, puta dvije mogućnosti za 3, i tako dalje, ukupno 2^N.

Idemo dalje: na koliko načina možemo svakom podskupu od S pridružiti 0 ili 1? Drugim riječima, koliko ima funkcija iz skupa svih podskupova – partitivnog skupa P(S) u {0, 1}?

Analogno prethodnome, to je 2^K gdje je K broj podskupova, jer za svaki podskup biramo 0 ili 1. A koliki je K? Podskup kreiramo tako da svaki broj u njega stavimo ili ne stavimo (dvije mogućnosti), dakle K = 2^N. Traženih je funkcija, dakle, 2^{2^N}.

Idemo dalje…

Na koliko načina možemo svakom podskupu od S pridružiti vrijednost 0 ili 1, ali tako da dodavanjem elemenata u podskup njegova vrijednost može samo porasti? Drugim riječima, koliko ima monotonih funkcija f : P(S) \to \{0, 1\}, što znači da je f(A)\le f(B) za sve A\subset B?

Nemamo pojma, ali na prvi pogled možemo brutati, tj. napisati program koji ovo prebraja za dovoljno mali N. Što mislite, koliko mali?

Riječ je o N-tom Dedekindovom broju, a ono što je fascinantno je da već za N = 9 nitko nije uspio izračunati taj broj. Postoji formula, ali ona nije zatvorena, tj. sadrži sumaciju pa u suštini i nije formula nego spori pseudokod.

Osmi Dedekindov broj izračunat je još 1991. godine i to uz pomoć pametnih trikova za smanjenje složenosti. Osim u izvornom članku, taj algoritam možete pronaći i ovdje. Iako su se od tada računala ubrzala stotinu i više puta, deveti Dedekindov broj još uvijek je nedohvatljiv. A ima 40ak znamenaka, prava sitnica. Evo vam prilike da se upišete u povijest matematike.

Čini mi se da trenutačno znanje o Dedekindovom problemu nije dovoljno da bi se osmislio dovoljno efikasan algoritam za N = 9, ma koliko ga pametno optimizirali. Potrebna je nova spoznaja o samom problemu, neki novi teorem koji će omogućiti pojednostavljenje formule.

Ok, so what? Ima mnogo neriješenih problema u matematici; zašto sam baš o ovome pisao? Zato što izgleda rješiv (naglasak je na izgleda, a ne na rješiv :)) i zato što, čini mi se, trenutačno ne zanima ozbiljne matematičare pa konkurencija nije jaka. Ako nas dvadeset navali na problem, dovoljno je da svatko izračuna samo dvije ili najviše tri znamenke. Računala će se još ubrzati, a iskustvo nas uči da zadatak s ograničenjem N ≤ 10 ne može biti težak.

Tema dana: konstrukcijski zadatci

Ad hoc zadatke (kojima je adhocness level 4-5) teško je uvježbati. Oni su s jedne strane dobri za informatička natjecanja jer su originalni, ali s druge strane ponekad favoriziraju matematičare i one koji su manje iskusni u znanju/kodiranju (ali su zato bistriji). Je li to dobro ili loše, ne znam, no ispalo je da su zadatci koji su meni kao autoru tijekom godina padali na pamet često bili konstrukcijski ad hoc. Ovdje sam takve odlučio sabrati, ne kao nekakvu lekciju – jer takvi zadatci nisu osobito poučni – nego iz čistoga gušta. Podijelio sam ih u kategorije s obzirom na veličinu inputa.

– Ulaz je niz i slično:

– Ulaz su dva broja:

– Što mislite koliko je (netrivijalnih) konstrukcijskih zadataka moguće napraviti tako da im je ulaz jedan jedini broj? Quite a lot, as it turns out. Izgleda da sam od početka nesvjesno prihvatio taj izazov jer sam ih dosad složio (barem) osam, a možda sam neki i zaboravio:

Tip of the day: granice intervala

U pretpretprošlom postu kao jednu od točaka spomenuo sam “neelegantno baratanje donjim i gornjim granicama intervala” kao jednu od početničkih mana u kodiranju. Koje je onda elegantno baratanje?

Uz oznake L i R za lijevu i desnu granicu (left i right), najbolje je brojevima L i R označiti interval {L, L+1, …, R-1}; dakle, interval [L, R> kojemu je donja granica uključena, a gornja isključena. Ta asimetrija može se isprva učiniti neelegantnom, ali ona nam zapravo pojednostavljuje život:

  • Veličina intervala jednostavno je R – L. (Kad bi obje granice bile uključene, bila bi R – L + 1.)
  • Intervali se na ovaj način lako i prirodno nadovezuju: [A, B> + [B, C> = [A, C>. Ovo je korisno u mnogim “podijeli pa vladaj” pristupima gdje se interval dijeli na dva manja, primjerice u tournament stablu: [L, R> dijelimo na [L, mid> + [mid, R>.
  • Na ovaj način možemo pokriti i slučaj kad je interval prazan: L = R.

Druge prednosti koje mi nisu pale na pamet slobodno dopišite u komentare. Jedan od rijetkih slučajeva gdje koristim drugačiji princip (interval [L, R] kojemu su obje granice uključene) jest binarno pretraživanje, iako mnogi i ondje koriste gornji princip.

Princip “donja uključena, gornja isključena” koriste standardni oblici for petlje u većini programskih jezika: sjetite se kako radi range u Pythonu ili najčešća petlja for (i=0; i < n; ++i) u jeziku C. Sve je to povezano i s činjenicom da su nizovi uglavnom indeksirani od nule, tako da se niz duljine N nalazi na indeksima iz intervala [0, N>. Kraj je isključen: u C++u ćete znati da ste došli do kraja STL containera (vector, string, set, map…) kada naiđete na s.end(), primjerice u petlji: for (it = s.begin(); it != s.end(); ++it) ili u provjeri if s.find(element) == s.end() kao znak da element nije pronađen.

Zašto sve ide od nule? Mnogo je razloga, čak i matematičkih. Brojevi koje možete zapisati s K binarnih znamenaka čine interval [0, 2K >. Ostatci modulo N su 0, 1, …, N-1. Koristite li hash tablicu s modulom N, jasno je da su upravo to indeksi koji vam trebaju. Ili, ako se po nizu krećete ciklički, kad povećate indeks za proizvoljan korak, dovoljno ga je modati s N da dobijete pravi indeks (N -> 0, N+1 -> 1, N+2 -> 2, …). Općenito se formule pojednostavljuju: pogledajte npr. odgovore na https://www.quora.com/Why-do-array-indexes-start-with-0-zero-in-many-programming-languages.