infoarena

Aici puteţi discuta despre problema Secventa 2 (http://infoarena.ro/problema/secv2).

Mircea te rog mult de tot poti sa postezi si tu macar primul test, ma chinui la problema asta si de-mi sar capacele, te rog frumos.

Input:


Output:

Multumesc frumos, acum stiu ce-am gresit... :)

nu reusesc nici cum sa gasesc un algoritm care sa se incadreze in 0.18s!!! Some help... please ... anyone :(

eu am gasit o rezolvare in O(n).;
care a mers pe teste...
chestia e ca tu parcugi vectorul ca pentru o suma maximala, cu conditia din enunt

Chiar daca o scoti in O(n) e posibil sa-ti iasa din timp. Poti folosi "vraja marii la malu' marii" adica sa-ti pui un bufer la fisierul de intrare. :mrgreen:
Cam 1 MB iti este de ajuns sa elimine neplacerile cauzate de o citire greoaie. Functia e "setvbuf", si iti poate folosi la multe probleme in care timpul e critic.

multumesc frumos pentru sfat

Input:
Code:
13 13
-24468 -3302 -23557 -1899 -4410 -650 -6467 -9733 -16334 -15731 -7225 -2730 -11983
 


Output:
Code:

1 13 -128489
 
interesant ca mie pe testu asta imi da (acasa) 0 0 0 si totusi iau o suta de puncte... nu-s bine alese testele. stiu si pe altii carora nu le-ar merge testele pt care suma maximala ar da negativa...... dati un test cu n>k si cu toate numerele din vector negative si veti avea surprize la reevaluare(daca conteaza pentru cineva)

Tu ai intrebat de limita de 0.18s care e la problema "Secventa" nu la "Secventa 2" unde ai postat... testul de mai sus este printre testele de la problema Secventa 2 (cel putin daca nu le-a schimbat nimeni :)).. deci, tu pentru ce postezi? Daca e vorba de problema "Secventa", cum banuiesc, voi muta toate post-urile unde trebuie.. si incearca sa nu mai postezi aiurea  [-X

postul cu limita l-am pus unde nu trebe. =; ... sorry dar ce de-al 2-lea e bine pus! Chiar am trimis un algoritm incomplet care totusi a luat 100p

Poate ca daca ai pune la cea mai mica suma pe care o consideri -maxlongint nu ti-ar mai da  0 0  0, asa ca alta data sa-ti construiesti un algoritmmai bine facut, [ sau sa te uiti mai bine pe cod], inainte sa postezi pe forum...  :evil:  :evil:  :evil:

dany3dx,
foarte bine ca ai gasit un caz particular pt problema. Dar asta nu-nseamna ca nu-s bine alese testele. Poate vor tine cont de postu tau si vor modifica un test, adaugand cazul asta particular. Poate ca nu. Dar in mod sigur nu se va reevalua problema pt toti cei care au trimis solutii la ea [cel putin nu cred :)].  

cat despre algoritmi "incompleti" care iau 100 pcte. Nu-i asa grav!

nu incape in numarul de teste care le numesti particulare... dar ai oarecum dreptate.. nu-i asa grav

Zici ca ai trimis la Secventa 2 sursa care a luat 100p si da 0 0 0 pe testul ala cu 13 13 ? Dubios, fiindca testul ala stiu sigur ca l-am folosit cel putin in concurs, nu tin minte sa fi avut loc vreo modificare a testelor, o sa verific... :-k

nu este nici o problema cu testul , decat ca este format numai din valori negative iar voi probabil ati initializat maximul cu 0.incercati sa puneti maximul=-1250000000 la inceput.

Am incercat sa fac si eu problema si iau 70p. si nu stiu unde am gresit. Maximul l-am pus de -1250000001. Vectorul il parcurg in suma maximala,cu conditia din enunt:

v[k-1] are suma primelor k-1 elemente.
Care ii problema?

nustiu ce sa zic de codul ala :-k
mai bine ai spune care e ideea ta de rezolvare

Suma maxima ia valoarea primelor k-1(k-ul este lungimea minima a secventei) elemente al sirului de numere si o pun in v[k-1]. Acum merg de la k la n. Eu acum consider asa  dak suma v[i-1] este mai mica decat v[i-1]-a[poz] adik daca iau din suma elementul din stanga secventei(poz este init cu 0) si voi avea o suma mai mare atunci ma voi scapa de aceste element si voi aduga la v suma v-a[poz]+a si incrementez poz.Acum dak v este mai mare decat suma maxima atunci max=v si actualizez pozitia 1 si pozitia 2 a secventei.
Deci ce zici de idee?

nustiu ce sa zic.. probabil nu e corect daca nu prinzi toate testele.. eu am facut altfel

Probabil ca da,nu mi-ai putea da un indiciu mic?

Cred k este pe ideea corecta...Dar mi se pare ca te-ai complicat prea mult...Eu fac suma elementelor de la 1->k, 1->k+1 ,..., 1->n.Memorezi suma maxima si pe ce pozitie a fost, si iti da capatul din dreapta. Dupaceia faci acelas procedeu ca cel de sus numai ca faci sumele de la d->d-k, d->d-k-1, ... d->1.
Si ai gasit cele 2 capete.
EX:
v-sirul de elemnte
8 3
-3  1 -1  3 1 -2  8 -5

ai suma maxima pe pozitiile 2 si 4
Deci ai solutiile
2 7 10
4 7 10
Sper k ai inteles :)

Thanks! Acum iau 100p pe problema. Totusi is curios la ce teste a picat solutia mea  #-o .

dobre, ptr urmatoarea intrare:



cat iti da?

rasp corect e 5 6 9. mie mi se pare ca prog tau afiseaza 1 3 6

cred ca ar fi bine sa se faca alte teste si sa se recorecteze problema.

Sa stii  ca ai dreptate ... Dar nu pot sa inteleg cum de am luat 100p pe ea
 :eyebrow: si totusi care ar fi solutia corecta ... Bine ca ai sesizat altfel in concursuri de mai intalneam probleme de genu tot asa le abordam.

problema se poate rezolva corect cu programare dinamica

Si eu am luat 100 de puncte, dar pentru



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

complexitate liniara O(n)

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:

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 :P ...

Paste Fericit tuturor !!!
Hristos a inviat!!

De sarbatori nimic nu e mai frumos decat sa te delectezi cu putina info!!! :-'

Paste fericit tuturor! :roll:

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  =D>

nu poate Gigel sa ne trimita sursa pe care o facuse el si noi doar sa o modificam ? :D :D :D :-'

Trimite'i un mail si intreaba'l.. poate'ti raspunde  :thumbup:

kre a mai rezolvat-o si a zis k nu-i dadea primu test :D ce a gresit:P...?:D;;) :evil:

Aveti un hint pentru rezolvarea cu complexitate liniara pls.  :D

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

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 ](*,)

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 ;)

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  :thumbup:

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  :)

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 :D

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 :P

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

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: