Pagini: 1 [2]   În jos
  Imprimă  
Ajutor Subiect: 028 Secventa 2  (Citit de 12796 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
u-92
Vizitator
« Răspunde #25 : Ianuarie 21, 2006, 14:42:10 »

problema se poate rezolva corect cu programare dinamica
Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #26 : Februarie 19, 2006, 00:37:53 »

Si eu am luat 100 de puncte, dar pentru

Cod:

4 3
-1 -2 -3 -4 -5 -6


imi afiseaza 4 6 -15...  Sad  Ce complexitate ai obtinut cu programare dinamica u-92 ?
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
u-92
Vizitator
« Răspunde #27 : Februarie 19, 2006, 13:23:50 »

complexitate liniara O(n)
Memorat
razyelx
Client obisnuit
**

Karma: 0
Deconectat Deconectat

Mesaje: 82



Vezi Profilul
« Răspunde #28 : Aprilie 08, 2007, 10:37:13 »

eu am facut-o de complexitate o(n*n) mi se pare... oricum normal ca la testul lui Mircea Pasoi nu imi da cum trebuie. Presupun pt ca folosesc borland si nu imi vede long long in rest imi merg toate testele.. totusi la evaluare nu imi intra pe primul test si utlimele 3. nusth dc la primul am raspuns gresit si la ultimele 3 cum e si normal pt complexitate iau. Algoritmul meu suna cam asa:
iau merg cu i de la 1 la n-1(normal ar fi si n, deoarece ar fi posibila varianta ca ultimul sa fiu suma maxima) apoi cu un j de la i+1 la n. imi iau o suma cache care initial ia val -26000 si se schimba la fiecare suma maxima gasita, la fel si capetele sirului care a=i si daca s>cache b=j. Daca vreau sa o fac mai eficient imi pica si testul 6 la limita de timp. o idee pls.. ahh sa nu uit daca folosesc long long chiar ca nu mai intra in timp  Yahoo!
« Ultima modificare: Aprilie 08, 2007, 10:40:12 de către Brestin Sebastian » Memorat
gabitzish1
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« Răspunde #29 : Aprilie 08, 2007, 12:04:56 »

razyelx .. mai uita si tu de problemele astea.. macar de sarbatori Wink.. nici mie nu imi lua primul test pana mi'am dat seama ca nu rezolvam bine cazul in care secventa cautata era chiar sirul dat... (poate la tine e la fel.. e doar o sugestie.. ) oricum.. ai putea sa te stresezi maine cu ea.. azi ocupa'te de sarbatori Tongue ...

Paste Fericit tuturor !!!
Hristos a inviat!!

Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #30 : Aprilie 08, 2007, 12:08:08 »

De sarbatori nimic nu e mai frumos decat sa te delectezi cu putina info!!! Whistle

Paste fericit tuturor! Rolling Eyes
Memorat
razyelx
Client obisnuit
**

Karma: 0
Deconectat Deconectat

Mesaje: 82



Vezi Profilul
« Răspunde #31 : Aprilie 08, 2007, 22:09:47 »

Adevarat a inviat! ce sa fac eu eram ca ma las de info... si ca ma apuc de altele, dar ce sa fac daca te plictisesti de mai apuci si de niste pb apoi mai stai cu familia si stuff... chiar amu am de gand sa manc o bucata de tort... anyway ms de sfat o sa il incerc.. dar maine  Applause
Memorat
dexter_dex
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #32 : Martie 05, 2008, 19:48:30 »

nu poate Gigel sa ne trimita sursa pe care o facuse el si noi doar sa o modificam ? Very Happy Very Happy Very Happy Whistle
Memorat
gabitzish1
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« Răspunde #33 : Martie 05, 2008, 20:10:25 »

Trimite'i un mail si intreaba'l.. poate'ti raspunde  Thumb up
Memorat
runnaway90
Strain
*

Karma: -7
Deconectat Deconectat

Mesaje: 25



Vezi Profilul
« Răspunde #34 : Aprilie 20, 2008, 18:24:17 »

kre a mai rezolvat-o si a zis k nu-i dadea primu test Very Happy ce a gresit:P...?Very Happy;Wink Evil or Very Mad
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #35 : Aprilie 24, 2008, 22:58:35 »

Aveti un hint pentru rezolvarea cu complexitate liniara pls.  Very Happy
Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #36 : Aprilie 24, 2008, 23:00:54 »

Scrie mai sus: programare dinamica. Mai precis, secventa de suma maxima.
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #37 : Aprilie 24, 2008, 23:02:34 »

Pai da... dar aici secventa de suma maxima trebuie sa fie de cel putin k, si nu prea stiu cum sa le leg, si ce incerc, tot in n^2 iese Brick wall
« Ultima modificare: Aprilie 24, 2008, 23:27:26 de către Andrei Misarca » Memorat
amadaeus
Client obisnuit
**

Karma: 28
Deconectat Deconectat

Mesaje: 93



Vezi Profilul
« Răspunde #38 : Aprilie 25, 2008, 09:59:13 »

Ca sa fie de lungime cel putin k e destul sa fixezi ultimele k-1 elemente si sa te uiti in dinamica in urma cu k pozitii Wink
Memorat

"one of these days I'm going to cut you into little pieces..."
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #39 : Aprilie 25, 2008, 11:47:16 »

Problema subsecventei de suma maxima se rezolva astfel:

Notand cu V sirul initial, vom construi un sir S al sumelor partiale. S[ i ] = V[1] + V[2]+ ... + V[ i ]. Suma elementelor dintr-o subsecventa A...B este egala cu S[ B ] - S[A-1]. Dorim sa determinam pentru fiecare pozitie B care este subsecventa de suma maxima care se termina pe pozitia B. O solutie in O(N^2) ar fi sa parcurgem toate elementele A intre 1 si B si din S[ B ] sa scadem S[A-1] si sa retinem maximul. Insa observam ca ne intereseaza la fiecare pas doar minimul dintre valorile S[A-1] cu A intre 1 si B. Astfel e destul de usor sa determinam subsecventa de suma maxima in O(N).

Pentru subscventa de lungime cel putin K te las pe tine sa te gandesti, insa nu e foarte greu sa modifici algoritmul prezentat de mine mai sus  Thumb up
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #40 : Aprilie 25, 2008, 12:06:10 »

Citat
Insa observam ca ne intereseaza la fiecare pas doar minimul dintre valorile S[A-1] cu A intre 1 si B
Dar la fiecare pas ar cam trebui sa aflu acest minim, deci complexitatea ar fi cam O(n^2)  Confused
Pentru aflarea secventei de suma maxima in O(n) imi faceam un sir S, cu proprietatea ca S[ i ] = S[ i-1] + V[ i ], daca S[ i-1 ] > 0 sau V[ i ], daca
S[ i-1 ] < 0, iar maximu din acest sir e suma  maxima, pozitiile de pe care incepe si pe care se termina fiind usor de determinat. Dar la problema asta nu ma prea ajuta daca fac asa  Smile
Memorat
fireatmyself
Nu mai tace
*****

Karma: 36
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #41 : Aprilie 25, 2008, 12:10:29 »

tu vrei sa determini subsecventa de suma maxima care se termina in B, deci vrei sa scazi din S[ B ] un S[A-1] cat mai mic, exact cum spunea Wef, alegand minimul dintre S[1], S[2], ..., S[B-1]. cand treci la B+1 ai deja calculat minimul de la 1 la B-1, dar tie iti trebuie minimul de la din intervalul [1,B]. asta se face in O(1). gandeste-te un pic Very Happy

ideea de aici te ajuta foarte mult la problema aceasta. tu mai sus determini o secventa de cel putin un element, dar pentru k trebuie sa gasesti pentru un B fixat un S[A] minim care sa-ti asigure faptul ca in secventa sunt cel putin k Tongue

pune pe hartie exemplul asta si vezi cum merg ambii algoritmi:
n = 9 si k = 3
-2 -1 3 2 -4 2 2 -7 3 2

raspunsul ar trebui sa fie 5: 3 2 -4 2 2
iar pentru subsecventa de suma maxima (fara restrictii) raspunsul ar trebui sa fie 6: 3 3
« Ultima modificare: Aprilie 25, 2008, 12:21:10 de către Bogdan A. Stoica » Memorat

Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #42 : Aprilie 25, 2008, 12:34:56 »

Dap... stiu, da' am tot incercat o 'ajustare' a algoritmului de mai sus si pentru K elemente... dar nu mi-a prea intrat in mai putin de O(n^2)... multzam fain pentru explicatzii, am prins faza(am reusit sa scot suta asa).  Yahoo!
« Ultima modificare: Aprilie 25, 2008, 12:46:48 de către Andrei Misarca » Memorat
Pagini: 1 [2]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines