Savezno 2004. Ideje za neke zadatke ...

Sve u svemu, vrlo lepa ideja, i neverovatno glupa formulacija zadatka.
Sad sam se bas zainteresovao; pokusacemo nesto...pa mozda i postujemo.

Rajko

Srki, mislim da tvoje resenje sa listom nece raditi, ne vidim kako uzima u obzir da gornji sprat nije optimalan za rusenje.

Citajuci i ostale postove, izgleda da nismo uspeli da nadjemo neko dobro resnje :/

Uzima u obzir ali mozda nisam lepo objasnio. Rekao sam da listu za odredjen sprat pravis na osnovu prethodnog sprata i kolicine vode koja ode sa prethodnog sprata i cenu za to.

Zar to onda nije opet losije od O(n^2)? Ako te ne mrzi, molim te napisi alogirtam u pseudokodu - jasan mi je deo za liste, ne moras to da razradjujes.

Ako imamo niz cene[n], voda[n], maksimalnavoda[n] onda uradimo nesto ovako:

I to je to.
Na kraju samo treba videti clan sa najmanjom cenom iz lista[1].

E da, podrazumeva se da u listu ne ubacujemo clanove kod kojih je kolicina vode veca od maksimalne za jedan sprat koja je u uslovima zadatka tj. 218.
Pod takvim uslovima slozenost zadatka je O(n)

Ajde sada da prodjemo kroz pseudokod koristeci primer iz prve poruke:
Imamo 4 sprata.
10 50 100 (tezina vode na tom spratu, maksimalna moguca tezina vode, cena)
0 100 3
100 100 2
10 50 6

E u prvoj liniji lista[5]={ (0,0) }
Posle imamo lista[4]={ (10,6) };
lista[3]={ (100,2), (110,6) }
lista[2]={ (100,5), (110,6)}
lista [1]={ (10, 100) , (100,5), (110,6) }

Iz lista[1] vidimo da je najmanja cena 5.

Evo da probam da kažem nešto na zadatu temu.

Najpre u vezi s dinamičkim programiranjem. Slažem se da je naziv pomalo nesrećan, pošto je jelte svaki program posledica programiranja; što bi sad pa to dinamičko bilo posebnije od svih ostalih? Ne bih se složio sa onima koji kažu da je dinamičko programiranje korišćenje rekurzije, jer se zapravo svaki program može izraziti rekurzivno. O tome govori ta, u par navrata pominjana, Čerčova teza.

Kada pišete program, rekurzije se obično izravnaju da bi cela stvar bila manji zalogaj za računar, pa se zato u samim sorsovima pojavljuju retko. Ali rekurzivni programi su neverovatno važni kada se algoritam izmišlja. To je zato što svaki rekurzivni program možemo da izrazimo preko samo tri bitna sastojka: početnog uslova, induktivne hipoteze i induktivnog koraka. To su jedine tri stvari koje treba zapamtiti.

Dosta često ljudi o programima razmišljaju tako što pokušavaju u glavi da izvrše sve instrukcije, korak po korak, vodeći računa o međurezultatima. Upoznao sam nekoliko ljudi koji mogu da isprate program do u neverovatnu dubinu, ali IMHO to je rasipanje resursa. Gde bi im bio kraj da tu metodologiju zamene samo sa tri gorepomenute stvari; definišite ih i pustite da indukcija odradi ostatak posla za vas.

Naravno da je problem nabosti pravu induktivnu hipotezu, i induktivni korak da bi se sve razmotalo kako treba (obično početni uslov nije glavobolja), ali jednom kad ste to uradili, prepevavanje na jezik petlji i uslova je čista nizbrdica. (Ovde ću malo da se ponovim pa da kažem da Udi Manber u svojoj knjizi Introduction to Algorithms: a creative approach objašnjava isto ali mnogo tačnije, bolje i lepše; pogledajte ako možete, nećete se razočarati:)

Evo jedan bez veze primer koji (kao) objašnjava onaj deo sa rekurzijama. Treba da se napiše program koji štampa sve brojeve od 1 do 10. Retko ko bi trepnuo dvaput pre nego što bi smislio nešto poput:



