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.

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.