u-92
Vizitator
|
|
« Răspunde #25 : Ianuarie 21, 2006, 14:42:10 » |
|
problema se poate rezolva corect cu programare dinamica
|
|
|
Memorat
|
|
|
|
•Marius
|
|
« Răspunde #26 : Februarie 19, 2006, 00:37:53 » |
|
Si eu am luat 100 de puncte, dar pentru imi afiseaza 4 6 -15... 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
Mesaje: 82
|
|
« 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
|
|
« Ultima modificare: Aprilie 08, 2007, 10:40:12 de către Brestin Sebastian »
|
Memorat
|
|
|
|
•gabitzish1
|
|
« Răspunde #29 : Aprilie 08, 2007, 12:04:56 » |
|
razyelx .. mai uita si tu de problemele astea.. macar de sarbatori .. 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 ... Paste Fericit tuturor !!! Hristos a inviat!!
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #30 : Aprilie 08, 2007, 12:08:08 » |
|
De sarbatori nimic nu e mai frumos decat sa te delectezi cu putina info!!! Paste fericit tuturor!
|
|
|
Memorat
|
|
|
|
•razyelx
Client obisnuit
Karma: 0
Deconectat
Mesaje: 82
|
|
« 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
|
|
|
Memorat
|
|
|
|
•dexter_dex
Strain
Karma: 0
Deconectat
Mesaje: 1
|
|
« Răspunde #32 : Martie 05, 2008, 19:48:30 » |
|
|
|
|
Memorat
|
|
|
|
•gabitzish1
|
|
« Răspunde #33 : Martie 05, 2008, 20:10:25 » |
|
Trimite'i un mail si intreaba'l.. poate'ti raspunde
|
|
|
Memorat
|
|
|
|
•runnaway90
Strain
Karma: -7
Deconectat
Mesaje: 25
|
|
« Răspunde #34 : Aprilie 20, 2008, 18:24:17 » |
|
kre a mai rezolvat-o si a zis k nu-i dadea primu test ce a gresit:P...? ;
|
|
|
Memorat
|
|
|
|
•Mishu91
|
|
« Răspunde #35 : Aprilie 24, 2008, 22:58:35 » |
|
Aveti un hint pentru rezolvarea cu complexitate liniara pls.
|
|
|
Memorat
|
|
|
|
•Marius
|
|
« 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
|
|
« 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
|
|
« Ultima modificare: Aprilie 24, 2008, 23:27:26 de către Andrei Misarca »
|
Memorat
|
|
|
|
•amadaeus
Client obisnuit
Karma: 28
Deconectat
Mesaje: 93
|
|
« 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
|
|
|
Memorat
|
"one of these days I'm going to cut you into little pieces..."
|
|
|
•wefgef
|
|
« 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
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•Mishu91
|
|
« Răspunde #40 : Aprilie 25, 2008, 12:06:10 » |
|
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) 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
|
|
|
Memorat
|
|
|
|
•fireatmyself
|
|
« 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 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 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
|
|
« 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).
|
|
« Ultima modificare: Aprilie 25, 2008, 12:46:48 de către Andrei Misarca »
|
Memorat
|
|
|
|
|