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.

Tema dana: clear thinking

Prije više od deset godina, na nekom starom ZRS-ovom forumu koji je odavno ugašen, postojala je tema koja se zvala “Najbolji zadatak” ili nešto slično. Ondje je (legenda) Goran Žužić linkao nekoliko zadataka koje smatra odličnima. Ako se dobro sjećam, za jedan od tih zadataka Goran je napisao otprilike ovo: “Svi ga mogu riješiti, ali prvo si morate neke stvari u glavi raščistiti“.

Rješavajući zadatak bilo mi je jasno što je Goran mislio. Zadatak nije težak, osnovna ideja brzo se uviđa, ali ne možete ga odmah na brzinu isprogramirati. Morate razmisliti te pažljivo i što elegantnije pokriti sve detalje i slučajeve. To ne možete ako vam “stvari u glavi nisu raščišćene”. I bit će vam teško bez papira i olovke.

To vrijedi za gotovo sve “tehničke zadatke” čiji je adhocness level jednak 2. Ako je baratanje slučajevima važan i prirodan dio rješenja kao u gore spomenutom zadatku (a ne da je riječ o simulaciji u kojoj je nabrojeno deset pravila), to su odlični zadatci. Umjetnost njihovog rješavanja uključuje pametno i smisleno kategoriziranje slučajeva te smišljanje rješenja koje ih pokriva elegantno, sa što manje muke (ifova i slično), te nije bug-prone tj. napisano je tako da minimizira vjerojatnost pogreške. Takvi zadatci rade razliku između “urednih” i “neurednih” programera, između onih koji su sustavni, pažljivi, temeljiti te onih drugih, koji su možda genijalni ali im nedostaje malo koderske discipline i sistematičnosti jer su im stvari u glavi više razbacane nego složene. Vježbanje takvih zadataka čini način razmišljanja ljepšim i čišćim.

