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.

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.

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

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.