Digresija: matematika i (neki) matematičari

Prekjučer se pojavio zanimljiv članak o nesporazumu nekolicine velikih matematičara o tome je li Japanac Shinichi Mochizuki dokazao ABC hipotezu ili nije, a budući da jedan od sudionika te priče ima veze s matematičkim natjecanjima i jednom sam ga prilikom upoznao, došlo mi je napišem ovaj post.

Ne razumijem se u područje nimalo, ali koliko sam shvatio, Mochizukijev dokaz u četiri rada na ukupno 500 stranica ne razumije nitko osim samog Mochizukija; riječ je o novoj teoriji koja uvodi hrpu novih koncepata te osim ABC hipoteze rješava još neke otvorene probleme. Ozbiljni matematičari možda bi ignorirali takve nastranosti da Mochizuki i sam nije ozbiljan matematičar s prethodnim značajnim rezultatima. Ovako je privukao pažnju 30-godišnjeg matematičara Petera Scholzea koji je zajedno sa svojim kolegom Jakobom Stixom u ožujku otputovao u Kyoto da bi Mochizukiju objasnio zašto mu dokaz ne valja, na što je Japanac odgovorio da oni ništa ne kuže.

Peter Scholze nije bilo tko, on je dobitnik Fieldsove medalje, “matematičkog nobela”. Prije deset godina potražio sam ga na IMO-u 2008. (tada je vodio njemački tim) jer je prethodnih godina bio iznimno uspješan natjecatelj. Kad sam ga pitao postoji li osoba koja može riješiti bilo koji zadatak koji se pojavi na IMO-u ili Shortlistu, rekao je da je on takva osoba, ali to nije rekao hvalisavim ili ponosnim tonom. Također mi je rekao da, kad se pripremao za natjecanja, uglavnom nije čitao rješenja nego bi zadatak koji ne zna riješiti uvijek ostavljao za poslije.

Suprotnu stvar rekao mi je još uspješniji IMO-vac Iurie Boreico, osvajač nekoliko perfect scoreova na IMO-u i posebne nagrade za rješenje nejednakosti na IMO-u 2005. Njega nisam upoznao, ali sam ga bio kontaktirao na MSN-u (messenger iz nekih davnih vremena). On mi je tada savjetovao da, barem u početku, bez pardona čitam rješenja zadataka koje ne znam riješiti. Zanimljivo. Ne sjećam se svega, no možda je taj savjet bio u kontekstu mog početništva, jer tada još nisam bio IMO-vac.

Kome je bolje vjerovati? Vjerojatno osvajaču Fieldsove medalje. Uz Iuria se vežu neke zanimljivosti, npr. to da je trenutačno “Algorithmic Trader at Jump Trading LLC” (info s LinkedIna). Dakle, jedan ima više para, drugi je veća faca, ali obojica su legende.

Tema dana: duguljaste matrice

Dok sam bio srednjoškolski natjecatelj, netko mi je poslao zip s desetak tekstualnih dokumenata u kojima je (legenda) Luka Kalinovčić, tada mentor u ZRS-u i HSIN-u, opisao nekoliko algoritama i riješio nekoliko zadataka. Budući da su neki od tih tekstova vrlo poučni, odlučio sam ih podijeliti u ovoj i nekim budućim objavama.

Jedna od tema u toj mapi bila je i “Exponential time DP”, tj. dinamičko programiranje s eksponencijalnom složenosti. Takva složenost obično nastaje kada u stanju dinamike držimo “masku”, najčešće binarni broj čije nam znamenke 0-1 kazuju koje smo od N objekata dosad odabrali/iskoristili a koje nismo, pa je broj mogućih stanja (npr. 2N) eksponencijalan.

Naravno, to ima smisla samo ako je N iz gornjeg odlomka relativno malen. Ako je taj N jedna dimenzija neke matrice, koja dakle ima malen broj redaka (ili stupaca), govorimo o “duguljastoj matrici”. Promotrimo, primjerice, sljedeći zadatak:

Na koliko načina možemo popločiti sobu dimenzija R x S pločicama oblika kao na slici? (2 R ≤ 100, 2 ≤ S ≤ 10). Rješenje ispišite modulo 220.

tri

Primjeri:

ulaz: 2 3

izlaz: 2

ulaz: 4 3

izlaz: 4

ulaz: 9 8

izlaz: 204184

ulaz: 47 9

izlaz: 6656

Dakle, zadani broj stupaca je najviše 10, dok broj redaka može biti do 100, pa je matrica “duguljasta”. Za veći broj stupaca zadatak bi bio daleko teži (ako bi uopće bio rješiv). Rješenje zadatka i njegovu implementaciju dao je Luka Kalinovčić u već spomenutoj prastaroj mapi, a odgovarajući dokument nalazi se ovdje.

Drugi Lukin primjer nalazi se u ovom dokumentu gdje se rješava zagonetka kakva se redovito nalazi u našim novinama.

Zadatci za vježbu:

  • Tiling a grid with dominoes – najlakši zadatak ovog tipa.
  • Star – nije baš matrica :), na prvu može uplašiti, ali nakon malo razmišljanja…
  • Pattern transformation – mnogo smjerova, ali jako male dimenzije, u prijelazu možemo birati cijelu masku sljedećeg retka!
  • EEPROM – Izborne pripreme 2007.
  • Tiles – praktički isti zadatak kao Bugs Integrated, Inc. sa CEOI 2002. – dakle, ova je stvar bila korištena i prije 16 godina, ali samo troje ljudi je tada riješilo zadatak na CEOI-u.
  • Poligoni – Izborne pripreme 2013., jedan od težih zadataka iz moje radionice.

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.

Tema dana: podijeli pa vladaj

Ova prezentacija čini mi se kao dobar uvod u temu, s nekoliko klasičnih primjera. (Preskočite slajdove s dokazima složenosti koji su previše matematički.)

Zadatci za vježbu:

Inversion count –> rješenje možete naći u ovoj prezentaciji

Ultimate Orbs (CSAcademy)

Graškrižja (HONI)

Mravograd (izvorno DMIH 2007.)

Hrpa zadataka u A2 arhivi

Na ovom zadnjem linku pogledajte i cijeli sajt, mogao bi vam postati dobro mjesto vježbanja.

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.

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.