Dvije stablaste fore

Za neko ukorijenjeno stablo, poredajmo vrhove stabla u niz onim redom kojim ih dohvaćamo DFS obilaskom iz korijena. Taj niz ima svojstvo da svako podstablo čini interval, tj. uzastopni podniz. (Ako dva vrha pripadaju nekom podstablu, onda se između njih u nizu nalaze samo vrhovi iz istog podstabla.) Koristeći taj niz, neki upit na podstablu svodi se na upit na intervalu niza. Nekoliko zadataka koji koriste tu foru:

No posljednji zadatak mnogo je lakše riješiti koristeći manje-u-veće trik. Ako imamo neke skupove od ukupno N elemenata i želimo ih spajati jedan u drugi dok ih sve ne spojimo (spajanja čine stablo), i ako pri spajanju dvaju skupova pazimo da uvijek prebacujemo elemente iz manjeg skupa u veći, svaki element će biti pomaknut najviše log(N) puta jer svakim prijelazom dolazi u barem duplo veći skup. To možemo koristiti kad neke informacije dižemo iz listova prema korijenu stabla, u svakom čvoru spajajući skupove koje smo prethodno izračunali za njegovu djecu, kao u navedenom zadatku Distinct colors. Tim je trikom moguće riješiti i Stablo u stablu iz gornje liste – to je uspjelo Anti Đereku dok smo pripremali zadatak. Još jedan zadatak s tim trikom: Loza (HIO 2010.).

Još zadataka slobodno linkajte u komentarima.

Tip of the day: granice intervala

U pretpretprošlom postu kao jednu od točaka spomenuo sam “neelegantno baratanje donjim i gornjim granicama intervala” kao jednu od početničkih mana u kodiranju. Koje je onda elegantno baratanje?

Uz oznake L i R za lijevu i desnu granicu (left i right), najbolje je brojevima L i R označiti interval {L, L+1, …, R-1}; dakle, interval [L, R> kojemu je donja granica uključena, a gornja isključena. Ta asimetrija može se isprva učiniti neelegantnom, ali ona nam zapravo pojednostavljuje život:

  • Veličina intervala jednostavno je R – L. (Kad bi obje granice bile uključene, bila bi R – L + 1.)
  • Intervali se na ovaj način lako i prirodno nadovezuju: [A, B> + [B, C> = [A, C>. Ovo je korisno u mnogim “podijeli pa vladaj” pristupima gdje se interval dijeli na dva manja, primjerice u tournament stablu: [L, R> dijelimo na [L, mid> + [mid, R>.
  • Na ovaj način možemo pokriti i slučaj kad je interval prazan: L = R.

Druge prednosti koje mi nisu pale na pamet slobodno dopišite u komentare. Jedan od rijetkih slučajeva gdje koristim drugačiji princip (interval [L, R] kojemu su obje granice uključene) jest binarno pretraživanje, iako mnogi i ondje koriste gornji princip.

Princip “donja uključena, gornja isključena” koriste standardni oblici for petlje u većini programskih jezika: sjetite se kako radi range u Pythonu ili najčešća petlja for (i=0; i < n; ++i) u jeziku C. Sve je to povezano i s činjenicom da su nizovi uglavnom indeksirani od nule, tako da se niz duljine N nalazi na indeksima iz intervala [0, N>. Kraj je isključen: u C++u ćete znati da ste došli do kraja STL containera (vector, string, set, map…) kada naiđete na s.end(), primjerice u petlji: for (it = s.begin(); it != s.end(); ++it) ili u provjeri if s.find(element) == s.end() kao znak da element nije pronađen.

Zašto sve ide od nule? Mnogo je razloga, čak i matematičkih. Brojevi koje možete zapisati s K binarnih znamenaka čine interval [0, 2K >. Ostatci modulo N su 0, 1, …, N-1. Koristite li hash tablicu s modulom N, jasno je da su upravo to indeksi koji vam trebaju. Ili, ako se po nizu krećete ciklički, kad povećate indeks za proizvoljan korak, dovoljno ga je modati s N da dobijete pravi indeks (N -> 0, N+1 -> 1, N+2 -> 2, …). Općenito se formule pojednostavljuju: pogledajte npr. odgovore na https://www.quora.com/Why-do-array-indexes-start-with-0-zero-in-many-programming-languages.

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.

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.