Savezno 2004. Ideje za neke zadatke ...

na sajtu www.yuoi.nis.edu.yu mogu da se skinu zadaci.
zadatak koji mene najvishe zanima je sledeci :

Mene ovo najvishe asocira na dinamichko programiranje, ali nikako ne mogu
da provalim formulu...
Inache, zanimaju me ideje josh i za 4. i 5. zadatak.

Potpis

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Slazem se da je neukusno. Politiku na stranu, ajmo po zadatku.

Moja ideja - ne garantiram da je tocna ili da ce dati rjesenje u prihvatljivom vremenskom roku. Neka svaki kat predstavlja jedan cvor grafa (broj kata neka je odmah i oznaka cvoar grafa).

Pretpostavimo miniranje kata i. Ovisno o tezini vode na tom katu, tezini vode i izdrzljivosti katova ispod, proces rusenja katova ce se zaustaviti na nekom katu j. Tada se u grafu povuce brid od cvora i do cvora j. Bridu se dodjeljuje oznaka (w, c) gdje je w ukupna tezina vode na j-tom katu nakon rusenja, a c je cijena rusenja kata i.

Iz svakog kata i=2..n povucemo brid sa oznakom (w, c) do odgovarajuceg kata j.

Kada je graf konstruiran, nad grafom se izvrsi Dijkstrin algoritam pocevsi od vrha 1 uzimajuci za udaljenost komponentu c para (w, c) kojim je oznacen brid. Rezultat ce biti "najjeftiniji" put do svakog vrha i=2..n (ukupna cijena puta je najjeftinija cijena rusenja kata 1 ako se pocinje od kata i).

Pocevsi od vrha s najjeftinijom cijenom, pratimo put od tog vrha do vrha 1 i usput se zbrajaju tezine w kojima su obiljezeni bridovi. Najjeftiniji put ciji zbroj tezina vode (w) nadmasuje limit L_1 je rjesenje zadatka.

Sad, ima nekoliko problema.

1. MISLIM da je moguce konstruirati bridove grafa u jednom prolazu kroz vrhove, ali jos nisam razradio rjesenje.

2. Dijkstrin algoritam nad cijelim grafom ima slozenost O(n^2) gdje je n broj vrhova grafa. Zadatak dopusta do n=100000=10^5 katova. To daje oko 10^10 operacija. Nemam ideje koliko dugo bi to trajalo.

3. Odabir najjeftinijeg redoslijeda katova. U najgorem slucaju potrebno je ispitati svih n-1 puteva (n-1vi ce ispasti jedini koji ima dovoljnu tezinu da srusi sve katove ispod).

Vremenom izvrsavanja dominira 2. korak ako se 1. moze napraviti u O(n) (a mislim da moze uz puno dodatne memorije).

Ovaj, bez uvrede, ali nisam bash skontao shta znache neke rechi kljuchne
za objasnjenje zadatka koje je dao zvrba.
Shta znachi "kat" i "brid"?

Moderatora bih zamolio da pobrishe offtopic teme ...

Potpis

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Kat - sprat.
Brid - (iz konteksta) grana ili ivica.

Ne znam koliko je efikasno, ali da probam.

Koliko vidim, ti moraš da izazoveš lančanu reakciju, pošto dizanje nekog sprata u vazduh ne koristi mnogo ako se ta bujica vode zaustavi negde iznad prvog sprata. Pošto ta najjeftinija lančana reakcija mora da ima najviši sprat (pa makar on bio i prvi), kreni od najvišeg sprata i za svaki sprat (počevši od poslednjeg) izazovi lavinu do (ispod) prvog i zapamti cenu i taj sprat (čisto da bi na kraju rekonstruisao scenario).

Lančana izgleda ovako:
Digneš n-ti sprat u vazduh, povećaš cenu i gledaš gde će voda da se zaustavi. Zatim digneš u vazduh taj sprat, zaračunaš cenu i opet pratiš dokle se spuštaš (ne zaboraviš da sabiraš zapreminu vode). Tako nastaviš do propadanja prvog.

Uf, opet mi je obrisana upadica o dinamiskom programiranju, mislim da nije offtopic jer se spominje u postavci teme :).

Dakle sta je to dinamicko programiranje, ako ti mirise na to, onda pojasni sta je tacno, da li je to odrejeneo secenje brute force varijante ili pak neko unosenje slucajnosti ?

Uzgred zasto nisi probao grubom silom da resis zadatak ?

Potpis

CHUPCKO

Gle, dinamicko programiranje je metoda optimizacije. Primjenjiva je u slucaju da optimalno rjesenje manjeg problema vodi optimalnom rjesenju veceg problema. Problem se pocinje rjesavati od najmanje instance, pamte se sva rjesenja i onda se na temelju tih zapamcenih rjesenja rjesavaju vece instance problema.

