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.

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