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.

Jedna misao o “Tema dana: duguljaste matrice

Komentiraj

Popunite niže tražene podatke ili kliknite na neku od ikona za prijavu:

WordPress.com Logo

Ovaj komentar pišete koristeći vaš WordPress.com račun. Odjava /  Izmijeni )

Google+ photo

Ovaj komentar pišete koristeći vaš Google+ račun. Odjava /  Izmijeni )

Twitter picture

Ovaj komentar pišete koristeći vaš Twitter račun. Odjava /  Izmijeni )

Facebook slika

Ovaj komentar pišete koristeći vaš Facebook račun. Odjava /  Izmijeni )

Spajanje na %s