Za detalje trazi na googleu "dynamic programming" i mozes dodati "tutorial".

Ne ne ne, nije prepoznata moja ironija, oko metode i naziva metode :).
Ali ajde, cini mi se da je dinamicko programiranje, ono sto je bilo objektno orjentisano pre nekih 10 goidna, magicna mantra koja sve resava :).

P.S. Cak sam pre nekih 5 godina pisao radove koji koriste te metode, ali nisam znao da se to zove tako :)...

Da se vratimo na temu, da li si probao metodu grube sile ?

Potpis

CHUPCKO

Dinamicko programiranje je citava jedna nauka za sebe. Stvorena je u cilju pronalazenja resenja sa sto je moguce manje koraka. Ovog trenutka mogu da se setim samo 'metode severozapadnog ugla' (ipak, davno bese), ali ima tu jos dosta toga. Dinamicko programiranje NEMA nikakve veze sa objektnim programiranjem ili bilo kojom drugom vrstom IMPLEMENTACIJE resenja; mozes da pises postupak resenja u cemu god hoces (recimo Fortranu).

Rajko

Ej bre ljudi, ala ga vi zakomplikovaste ovde :)

Pa Chupcko, zar ne mislish da je ogranichenje malo preveliko da bi se
probao brute force? I shta ti imash toliko protiv dinamichkog? :)

Potpis

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Pa samim tim mu je ime pogresno , to je opis metodologije kako se resava :), kao rekurzija recimo :).

Mozda da si samo pazljivije procitao sta sam napisao shvatio da sam pricao o mistifikaciji pojma.

Dakle defintino dinamicko programiranje nije programiranje, nego metodologija filtriranja medju svim resenjima (obicno gruba sila).

A poredjenje sa objektno orjentisanim je samo podsecanje na jos jednu mistifikaciju (koja traje jos i danas, zar ne :) ).

Ali ajde, da kazemo da je sve ustvari dinamicko programiranje :).

Recimo racunanje kvadratnog korena je dinamicko programiranje, kako, pa lepo:

Napisemo za pocetak neki prost petlja program (oo evo novog izraza: petlja programiranje) koji ide od 0 do n, uvecavajuci za 1 i ceka da i^2 bude vece od n.

Primeticemo da je algoitam puno spor (mada za 1 radi lepo :) ). Primenimo neke ustede ...

Trt mrt i eto nam dinamickog programiranja :).

Naci cu recimo jedan moj stari esej, pa cemo svi prepoznati dinamicko programiranje u njemu .

Dakle lepo je to dinamicko programiranje :)))), ali daj mi primer nekog koji nije dinamicko :), ja cu ti prepoznati metode dinamickog u njemu :)))).

P.S. Jel se seca neko "samomodifikujuceg programiranja"

Potpis

CHUPCKO

Preuzecu rizik da gresim, ali moram opet da offtopic-ujem:

Chupcko, kad tako lepo shvatas znacenje izraza, onda objasni deci zasto
se Linearno programiranje tako zove?
Funkcionalno programiranje takodje? Kako su mene ucili, Dynamic
programming se ne koristi samo u programiranju,
vec i u nekim granama matematike :) Nebitno, Joca terorista moze zgradu
srusiti na razne nacine, a jedan od njih
je i "ono nesto dinamicko" :)

--
Visit my photo log at http://www.fotolog.net/mucky

Kakve ustede?


Pa ako si pocetni algoritam izmenio tako da pamtis resenja preklapajucih podproblema onda je to dinamicko programiranje. Ja uopste ne shvatam sta je problem sa pojmom dinamicko programiranje?


Npr. algoritam za nalazenje Fibonacijevog broja rekurzijom. Gde tu vidis dinamicko programiranje?

Da ne bih bio potpuno offtopic da odgovorim na postavljeni zadatak.
Mozes da krenes od poslednjeg sprata i za svaki sprat da pravis listu od kojih svaki clan sadrzi dva podatka: kolicinu vode koja ode sa tim spratom i minimalna cena za to. Posle za sprat ispod koristis listu sa prethodnog da napravis novu listu. Lista ne treba da ti sadrzi podatke za kolicine vode preko 219 jer nema potrebe. Ako dobijes kolicinu vecu od 210 onda samo zapamti za 219.

Na ovaj nacin ce ti program brzo naci resenje. Pocnes od najviseg sprata za koji ces imati listu od samo jednog clana koji sadrzi kolicinu vode sa tog sprata i cenu za rusenje tog sprata.

