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.

HONI i rješenje kao niz zamjedbi

(Najprije sam napisao “niz opservacija”, i ekipa zaista koristi riječ “opservacija” dok “zamjedbu” ne koristi nitko, no evo, smatram da je ova riječ bolja i malo trendsettinga neće mi škoditi.)

Ako je zadatak dobar, proces smišljanja rješenja vjerojatno neće biti binaran – od “nemam pojma” do “aha, smislio sam” u jednom trenutku – nego će se sastojati od nekoliko stepenica od kojih ćemo na svakoj uočiti nešto što će nas dovesti malo bliže rješenju. (Zapnemo li na nekoj od njih, možda možemo skupiti djelomične bodove – “parcijalu” iz sekcije Bodovanje).

Kao primjere tih stepenica navest ću tijek svojih misli prilikom čitanja i razmišljanja o zadatcima 2-5 s jučerašnjeg HONI-ja (a možda i 6-7 u idućem postu). Ovo je i doprinos objavljivanju rješenja s tog natjecanja, koja je bolje objaviti što prije, jer interes za rješenjima eksponencijalno pada kako vrijeme od natjecanja prolazi.

Zadatak Glasovi

Zamjedba #1. U većini slučajeva, gljive su u istoj košari kad im je isti cjelobrojni količnik pri dijeljenju s K.

Zamjedba #2. Poseban slučaj: ako je gljiva djeljiva s K, ona zapravo pripada prethodnoj košari (s obzirom na svoj količnik).

Zamjedba #3. Poseban slučaj: ako je bilo koja od zadanih dviju gljiva u istoj košari kao posljednja (N-ta gljiva) i pritom N nije djeljiv s K, odgovor je NE.

Zadatak Magnus

Zamjedba #1. Znam tko je Magnus (a bome znam i tko je Kile).

Zamjedba #2. Sva slova koja nisu H, O, N, I možemo bez pardona odmah izbaciti (jer su beskorisna).

Zamjedba #3. Mogu izbaciti sva slova s početka riječi dok ne dođem do slova H (jer su beskorisna).

Zamjedba #4. Nakon što sam našao H, mogu izbaciti sva sljedeća slova dok ne dođem do slova O (jer su beskorisna).

Zamjedba #5. Mogu izbacivati sljedeća slova dok ne dođem do slova N i potom sljedeća dok ne dođem do I. Tako sam dobio jedan HONI-blok.

Zamjedba #6. Prethodne korake (pronalazak H, O, N, I) ponavljam dok god mogu i to je rješenje.

Zadatak Pismo

Zamjedba #1. Ne znam tko je Kasap.

Zamjedba #2. Ako uzmem cijeli niz kao interval, dobit ću najveću (a ne najmanju) razliku max – min.

Zamjedba #3. Uvijek se isplati smanjiti interval, tj. izbaciti neke brojeve iz njega, jer tako njegova razlika max – min može samo opasti, ne i narasti.

Zamjedba #4. Dovoljno je promatrati intervale koji se sastoje od samo dvaju susjednih brojeva.

Zadatak Sajam

Zamjedba #1. Redoslijed operacija nije važan.

Zamjedba #2. Ako dvaput napravimo istu operaciju, kao da je nismo ni napravili, tj. svaku ćemo napraviti 0 ili 1 puta.

Zamjedba #3. Prvo ću smisliti jednostavniji slučaj kad je K = 0, tj. flipam samo retke i stupce.

Zamjedba #4. Ako fiksiram prvi redak (s flipom ili bez njega), točno znam koje stupce moram flipati (a koje ne smijem) da bih ga cijeli pogasio. I onda samo provjerim ostale retke.

Zamjedba #5. Općenito, ako kažem da ću tek na kraju flipati stupce, zadatak se svodi na izjednačavanje redaka (bez flipanja stupaca).

Zamjedba #6. Ako postoji redak gdje se ne koristi posebno flipanje ćelije, dovoljno je njega fiksirati i provjeriti koliko mi treba operacija (više ili manje od K) da ostale retke s njim izjednačim.

Zamjedba #7. To je ipak sporo, ukupno O(N3).

Zamjedba #8. U drugom slučaju, ako je K = N i ako se u svakom retku posebno flipa jedna ćelija, dovoljno je za prvi redak odabrati i fiksirati ćeliju koju flipamo te napraviti istu provjeru.

Zamjedba #9. Pristupom iz prethodnih zamjedbi, na točan raspored flipanja možemo naići mnogo puta, fiksirajući bilo koji njegov redak koji ima nula ili jednu flip ćeliju.

Zamjedba #10. Takvih je redaka u svakom scenariju barem N/2, a jedan od njih pogodit ćemo u npr. 20 slučajnih odabira, što je daje složenost O(20 * N2).

Tip of the day: code review

