bTreba mi pomoc oko bojenja. Neka pogleda ko hoce sto sam poslao, ima dosta komentara, a ko nije to radio, a misli da može da mi pomogne, neka mi pošalje mejl na moj mejl boba5555@gmail.com ili neka posalje svoj mejl, pa cu mu poslati kod. Hvala unapred.
Prolazi mi sa 7 test primera, a za 3 puca na vremenu, ali nije mi jasno zasto.
Hvala.
Uradio sam ovaj zadatak, ali ako nekog STVARNO zanima kako se radi, mogu mu objasniti.
Mene me interesira. Ono resenje od topcoder nisam bas najdobro razbrao...
Ja cu ti opisati kako sam ja shvatio i kako sam radio, prvo mi je trebalo da shvatim ono sa topcoder-a i to nije tesko shvatiti. Evo kako oni pisu
Ako bojis od i do j sa nekom bojom l.
Imas neki akumulator (pisacu a) na koga gomilas vrednosti za minimum i on je na pocetku nula
D[i, j, b] je oznaka za optimalno bojenje od i do j ako je taj deo obojen bojom b
ako je Boja[i]<> l onda
a postaje 1
k šeta od i do j
ako je Boja[k] = Boja[i] onda
a postaje a + D[i + 1, k - 1, Boja[i]] + D[k + 1, j, l]
update-uj D[i, j, l] ako je manji od prethodne vrednosti i zapamti do kog polja si bojio jer će trebati za rekonstrukciju.
Evo i logčckog objašnjenja ovoga.
Ako bojiš jedan deo trake, ti treba da obojis i prvo polje i bojenje SAMO tog polja ne utiče na bojenje ostalih, jer je ono ispred svih ostalih, pa hajde onda odmah da ga obojimo (tako piše i na topcoderu).
Jedna veoma bitna činjenica je da nema potrebe da proveravamo da li će bojenje polja koje nema boju kao i prvo polje išta promeniti na ''bolje'' jer to polje svakako treba da obojimo drugom bojom, ali ako neko polje ima istu boju kao što ima i prvo polje, onda se nama MOŽDA isplati da od prvog do tog polja obojimo sa bojom prvog polja, jer ćemo na taj način smanjiti bojenje jednog polja, samo ne znamo da li tako bojimo optimalno, pa zato probamo za sva polja. Znači nama bojenje polja koje je različite boje od prvog polja ne može smanjiti broj potrebnih bojenja.
Ako obojimo od i do k jednom bojom, znači da smo polja i i k ''rešili'' pa sad na isti način optimalno bojimo od i + 1 do k - 1, a ostatak od k + 1 do j nastavljamo dalje.
Da li je ovo za sad jasno? Ovo nije ideja koja prolazi na vremenu, tačnije jeste, ali treba nešto pametno da se smisli i ova puno optimizuje. Samo po mom mišljenju trebalo je ovo prvo shvatiti pa onda optimizovati.
Ako nešto nije jasno, napiši, a ako jeste onda opet napiši da nastavim dalje.
Inače nisam ni ja otkrivao toplu vodu, već sam malo pokupio ideju sa zvaničnog rešenja.
Možeš ovo uraditi i memoizacijom i iterativno, nije bitno. Bojenje posle toga ide trivijalno rekurzijom kako god radio dinamički deo.
Ako hoćeš mogu ti poslati kod za ovaj deo, samo mi pošalji mejl na moj mejl i to je to.
P.S. Tijana javi se i ti da li ti je jasno.
Hvala ti, razgledacu tvoje objasnjenje kad ke imam vise vreme
U redu, ali to nije sve. Ovo ti neće proći zbog vremena, ali bitno mi je da prvo ovo shvatiš pa onda da ti napišem kako dalje. Napisao sam to negde u tekstu. Kad budeš hteo, postuj pa ću nastaviti dalje.
Pozdrav,