Drugi nacin za resenje je da pamtis listu cena za rusenje tog sprata i maksimalnu kolicinu vode koja pri tome moze da ode na donji sprat.

Naci cu negde, ali dok nadjem :)...

Dinamicko programiranje je "postupal" kojim od jednog algoritma dobijas drugi (gde se menja slozenost), zar ne :).

E sada, ja kazem da za svaki algoritam B postoji algoritam A tako da je algortiam B nastao primenjujuci postupke dinamickog programiranja nad algoritmom A.

E jos da to dokazem :).

Sada mi je mnogo jasnije sta je to dinamicko programiranje, steta samo sto nisam pre znao da ga tako zovem dok sam ga primenjivao :).

A offtopic, ja i dalje nisam video da je iko pokusao brute force :) slozenost je samo n! na prvu loptu :).

Potpis

CHUPCKO

Ne, nije svejedno kako menjas postupak. Fora je da koristis preklapajuce osobine podproblema. Tek onda bi mogao da menjanje slozenosti nazoves dinamickim programiranjem.


Samo? Pa nije ni cudo sto niko nece to da pokusava da implementira. A ako mislis na ideju, ne verujem da nisu pokusali ali sto bi se zamarali ljudi da pisu na forum ideju koja nije dobra za implementaciju?

Pa da, koristeci tu metodu dinamickog programiranja :)

To jel domaci za doktorske studije negde u americi :).

Brute force je lep jer tek kada pogledas tako napisan program mozes pronaci invarijatne i odredjene podprobleme i razne metodologije ....

Ono sto meni smeta je naziv, nije to programiranje, nego metodologija analize ipoboljsanja perfomansi koristeci razne funkcije. Mozda jednom ispricam o mom programu za trazenje pokrivanja pentomimima (lep primer secenja brute force metode, a mngo bi rekli, pa to je dinamicko programiranje).

Meni smeta sto neko daje tako idiotski naziv necemu sto je normlano :).

Potpis

CHUPCKO

Pozdrav svima!

Prvo offtopic o DP: svi kojima smeta naziv dinamicko programiranje neka lepo smisle neki lepi naziv u duhu srpskog jezika, pa neka to razglase medju programerskom zajednicom...

A sad o zadacima:

3: ideja koja donosi 90 poena: napisete greedy koji ide na obrnutu stranu od logicne ( ne znam tacno kako ali meni je proslo na takmicenju ), i nadate se da su test primeri debilni ( kao sto su i bili ); ideja za 100 poena: DP u nlogn, primenom kumulativnih tabela...

4: najjednostavnija Dijkstra, samo sto ( skoro ) niko nije dobro implementirao obrtanje kockice, zadatak je trivijalan....

5: divide and conquer, primeni se ideja slicna quicksort-u ( nosi 86 poena ) ili randomized quicksort-u ( 100 poena ) iako je zadatak uradjen po strategiji sa papira nosio oko 60 poena....

Offtopic 2: Rajko jako si zaboravan, sve smo ti ovo ispricali jos dok smo se vracali sa saveznog... Ako ti treba neki info, pomoc, algoritam.... slobodno pisi posto "obozavani direktor" nece organizovati pripreme ove godine ( izgleda )....

Offtopic 3: Kakve veze ima koji je tekst zadatka sa tim da li je zadatak dobar ili ne? Prica o teroristima je naravno jako glupa, ali nije najgluplja, pogledajte zadatak Artemis ( prvi dan IOI 2004 ), tekst je ultra glup narocito deo sa fudbalskim igralistem ( koji je tu zbog velike ljubavi jednog od clanova ISC-a prema fudbalu )...

Setih se onogo vica o morskom prasetu. Znate vec, to je onaj vredjajuci vic o slicnosti izmedju zene programera i morskog praseta :).

E od sada ga pricam ali u varijanti sa morskim prasetom i dinamickim programiranjem :).

Dakle nije u pitanju duh srpskog jezika (jel nam se tako zove jezik ?) nego smislenosti :).

Salu na stranu, izgleda da je Danica jasno rekla koje metode mogu da se koriste :).

Potpis

CHUPCKO

Dinamicko programiranje:
http://en.wikipedia.org/wiki/Dynamic_programming

Naziv ni na engleskom nema mnogo smisla, ali to i nije bitno. Nauci sta je i to je to.
Zapravo predstavlja resavanje problema indukcijom.

Nauka nekada podrazumeva i kriticki odnos ka necemu sto posmatras :), pa makar moja zamerka bila ime :).

Kako bese, morsko prase niti je morsko niti prase :).

I da li na kraju ima neko da postuje resenje :))))

Potpis

CHUPCKO