Zamolio bih nekog da me malo usmeri kako da radim ovaj zadatak.
z. premestanje
Takodje lol nesto sta god da smislim ne mogu da dokazem da ce za svaki slucaj biti optimalno. Ono sto sam nekako skontao je da verovatno treba krenuti sa kraja i gledati kako dovesti na kraj one koji su na krajevima u pocetnom redosletu premestanjima iz zeljenog. ???
razmishljaj ovako :
nebitno je kojim redosledom uzimas decu.
Znaci, mozes sve (koji ce nam trebati) uzeti odjednom
i onda gledati kako taj skup da stavljas na pocetak/kraj tako da dobijes
zeljen raspored..
U sustini, zadatak se svodi na trazenje najduzeg rastuceg podniza.
Ostale elemente u trebas izvaditi i postavljati na odgovarajucu stranu.
nebitno je kojim redosledom uzimas decu.
Znaci, mozes sve (koji ce nam trebati) uzeti odjednom
i onda gledati kako taj skup da stavljas na pocetak/kraj tako da dobijes
zeljen raspored..
U sustini, zadatak se svodi na trazenje najduzeg rastuceg podniza.
Ostale elemente u trebas izvaditi i postavljati na odgovarajucu stranu.
Da.
Sortiras po prvom i onda nadjes najdulji rastuci podniz u O(N log N) i to backtraceas.
Sortiras po prvom i onda nadjes najdulji rastuci podniz u O(N log N) i to backtraceas.
Ispravak:
Taj najdulji rastuci podniz treba biti takav da je svaki sledeci za jedan veci, tj. a[i] = a[i-1] + 1.
Pa zato taj zadatak mozes rjesit u O(N) ako jos i "sortiras" tako sto elemente u drugom nizu zamijenis sa odgovarajucim elemntima.
Taj najdulji rastuci podniz treba biti takav da je svaki sledeci za jedan veci, tj. a[i] = a[i-1] + 1.
Pa zato taj zadatak mozes rjesit u O(N) ako jos i "sortiras" tako sto elemente u drugom nizu zamijenis sa odgovarajucim elemntima.
Ja samo znam kako to da oradim u O(n^2). Moze malo objasnenje kako da to uradim u O(n *logn)? A i ovo, kako se radi za linearno vreme?
I jos nesto, nekad moze da ima 3 resenja, u dati primer l2 l1 l3 takodje valja. Koje resenje ispisen tada?
I jos nesto, nekad moze da ima 3 resenja, u dati primer l2 l1 l3 takodje valja. Koje resenje ispisen tada?
Ako se ne varam, ovde ti treba specijalan rastuci podniz, tacnije ako imas niz
1 3 5 7 2 4 6
najduzi koji treba za zad je recimo (1, 2) ili (5, 6), a ne recimo (1, 3, 5, 7). Probaj pod ovakvim uslovima da razmisljas o zadatku...
1 3 5 7 2 4 6
najduzi koji treba za zad je recimo (1, 2) ili (5, 6), a ne recimo (1, 3, 5, 7). Probaj pod ovakvim uslovima da razmisljas o zadatku...
Moze da tvoju ideju demonstrises za primer iz zadatka (sa dve nize). Jer ja mislim da kazes da clanovi u podnizu moraju biti susedne u originalnu nizu( tako to se "preveduje" za slucaju u zadatke) ali mislim da to nije tacno.
Onda zadatak sadrzi lose test primere na kojima mozes tako da uradis i proci ce ti :)
Ovako, prvo indexiras kako treba sve
3 -> 1; 1 -> 2; 2 -> 3; 5 -> 4; 4 -> 5
sto znaci da ti je pocetni niz nesto kao
5 1 4 3 2 -> 4 2 5 1 3
U ovom slucaju, najduzi ti je (4, 5) ili (2, 3), koji god da uzmes ok je
pa ce resenje za (4, 5) biti ovako
3 na pocetak
2 na pocetak
1 na pocetak
sto kada se prebacis na ono indexiranje koje sam naveo na pocetku ispada
2, 1, 3 tim redom na pocetak
i kako sto vidis tacno algoritamski se dobija resenje koje je dato u zadatku. Nadam se da ti ovo pomaze...
Ovako, prvo indexiras kako treba sve
3 -> 1; 1 -> 2; 2 -> 3; 5 -> 4; 4 -> 5
sto znaci da ti je pocetni niz nesto kao
5 1 4 3 2 -> 4 2 5 1 3
U ovom slucaju, najduzi ti je (4, 5) ili (2, 3), koji god da uzmes ok je
pa ce resenje za (4, 5) biti ovako
3 na pocetak
2 na pocetak
1 na pocetak
sto kada se prebacis na ono indexiranje koje sam naveo na pocetku ispada
2, 1, 3 tim redom na pocetak
i kako sto vidis tacno algoritamski se dobija resenje koje je dato u zadatku. Nadam se da ti ovo pomaze...