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

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

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.

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.

Tema dana: pseudošuma

Nekoliko zadataka o pseudošumama s raznih judgeva (ima ih sigurno i mnogo više):

Codechef: Chirag and Array

Zatemas: Katapult, Babe

Spoj (originalno DMIH, HONI, IOI): Youtube, Dugovi, Islands

GCJ: Best friends

CEOI 2006: Link

Nadopuna: u većini gornjih zadataka zapravo je riječ o usmjerenim pseudošumama ili, ekvivalentno, funkcijskim grafovima. Neka vas ne uplaše ovi pojmovi: riječ je jednostavno o usmjerenim grafovima gdje iz svakog vrha točno jedan brid izlazi van (x \to f(x)). Svaka povezana komponenta toga grafa sadrži jedan ciklus i nekoliko usmjerenih stabala spojenih na taj ciklus.

Adhocness level

Ponekad se raspravlja o tome što je dobar, a što loš zadatak. Ako izuzmemo težinu kao faktor koji manje-više pozitivno korelira s kvalitetom zadatka, najčešće se govori o tome je li zadatak “klasičan” ili je “ad hoc”, tj. je li “stoput viđen algoritam” ili ne koristi neki poznati algoritam nego je rješenje vrlo specifično za dotični zadatak.

Naravno, većina zadataka nije ni potpuno klasična ni potpuno ad hoc, a tako i treba biti. Mana klasičnih zadataka je što više testiraju teorijsko znanje nego dosjetljivost, dok neki ad hoc zadatci mogu biti previše “matematički” u smislu da se rješenje smišlja na papiru dok se ne nađe odgovarajuća “formula” koja se na kraju prepiše u smiješno kratak kod.

Da bismo bolje opisali ovaj raspon zadataka (tj. njihovih rješenja), predlažem sljedeću skalu – tzv. adhocness level: od 0 (premalo ad hoc) do 5 (previše ad hoc).

0 – Zadatci koji su čista implementacija nekog viđenog algoritma/strukture bez ikakvog razmišljanja ili značajne modifikacije. Dobri za učenje algoritma, ali loši za natjecanja ili vježbanje smišljanja. Primjeri: Super Mario, Ventilator

1 – “Klasični” zadatci – svode se na primjenu nekog poznatog algoritma/strukture čija primjena nije odmah očita ili je potrebno smisliti neku netrivijalnu modifikaciju. Znatno bolji od zadataka nivoa 0, ali još uvijek daleko od vrhunskih zadataka. Primjeri: George, Kaos, Aerodrom

2 – “Tehnički” zadatci, u kojima je realizacija teža od osnovne ideje, tj. preko 50% težine zadatka otpada na low-level detalje (iako i dalje mogu biti teški za smisliti). Ovakvi zadatci zbog specifičnosti nisu klasični, ali nisu nužno ni ad hoc jer i dalje mogu sadržavati neki poznati algoritam.

Naravno, ako je riječ o čistim koderskim, acslovskim zadatcima koji su obične simulacije nekih zadanih pravila, takvi zadatci su niske kvalitete. Ali u ovu kategoriju ubrajam i mnogo bolje, načelno teže zadatke, gdje se detalji i slučajevi u rješenju pojavljuju prirodnije. Ovdje se mišljenja razilaze – za neke je riječ o ružnim zadatcima, ali mislim da je tu riječ “ružno” samo sinonim za “meni je to teško, hoću doma”. Izazovna implementacija velika je prednost zadatka – testira vjerojatno najvažniju vještinu programera i može biti jako satisfakcijska ako se lijepo razradi. Kao neklasični, ali i daleko od “matematičkih”, ovo mogu biti odlični zadatci. Primjeri: Snake (memory limit!), Loza, Islands

3 – Zadatci gdje je primjena poznatog algoritma jako neočita, ili je poznati algoritam samo dio relativno originalnog (većinom ad hoc) rješenja, ili je zadatak prirodno višeidejni – zahtjeva neočitu primjenu više poznatih algoritama/struktura. Ovo su odlični zadatci. Primjeri: Wordplay, Mravograd, RP

4 – Ad hoc zadatci koje je moguće riješiti bez znanja algoritama, no i dalje zahtijevaju algoritamski način razmišljanja i/ili razumnu vještinu programiranja. Načelno dobri zadatci, ali blago favoriziraju matematičare, tj. one koji su vještiji u smišljanju nego kodiranju. Primjeri: Palin, Šetnja, Tvrtka

5 – Zadatci koji su “matematički” u smislu da bi u nekom obliku mogli komotno proći kao logičko-kombinatorni na neko matematičko natjecanje te ne zahtijevaju gotovo nikakvu vještinu programiranja nakon smišljanja rješenja. Mogu biti lijepi, ali nisu najprikladniji za informatička natjecanja (jedan po natjecanju bi mogao proći). Primjeri: Infokuhar, ABCD, Remove

Naravno, ovo je samo gruba podjela i za mnoge zadatke teško je jednoznačno odrediti kojem nivou (0-5) pripadaju. Volio bih čuti feedback na ovu skalu.