Ajde sad da probamo da isto to napravimo, samo rekurzivno. Ideja je da se napravi funkcija koja uradi parčence posla a ostatak svede na sebe, samo malo manju. Ovde nije preterano teško da se sredi ispis. Brojeve od 1 do 10 ispisaćemo tako što ispišemo prvo 1, a zatim ispišemo sve ostale (od 2 do 10). Kada ova dva koraka posmatramo zajedno, treba da dobijemo funkciju koja je ista kao drugi korak, samo malo „veća“. Nije teško da se vidi da je ta funkcija nešto kao: ispisi(int i). Ona treba da ispiše sve brojeve od i do 10.

Nezgodan deo je u tome što naša funkcija ispisi() nekako lebdi u vazduhu. Poziva se na samu sebe, deluje malo kao baron Minhauzen koji pokušava da se izvuče iz živog blata vukući se za čizme. Da bismo rešili ovaj „konflikt“ moramo da funkciju zakačimo za nešto realno. Kazaćemo da funkcija ispisi(10) ispisuje samo 10 i završava sa radom.

Ovim smo našli sva tri bitna sastojka odozgo: početni uslov (to je poziv ispisi(10)), induktivnu hipotezu (imamo funkciju ispisi(i) koja ispisuje sve brojeve od i do 10) i induktivni korak (ispisi(i) se može izraziti kao ispisivanje broja i i zatim pozivanje funkcije ispisi(i+1)). Kad ove tri stvari objedinimo u program, dobijamo:



E sad nadam se da nećete da mi se mnogo smejete zbog ovog ekstra glupog primera. Dabome da niko pri zdravoj pameti ne bi ovako napisao program koji broji od 1 do 10. Probajte da sagledate obrt: šta se dešava kada probamo da razumemo šta radi prvi primer? Nema mnogo pomoći nego da sagledamo svaku iteraciju ponaosob. Pošto petlja ide od 1 do 10 i telo je prilično jednostavno, neće biti problem da se isprati. Šta međutim kada je gornja granica 10000? Šta ako u telu petlje imamo nešto više od printfa? Ko će to sve da zapamti? (U stvari ispravan način za razumevanje petlje svodi se na to da se „vaskrsne“ rekurzija iz iteracije pa onda opet „podmiti“ indukcija da odradi prljavi posao, o tome je zamalo bilo reči pre neki dan u forumu C/C++.)

S druge strane, rekurzivna varijanta je „otporna“ na sva pomeranja granice. Razumevanje programa se ne menja sa promenom one desetke s početka: stavite 10000 umesto 10 ali ćete i dalje da koristite samo tri sastojka da biste razumeli funkciju.

Dakle, svaki program je bio rekurzija kad je bio mali, bez obzira da li je tu korišćeno „dinamičko programiranje“ ili nekakvo drugo.

Otkud onda dinamičko programiranje? Izraz verovatno dolazi iz vremena pre pravog „kompjuterskog“ programiranja. Slično kao što linearno programiranje nema posebne veze sa programskim jezicima itd, već je valjda neka matematička zezalica. Evo i zašto to mislim: jednom sam tako čitao neku knjigu iz automatike. U jednom delu se govori o nekakvom sistemu koga treba prevesti iz jednog stanja u drugo, uz minimalan utrošak energije (dakle recimo uz najmanju potrošnju struje ili tako nečeg sličnog, valjda je otud jasno što se inženjeri cimaju oko toga). Gle čuda, metoda za to zove se upravo dinamičko programiranje. (a još uvek smo negde na početku 20. veka, dakle nema nikakve šanse da je izmišljator metode imao računare na umu!)

Tamo je objašnjeno otprilike da dinamičko programiranje koristi nekakav „princip optimalnosti“ koji kaže: ako između početnog i krajnjeg stanja postoji najbolja putanja, ako se sistem jednom nađe na najboljoj putanji (bez obzira kako je dotle došao), od te tačke na dalje, mora da se kreće po njoj da bi i ceo put bio najbolji mogući. Štos koji se koristi da se reši stvar će verovatno da vam se učini poznat: krene se od krajnje tačke putanje i nekako, na mišiće, izračuna sam kraj te optimalne putanje. Zatim se izmaknemo još malo unazad i opet na mišiće izračunamo, ali samo deo putanje koji nas od te tačke vodi do malopre izračunate među-tačke. Princip optimalnosti se brine da, kad jednom izađemo na pravi put, sve ostalo klizi kako treba. Malo po malo, računajući parče po parče puta i krećući se unazad sve vreme i koristeći „princip optimalnosti“, na kraju dolazimo do početne tačke. Put kog smo (unazad) ocrtali od cilja do starta je ta najbolja putanja.