Sve ozbiljne softverske firme imaju praksu code reviewa, što znači da svaki napisani kod mora proći pregled nekog drugog člana tima prije nego što uđe u pogon, tj. postane dio proizvoda. To nije testiranje, koje se obavlja prethodno, tijekom programiranja. To je doslovno čitanje koda. Čak i najboljim zaposlenicima netko drugi mora pročitati kod, iako je prethodno već testiran. Svrha je stvaranje boljeg koda, ne toliko u smislu otkrivanja bugova (iako se nađe onih koje testovi nisu uhvatili), nego uočavanje stvari koje se mogu napraviti drugačije, elegantnije, pravilnije, sigurnije, robusnije, organiziranije, čitljivije za kasnije održavanje/nadogradnju itd.

Ova praksa u natjecateljskom programiranju nije uobičajena. Ako smo riješili zadatak i prolaze svi primjeri, zašto bismo se vraćali na kod koji je ispravan? Ipak, ako je kod ispravan, ne znači nužno da je dobro napisan i da će način na koji smo ga pisali biti dobar i u budućim, težim zadatcima. Zato je korisno baciti oko i na tuđe kodove da bismo iz njih nešto naučili. No jednako je korisno da netko drugi baci oko na naš kod. Tako neki mentori, voditelji grupa ili radionica (u MIOC-u, HSIN-u, ZRS-u…) odvajaju dio svog vremena da barem površno pogledaju kodove svojih učenika i ukažu im na stvari koje se mogu bolje. Čak i za vrlo dobre natjecatelje vrijedi: kad im netko bolji/iskusniji pogleda kod, uočava stvari koje se mogu poboljšati.

Početnički primjeri uključuju:

  • slabu čitljivost koda, npr. škrtarenje s razmacima i redcima (kako ćete debugirati kod koji je napisan gusto i zbrda zdola?),
  • nekonzistentna ili manjkava stilska obilježja (vidi npr. ovaj post),
  • nedeskriptivna imena varijabli – teško ćete se snaći u većem kodu ako vam se varijable zovu a,b,c,d,e,f,g,h,
  • glomazne porcije koda (umjesto organiziranja u funkcije) i kao posljedica kod koji je teško testirati dio po dio i debugirati,
  • duplikacija, tj. isti/sličan dio koda prisutan na više mjesta (lakše se griješi i teže se mijenja) umjesto izdvajanja u funkciju,
  • suvišne varijable i nepotrebno kompliciranje koda (odražava neurednost misli),
  • neefikasne petlje – npr. korištenje dvostruke gdje je dovoljna jedna,
  • neefikasno spremanje podataka u polja/parove/strukture,
  • deklaracije na lošem mjestu (uz neke iznimke, doseg varijabli treba biti najmanji mogući),
  • loše organizirani slučajevi (“puno ifova”) i formule u kojima je lako pogriješiti – te stvari spominjao sam i ovdje,
  • neelegantno baratanje donjim i gornjim granicama intervala (“jel tu sad ide > ili >=? plus jedan ili minus jedan?”),
  • računanje istih podataka više puta, npr. unutar neke petlje, umjesto da se unaprijed izračunaju,

i mnogi drugi. Nakon što se savladaju osnove, poboljšanja koda uglavnom su vezana uz konkretan algoritam i njegove implementacijske varijante. Istina je da vještina kodiranja kod početnika raste jako brzo, a s vremenom sve sporije (logaritamska krivulja), ali čitajući kodove boljih od sebe uvijek se mogu naučiti novi trikovi.

Tip of the day: atomske navike

U jednom od prijašnjih postova napisao sam sljedeću rečenicu: Ono što presuđuje, tj. razdvaja uspješne od onih koji su samo daroviti, ne samo na natjecanjima nego općenito, zove se disciplina. Htio bih napisati malo više o disciplini, budući da sam upravo pročitao odličnu knjigu o toj temi, a zove se Atomic Habits Jamesa Cleara. Riječ je o hrpetini korisnih trikova za produktivnost u bilo čemu, pa onda i u primjerice matematici ili programiranju. Poklonite si je za Božić!

Neki su ljudi prirodno disciplinirani. Sklonost organiziranosti, koja se u psihologiji mjeri kao savjesnost, uvelike ovisi o genima, kao i ostale crte ličnosti koje su dobrim dijelom predodređene. (Isto vrijedi za inteligenciju, ali ako se bavite matematikom ili natjecateljskim programiranjem, vjerojatno je imate u solidnoj mjeri, i to uglavnom možete zahvaliti čistoj sreći.) Na natjecanjima sam viđao one koji su uspijevali primarno zahvaljujući inteligenciji, kao i one koji su uspijevali primarno zahvaljujući upornosti. Oni koji su bili inteligentniji uglavnom su bili uspješniji. Ali među onima podjednake inteligencije, broj uloženih sati rada činio je veliku razliku.

