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.

Tip of the day: upsolving

Upsolving je pojam koji, čini se, potječe od Rusa i/ili Codeforcesa. Riječ je o rješavanju zadataka koje niste riješili na natjecanju (ili na simulaciji natjecanja).

Ovako je glasio Tip of the day Ante Đereka za sudionike IOI priprema 2016.:

Prije dosta vremena sam se ‘pripremao’ na topcoderu na sljedeci nacin: Odabrao bih prethodni contest, brzo bih napravio dva laksa zadatka, razmisljao bih 10ak minuta o tezemu, odustao i vise se na njega nisam vratio. Jedino sto sam tako naucio je bilo kako da malo brze kodiram zadatke koje vec znam 🙂

Bitan dio priprema je rjesavanje zadataka koji su ostali nerijeseni na natjecanju jer jedino tako ucite nove stvari. Nije potrebno da idete glavom kroz zid, ako nema napretka nakon 15ak minuta razmisljanja procitajte rjesenje (potpuno ili djelomicno), pitajte nekoga za hint i onda ponovo probajte rijesiti zadatak.

Nažalost, ljudska psihologija je takva da se mnogi poslije natjecanja ne žele vraćati na zadatke s natjecanja, pogotovo ako na tom natjecanju nisu bili uspješni. Poruka ovog posta je da nadiđete taj osjećaj. Dakle, ako se natječete na Codeforcesu, AtCoderu, CSAcademyju ili TopCoderu, ili možda samo na HONI-ju, Boži Težaku, županijskom, državnom ili HIO-u, napredak ćete postići samo na jedan način:

Pravilo natjecateljskog programiranja #1: Nakon svakog natjecanja ili simulacije natjecanja, bez iznimke, riješite barem jedan zadatak koji niste riješili na tom natjecanju. Čitanje rješenja je dozvoljeno, čak se i preporučuje.

Ono što presuđuje, tj. razdvaja uspješne od onih koji su samo daroviti, ne samo na natjecanjima nego općenito, zove se disciplina.