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.

Tema dana: duguljaste matrice

Dok sam bio srednjoškolski natjecatelj, netko mi je poslao zip s desetak tekstualnih dokumenata u kojima je (legenda) Luka Kalinovčić, tada mentor u ZRS-u i HSIN-u, opisao nekoliko algoritama i riješio nekoliko zadataka. Budući da su neki od tih tekstova vrlo poučni, odlučio sam ih podijeliti u ovoj i nekim budućim objavama.

Jedna od tema u toj mapi bila je i “Exponential time DP”, tj. dinamičko programiranje s eksponencijalnom složenosti. Takva složenost obično nastaje kada u stanju dinamike držimo “masku”, najčešće binarni broj čije nam znamenke 0-1 kazuju koje smo od N objekata dosad odabrali/iskoristili a koje nismo, pa je broj mogućih stanja (npr. 2N) eksponencijalan.

Naravno, to ima smisla samo ako je N iz gornjeg odlomka relativno malen. Ako je taj N jedna dimenzija neke matrice, koja dakle ima malen broj redaka (ili stupaca), govorimo o “duguljastoj matrici”. Promotrimo, primjerice, sljedeći zadatak:

Na koliko načina možemo popločiti sobu dimenzija R x S pločicama oblika kao na slici? (2 R ≤ 100, 2 ≤ S ≤ 10). Rješenje ispišite modulo 220.

tri

Primjeri:

ulaz: 2 3

izlaz: 2

ulaz: 4 3

izlaz: 4

ulaz: 9 8

izlaz: 204184

ulaz: 47 9

izlaz: 6656

Dakle, zadani broj stupaca je najviše 10, dok broj redaka može biti do 100, pa je matrica “duguljasta”. Za veći broj stupaca zadatak bi bio daleko teži (ako bi uopće bio rješiv). Rješenje zadatka i njegovu implementaciju dao je Luka Kalinovčić u već spomenutoj prastaroj mapi, a odgovarajući dokument nalazi se ovdje.

Drugi Lukin primjer nalazi se u ovom dokumentu gdje se rješava zagonetka kakva se redovito nalazi u našim novinama.

Zadatci za vježbu:

  • Tiling a grid with dominoes – najlakši zadatak ovog tipa.
  • Star – nije baš matrica :), na prvu može uplašiti, ali nakon malo razmišljanja…
  • Pattern transformation – mnogo smjerova, ali jako male dimenzije, u prijelazu možemo birati cijelu masku sljedećeg retka!
  • EEPROM – Izborne pripreme 2007.
  • Tiles – praktički isti zadatak kao Bugs Integrated, Inc. sa CEOI 2002. – dakle, ova je stvar bila korištena i prije 16 godina, ali samo troje ljudi je tada riješilo zadatak na CEOI-u.
  • Poligoni – Izborne pripreme 2013., jedan od težih zadataka iz moje radionice.

IOI, IPSC i nestandardni zadatci

Ovoga tjedna u Japanu se održava IOI 2018., najprestižnije natjecanje srednjoškolaca u programiranju. Pratimo trenutačne rezultate; nakon jučerašnjeg prvog dana natjecanja najbolja iz našeg tima je Paula Vidas – svaka čast!

Nisam gledao jučerašnje zadatke, ali IOI zadatci uglavnom su vrlo kvalitetni, zbog važnosti natjecanja i vremena koje majstori iz ISC-a (International Scientific Committee) ulože u izradu zadataka. Ponekad se pojavi novi tip zadatka kakav do tada nije bio uobičajen. Naime, u IOI Syllabusu – dokumentu koji navodi teme koje se mogu pojaviti – postoji kategorija Outside of focus koja sadrži sve teme koje nisu spomenute u dokumentu, dakle, beskonačno mnogo njih. Za njih vrijedi: “This does not prevent the inclusion of a competition task that is related to a particular topic from this category. The ISC may wish to include such a competition task in order to broaden the scope of the IOI.”

Primjeri nestandardnih zadataka s prethodnih IOI:

  • Languages (IOI 2010.), prepoznavanje jezika; kao i Art Class (IOI 2013.), prepoznavanje stila slike – koketiranje s umjetnom inteligencijom i strojnim učenjem.
  • Saveit (IOI 2010.), treba napisati dva odvojena programa od kojih prvi šalje informaciju drugome koristeći što manje bitova – “komunikacijska složenost”, čuo sam da je bilo i još takvih zadataka.
  • Odometer (IOI 2012.), svojim programom generiramo drugi (traženi) program.

Naravno, nestandardnih i mnogo luđih zadataka na manje ozbiljnim natjecanjima (kao što je CF April Fools Contest) ima mnogo više.

To nas dovodi do online natjecanja IPSC koje se održava za mjesec dana i koje se temelji na neobičnim zadatcima: “Internet Problem Solving Contest pushes the boundary of what is possible in programming competitions.” Natjecanje je jako popularno i preporučujem svima da se na njemu zabave u timovima do troje ljudi.

Za kraj bih naveo nekoliko “ludih” zadataka s naših natjecanja:

  • Šetnja (Državno 2014.) – prvo pojavljivanje “challenge” zadatka u osnovnim školama,
  • Esej (HONI 2015.) – lagan, ali netipičan zadatak,
  • Janje aka Vesela bojanka (HONI 2015.) – genijalan zadatak Ivana Paljka na tri stranice.

Tema dana: podijeli pa vladaj

Ova prezentacija čini mi se kao dobar uvod u temu, s nekoliko klasičnih primjera. (Preskočite slajdove s dokazima složenosti koji su previše matematički.)

Zadatci za vježbu:

Inversion count –> rješenje možete naći u ovoj prezentaciji

Ultimate Orbs (CSAcademy)

Graškrižja (HONI)

Mravograd (izvorno DMIH 2007.)

Hrpa zadataka u A2 arhivi

Na ovom zadnjem linku pogledajte i cijeli sajt, mogao bi vam postati dobro mjesto vježbanja.