Moguće je da nemate visoku savjesnost, ali jako uživate u onome čime se bavite i/ili imate veliku motivaciju za pobjeđivanjem. Tada vam ne treba disciplina: dovoljno ste motivirani za rad i bez planiranja. No entuzijazam je nekad prisutan, a često i nije. Veliku razliku čini vježbanje baš u ono vrijeme kad nam se ne da. Ako niste naročito organizirani, a to vrijedi za mnoge visoko inteligentne ljude koje sam viđao po natjecanjima, trebaju vam trikovi da biste izgradili konzistentne navike kao što je, recimo, svakodnevno vježbanje u vidu rješavanja barem jednog zadatka u određeno vrijeme.

Evo jednog prijedloga: svakoga dana u 19 sati riješite prvi zadatak s neke stare Codeforces runde – Div1, Div2 ili Div3, ovisno o vašem nivou. Ako vam je zadatak prelagan, a u tome i jest poanta, svejedno ga riješite. Za početak je važno samo stvoriti svakodnevnu naviku, a to je moguće samo ako je ona lagana: svi znamo da je snaga volje bullshit u trenutcima kad nismo motivirani – kad nam se baš i ne da. Zato je važno da je zadatak lagan. Ako ste nakon njegovog rješavanja dovoljno motivirani, rješavajte iduće zadatke, još bolje. Ali to u prvoj fazi stvaranja navike nije važno: cilj je samo održavati neprekinuti lanac na kalendaru. I to papirnatom! Križanje datuma olovkom nakon obavljenog posla odličan je osjećaj. Nakon dva do tri tjedna, kad vam svakodnevno vježbanje postane rutina, prijeđite na teže zadatke – one koji su “taman” težine tako da su vam izazovni, ali ih u većini slučajeva možete riješiti vlastitim naporima i ponekad uz malo nečije pomoći. Ne smiju biti preteški, jer pokazano je da se idealna razina motivacije stvara na optimalnoj težini izazova, takvoj da uspijevamo otprilike 50% puta. Ta se težina s vremenom i napretkom prirodno povećava.

Tip of the day: CSES Problem Set

Danas sam nabasao na odličnu arhivu kratkih i poučnih zadataka: https://cses.fi/problemset/list/ – idu od lakših prema težima i pokrivaju većinu bitnih tema natjecateljskog programiranja.

Na stranici ima još problemsetova, npr. ovdje možete simulirati i upsolvati Baltičke olimpijade: https://cses.fi/boi/list/

CSES problemset usko je povezan s knjigom Anttija Laaksonena pisanom tako da bude u skladu s programom međunarodne olimpijade.

Zadatci sa studentskog

Prije desetak dana održan je VRSIH 2018, mislim da su bili zgodni zadatci. Budući da su danas objavljena rješenja zadataka, može započeti njihov upsolving.

Zadatci su na natjecanju bili poredani po abecedi, a radi pristupačnosti ovdje ih redam po težini, uz neke usputne komentare. Izradu zadataka je vodio Ante Đerek, a sudjelovali smo i Ivan Paljak, Luka Kalinovčić, Mislav Balunović, Ivan Katanić, Gustav Matula i ja.

  1. Luka – preskočite osim ako ste početnik
  2. Flauta – koderski
  3. Menza – Ovaj zadatak nastao je tako što sam nekad davno morao smisliti kako efikasno provjeriti natjecateljsko rješenje na zadatku Pekar.
  4. Načitan – Ovo nije prvi (a vjerojatno ni posljednji) od mojih zadataka čiji je input jedan jedini broj. Zna li netko dokazati minimalnost rješenja za neparan N?
  5. Alloc – U tekstu možda nedostaje napomena da je dozvoljeno da se dvaput pozove malloc s istom varijablom, npr. “aaaa=malloc(10); aaaa=malloc(20);” pri čemu “free(aaaa)” oslobađa samo posljednji blok.
  6. Stablo u stablu – Poučna fora na stablu. Nekoliko sličnih zadataka: Path Union, Kingdom and its Cities
  7. Ploča – “matematički”, dobar za clear thinking, autor Luka Kalinovčić
  8. Hulja – geometrijski, autor Ivan Paljak
  9. Reality – odlična fora, autor Ivan Paljak
  10. Ghost leg – Meni je pao na pamet, Gustav Matula ga je riješio, a Luka Kalinovčić pripremio i napisao opis.

Kao što postoji zadatak dana, zadatak tjedna i zadatak mjeseca, tako postoji i zadatak natjecanja. U ovom slučaju to bi vjerojatno bio Ghost leg zbog lijepog i nestandardnog rješenja. Taj zadatak treba staviti na neki međunarodni judge poput Spoja; bilo bi super ako ima dobrovoljaca za to! A i za druge teže zadatke, kad se nađe vremena.