(Primjer početničkog bug-prone rješenja: širenje na osam susjednih polja u matrici možete napraviti koristeći osam ifova, u svakom navodeći susjeda (x-1, y-1) ili (x-1, y) ili (x-1, y+1) ili (x, y-1) ili (x, y+1) ili (x+1, y-1) ili (x+1, y) ili (x+1, y+1) – eto vidite, već sam pogriješio – i  pišući poseban kod za svaki od tih parova, što još umnaža mogućnost pogreške. Ili lijepo kažete ovako:

for i in range(8):
    susjed_x = x + [-1, -1, -1, 0, 0, 1, 1, 1][i]
    susjed_y = y + [-1, 0, 1, -1, 1, -1, 0, 1][i]
    # provjera itd

 

Ne samo u takvim zadatcima, nego gotovo uvijek, za urednost misli pomažu papir i olovka. Na papiru slobodno riječima pišite natuknice pa i pune rečenice: tako će vam i misli biti jasnije i dorečene te ćete ih lakše pretočiti u kod. Ne žurite, niste na Codeforcesu. (Osim kad ste na Codeforcesu. Ali ni tada, jer kao što već znate, sigurno ćete pogriješiti.)

Mali slučajevasti problemset, ugrubo po težini:

  1. The Longest Chain of Domino Tiles
  2. The Next Palindrome
  3. Lights, Snakes and Cages
  4. Zmaj
  5. Vandal
  6. Poduzeće
  7. Best Friends

Tip of the day: pravilno tipkanje

Otipkajte bilo koju rečenicu i odgovorite na sljedeće pitanje: koliko ste prstiju koristili? Zadatak Strojopis vrlo je poučan, i to ne zbog njegovog rješenja (koje nije naročito zanimljivo), nego zbog njegove priče. Njezina je poanta: programirajte koristeći svih deset prstiju na engleskom rasporedu tipaka. Te dvije stvari treba uvježbati istodobno.

Ne morate kupiti novu tipkovnicu, nego samo postaviti standardni US keyboard layout u postavkama operacijskog sustava. Na toj “engleskoj tipkovnici” česte koderske znakove poput ; [ ] { } \ = (a ima ih još) lakše je napisati. Ako je na vašoj fizičkoj tipkovnici označen hrvatski raspored, neko vrijeme trebat će vam “šalabahter” na ekranu dok ne upamtite gdje je koji znak na US rasporedu. Općenito naučite da nikada ne gledate u fizičku tipkovnicu: ako vam je to navika, naručite si blank tipkovnicu. U početku je učenje gnjavaža, ali poslije…

Tipkanje koristeći deset prstiju najbolje je uvježbati koristeći neki od online alata poput ovoga. Ideja je da svi prsti osim palčeva mirno počivaju na srednjem redu tipkovnice i da svaku tipku pritisne njoj najbliži prst – ali nemojte sami procjenjivati kojim prstom što pritisnuti, nego vjerujte alatu za učenje.

Pravilno tipkanje nije najvažnija stvar na svijetu: IOI zlato moguće je osvojiti i pišući trima prstima na hrvatskoj tipkovnici. No budući da je tipkanje desetorma prstima udobnije, jednom kad ga dobro uvježbate, bit ćete motiviraniji za rad: kodiranje će biti ne samo brže, nego i znatno ugodnije. Kad shvatite koliko je ljepše kad su vam šake uglavnom nepomične za vrijeme tipkanja, kodiranje će postati kao kad stari zahrđali bicikl zamijenite novim dobro podmazanim.

(Jezični tip: ne putujemo “s tramvajem” nego “tramvajem”, pa tako i ne tipkamo “s prstima” nego tipkamo “prstima”, bilo da je dvama prstima, trima, četirima, petorima ili desetorma prstima. Žalbe šaljite Hrvatskom jezičnom portalu ili Hrvatskom institutu za jezik i jezikoslovlje.)

Extra tip: eliminirajte potrebu za mišem, tj. za nepotrebnim micanjem ruke s tipkovnice i ponovnim vraćanjem da biste izveli radnju koju je sigurno moguće izvesti tipkovnicom. Zanimljivo je da smo lijeni guglati i naučiti kako određene stvari izvesti samo tipkovnicom (npr. za web browsing postoji dodatak Vimium – tipneš F i pored svakog linka na stranici vidiš slovo koje ga otvara), ali zato nam nije problem trošiti sate na navigaciju mišem i beskrajno putovanje ruke na relaciji miš – tipkovnica. I ja to radim, a znam da ne bih trebao. Kao što reče jedan moj prijatelj, lijenost je najbolja osobina programera jer ga tjera da pronađe prečace kojima štedi vrijeme i olakšava si posao. To je sve, naravno, mnogo lakše ako eliminirate nezgrapne i skupe Windowse i prijeđete na besplatan i za većinu programera daleko bolji Linux (npr. Ubuntu). Živcira me kad ljudi po defaultu pretpostavljaju da njihov sugovornik (npr. ja) posjeduje Windows, Word, PowerPoint itd. Ali to je već druga tema.

Tema dana: mravlji problemset

Budući da je danas Međunarodni dan mrava i mravlje kiseline, vrijeme je da se prisjetimo dobrih starih hrvatskih zadataka u kojima glavnu ulogu imaju mravi. Zato sam složio ovaj lijepi mravlji problemset. Zadatci su ugrubo poredani po težini.

  1. Zadatak Kolone
  2. Zadatak Mravojed
  3. Zadatak Mravi
  4. Zadatak Mrav
  5. Zadatak Mravi
  6. Zadatak Mravi
  7. Zadatak Ludi
  8. Zadatak Mravi
  9. Zadatak Mravi
  10. Zadatak Mravograd

CX9HaVD

Tip of the day: if manji if veći

Jeste li ikada riješili zadatak na foru ovog tipa: ako je N < 100 onda je efikasan jedan algoritam, a inače je efikasan drugi algoritam?

Drugim riječima, rješenje je kombinacija dvaju algoritama od kojih ni jedan ne rješava cijeli zadatak, ali svaki od njih rješava “pola” slučajeva koji se mogu pojaviti, tako da u uniji ti algoritmi čine potpuno rješenje.

Zadatak V (HONI 2007.)

Zadatak Broj (HONI 2012.)

Zadatak Utjecaj (Izborne pripreme 2017.)

Zadatak Rectangles

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.