E sad, programi koji koriste sličnu ideju su (kao) to dinamičko programiranje. Dakle ima tu rekurzije (pošto je jelte ima u svakom programu), ali ima i još malo više. Sad, da li je ime nesrećno ili ne, ne raspravljam, po knjigama se dobro ukopalo i teško da će skoro neko uspeti da ga odatle pomeri.

I napokon da se vratimo na zadatak posle ove digresije.

Rekoh već da nam za rešenje trebaju samo tri elementa. Mali problem je što na početku pojma nemam kako će ta tri elementa da izgledaju. Zato ću probati da stvar rešim postavljajući (nadam se prava) pitanja u nadi da ću nekako uspeti da napipam koji su pravi početni uslov, induktivna hipoteza i induktivni korak.

Glavni zadatak teroriste (jeste bez veze postavka, šta ćemo...) jeste zapravo da sruši sprat broj 1 na najjeftiniji mogući način.

Da vidimo prvo kako da se sruši sprat i po kojoj ceni, posle ćemo da vidimo šta je sa najjeftinijim rušenjem. Postoje tri načina:
- da se izminira sam sprat, u kom slučaju rušenje košta Ci;
- da se sa gornjih spratova dopremi dovoljno vode;
- da se uradi i jedno i drugo.

Treća varijanta otpada pošto sigurno košta više od primene bilo varijante 1 ili varijante 2 ponaosob.

Što se tiče varijante 2, ona košta najmanje onoliko kolika je ukupna najmanja cena rušenja svih spratova iznad ovog, a koji u zbiru imaju dovoljno vode da sruše ovaj sprat. Ako je ta cena manja od Ci, onda ovaj sprat ne miniramo, već samo čekamo da se voda sruči. Cena miniranja ovog sprata onda postaje 0. Prosto biramo između varijanti 1 i 2 onu koja manje košta. Pošto postoje samo dve mogućnosti za rušenje sprata, ako izaberemo jevtiniju, sigurno smo izabrali minimalnu.

Primetite da se ovde upravo pojavio jedan deo induktivne hipoteze: da bismo izračunali najmanju cenu za miniranje ovog sprata, potrebno nam je da nekako znamo najmanje cene za miniranje gornjih spratova.

Međutim, da bismo to sračunali uveli smo još par pretpostavki koje nam sad štrče, a to je da znamo koliko spratova iznad moramo da imamo srušene (bez obzira na koji način, dovoljno je da znamo da se sprat „minimalno“ srušio, metod 1 ili 2 nebitno je!) kao i da znamo koliki je zbir cena rušenja tih spratova kao i da znamo koliko vode ukupno ima u njima.

Dakle u principu smo rešili minimalno rušenje sprata, sad još treba da sredimo ove novouvedene stvari. I one mogu da se reše rekurzivno, a njihove induktivne hipoteze ćemo da sastavimo sa početnom. To se zove ojačavanje (strengthening) induktivne hipoteze (vidite gorepomenutu knjigu od Manbera). Prosto rečeno: moramo u jednoj petlji da sračunamo više od jedne stvari.

Negde gore ste primetili da nam na par mesta trebaju zbirovi nekakvih veličina od sprata a do sprata b (cena i količina vode će se računati na taj način). Ovaj podproblem se lako reši ako ubacimo induktivnu hipotezu da znamo koliki je zbir recimo svih količina vode od sprata x do sprata N. Neka je to recimo V(x). Količinu vode od sprata a do sprata b ćemo onda lako da sračunamo kao V(b) - V(a), ako je b a. Slično uradimo i sa cenom; obe stvari pomerimo u induktivnu hipotezu.

Inventar:

Induktivna hipoteza:
Za sprat i N znamo:
- zbir minimalnih cena rušenja svih spratova od i+1 do N
- zbir količina vode svih spratova od i+1 do N

