Zadatak dana: Cow School

Postoji trik koji se ponekad javlja da bismo ubrzali rješenja optimizacijskih (min/max) zadataka. Riječ je o transformaciji u geometrijsku domenu gdje je lakše vizualizirati stvari, skužiti što treba tražiti i tako smanjiti složenost. Taj trik ljudi ponekad zovu “dinamika s pravcima” jer se često javlja u ubrzanju prijelaza dinamike. Mislim da se koristi i naziv envelope.

Ovdje je taj trik ugrađen u ne-dinamički zadatak, za koji je profesor Brian Dean (USA Computing Olympiad) još prije desetak godina ispričao (snimio) rješenje na pametnoj ploči i tako popularizirao ovaj trik. Autori zadatka su dvije legende natjecateljskog programiranja, Bruce Merry i Richard Peng.

Zadatak: http://poj.org/problem?id=3266

Analiza: http://contest.usaco.org/TESTDATA/JAN07.schul.htm

Video s rješenjem: http://www.cs.clemson.edu/~bcdean/cowschool.swf — preuzmite i pokrenite (nekim flash playerom ili na http://flashplayer.fullstacks.net/ – povećajte width i height).

Još zadataka na ovu temu slobodno stavljajte u komentarima.

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