Početni uslov:
za sprat N znamo:
- minimalna cena rušenja svih spratova iznad je 0 (jer iznad nema ničega)
- ukupan zbir količina vode svih spratova iznad je 0 (jer iznad nema ničega)

Da bismo sastavili ceo algoritam treba nam još da napravimo induktivni korak. On mora da bude takav da, pošto se izvrši, saznamo:
- zbir minimalnih cena rušenja svih spratova od i do N
- zbir količina vode svih spratova od i do N

Induktivni korak:
Drugi deo lako računamo sabirajući zbir voda sa svih spratova od i+1 do N sa Wi. To je O(1).

Prvi deo je malo nezgodan, jer treba da lociramo najbliži sprat j iznad, takav da kada se saberu količine vode na spratovima između i+1 i j, to sve bude veće od limita Li na ovom spratu. Pošto je zbir količina vode od i+1 ka N monotono rastući, ovaj sprat može da se pronađe binarnom pretragom. Pošto zbir količina vode može direktno da se pronađe kao razlika zbirova količine voda, onda nam za to treba samo O(1), dobili smo to vrlo jeftino. Ostaje samo složenost binarne pretrage, O(log(N-i)) = O(logN).

Kada smo našli taj sprat iznad, uporedimo cenu rušenja sprata i sa cenom „urušavanja“ sprata pomoću vode. Na osnovu toga izaberemo varijantu rušenja 1 ili 2, zavisno koja je jeftinija.

Time smo završili induktivni korak i opisali sva tri bitna elementa programa. Nije zgoreg još jedna provera da sve pasuje (nisam proveravao, slobodno me izrešetajte ako sam nešto omanuo!).

Dakle, ako sa izvršavanjem algoritma krenemo od sprata N ka spratu 1, kada stignemo do 1 i završimo, znaćemo:
- zbir minimalnih cena rušenja svih spratova od i do N
- zbir količina vode svih spratova od i do N

Za minimalnu cenu nam treba samo da oduzmemo min. ukupne cene rušenja od 2 do N od min ukupne cene rušenja od 1 do N.

Na kraju, procena složenosti:
- induktivni korak se izvšava N puta, jednom za svaki od N spratova.
- složenost induktivnog koraka zavisi od i, ali nije veća od složenosti koraka za sprat 1, gde je otprilike O(logN): većina operacija je O(1) pošto smo koristili induktivnu hipotezu da svedemo sva računanja na minimum; jedini korak koji „iskače“ je ona binarna pretraga koja je O(logN). Kada saberemo tih par O-ova dobijamo samo O(logN).
- dakle, ukupna složenost je manja od N O(logN), što je ukupno O(NlogN).

Nadam se da nisam baš mnogo lupio...

f

A zasto?


Sta smo tacno time dobili?


ratatata!
Salim se, ali samo nije zgoreg da jos malo pojasnis algoritam.


Ne razumem.

Kod rekurzivnog rešenja moramo da imamo funkciju koja se induktivnim korakom svede na istu tu funkciju, samo sa malo drugačijim argumentom.

(1) U iteraciju sa i-tim spratom ulazimo znajući:
- zbir minimalnih cena rušenja svih spratova od i+1 do N
- zbir količina vode svih spratova od i+1 do N

(2)U iteraciju sa i-1-vim spratom moramo da uđemo znajući:
- zbir minimalnih cena rušenja svih spratova od i do N
- zbir količina vode svih spratova od i do N
da bi nam stalno važila induktivna hipoteza, to je uslov da indukcija radi. Primeti: (1) i (2) su ista funkcija, samo je u (1) argument i, a u (2) argument i-1.

Znači da telu iteracije za i-ti isprat moramo od (1) da nekako napravimo (2) da bismo održali važnost induktivne hipoteze.

Time smo sračunali koliko košta metod  rušenja br. 2. (urušavanje, iliti rušenje gornjih spratova na neki način i čekanje da voda uradi ostalo).  Zatim to uporedimo sa cenom miniranja sprata, metod br. 1. Zavisno od toga koja cena je manja, za sprat i trošimo ili Ci (ako mora da se minira) ili 0, ako može da se uruši.

Pa, igrom slučaja je u zadatku lakše da se pamti zbir koštanja svih spratova od i do N umesto samo koštanja svih spratova. Zato cenu sprata 1 dobijamo kao (zbir od 1 do N) - (zbir od 2 do N).

f

Hm, zar nije malo sumnjivo sto stoji 2x109? Pre bih rekao da je u pitanju , sto ce reci da Srkijevo resenje ipak ima kvadratnu slozenost (kao i ono koje sam ja predlozio).

Filipe, mislim da se princip optimalnosti u ovom zadatku ne moze primeniti. Metoda koju si opisao je i meni pala na pamet, ali sam nekako sebe ubedio da tako ne ide. Ispravi me ako gresim, ali evo jednog primera konfiguracije zgrade koja bi mogla da je zbuni:

1. sprat: vode ima 10 litara, kapacitet bazena 20 litara, cena rusenja 30.
2. sprat: vode ima 5 litara, kapacitet bazena 30 litara, cena rusenja 15.
3. sprat: vode ima 10 litara, kapacitet bazena 20 litara, cena rusenja 10.
4. sprat: vode ima 20 litara, kapacitet bazena 30 litara, cena rusenja 20.

E sad, minimalne cene rusenja pojedinih spratova:
4. - 20
3. - 10
2. - 15
1. - 20

Kao sto vidis, problem nam pravi onaj 2. sprat, posto ima preveliki kapacitet. Kad bi gledali po kolicini vode, za rusenje prvog sprata cemo (binarnom pretragom) naci da je dovoljno da dignemo samo treci sprat u vazduh. Medjutim, ta voda ce se zaustaviti na drugom spratu, pa zato moramo da rusimo samo cetvrti.

Voleo bih da vidim ono resenje sa primenom "kumulativnih tabela" (ne mogu da pogodim sta se krije iza tog pojma) koje je Danica pomenula.

Da, pogrešio sam. :( Minimalna cena stoji „iznad“ gornje granice za spratove koju sam postavio pa sam je promašio. Učinilo mi se da će minimalna cena da sama „siđe“ ali izgleda da nije tako...

f

To je ok ali dalje mi nije jasno jer ne vidim kako iz date funkcije mozemo da nadjemo resenje zadatka.


Cek, sta ti je cena jednog sprata? Ako je cena rusenja spratova od 1 do N i od 2 do N ista onda bi ti ispalo da je cena sprata 1 u stvari nula. Ili te ipak nisam dobro razumeo?

Hey!

Ja sam tek sada saznao za ovu raspravu... Ubacujete se previse!
Necu da komentarisem text zadatka, ali niko nije imao nista protiv njega...
Test primeri... Ako hocete da vidite debilne test primere - www.acm.ro
Meni jos uvek nije jasno zasto je prolazilo 90 poena na takmicenju, ali verovatno je neka greska u kodu ili algoritmu.
Inace, zadatak je vrlo simpatican! A i ne bi ste se vi ovoliko jebavali da vas ne interesuje!
Bodovanje je bilo sledece:

- za proveru rusenja svakog sprata i kretanjem na dole se dobija 30 poena
- za pametniju proveru, ali i dalje kvadratni algoritam se dobija 50 poena (sa koriscenjem niza u kojem smestamo spratove koje smo rusili za prethodni sprat)
- za resenje koriscenjem hipa i naravno dinamicki odozdo nagore se dobija svih 100 poena

Ako vas bas zanima, mogu malo i da pojasnim resenje zadatka...
Pozdrav!

Ako je tako onda moje resenje ne vajla jer bi mogao da se napravi slucaj da moje resenje predugo radi. Onda je najbolje dinamicki popunjavati matricu cena[i,j] gde je cena[i,j] najmanja cena rusenja spratova izmedju "i" i "j" (i<=j uz dozvoljeno rusenje spratova iznad j ako je ukupna cena urusavanja manja). To je malo izmenjeno Filipovo resenje jer gornja granica nije konstantna. U tom slucaju je slozenost resenja O(n*n). Tada se ide rekurzijom odozdole ka gore. Napisacu kasnije pseudokod.

Inace, ja sam autor zadatka (texta i resenja).