318 Buline

[•DITzoneC]

Aici puteţi discuta despre problema Buline.

[•k_ounu_eddy]

Problema asta e asemanatoare cu secventa.Deosebirea e ca nu se da k.

[•bogdan2412]

Nu e nevoie de deque-uri aici, spre deosebire de secventa.

[•mocke]

Ai putea sa faci si deque intradevar (eu asa am facut  ). Dublezi sirul, defapt mai adaugi primele N - 1 elemente la coada, faci sume partiale si astfel poti calcula secventa de suma maxima de lungime <= N (care reprezinta si raspunsul problemei). 

[•k_ounu_eddy]

Cum adica sume partiale?

[•Tabara]

Cum adica sume partiale?

Adica daca ai un sir de valori.

Cod:

sum[i] = sum[i-1] + a[i].

Se calculeaza asa

Cod:

sum[0] = 0;
for ( i = 1 i <= n; ++i )
      sum[i] = sum[i-1] + a[i];// a retine valorile sirului

( suma valorilor pana la pozitia i inclusiv ).Sumele partiale te ajuta sa afli care e spre exemplu suma intre doua valori [i,j] astfel

Cod:

( suma[i] - suma[j] ).

[•k_ounu_eddy]

Si apoi dupa ce calculezi toate sumele,retii maximul si il afisezi nu?
Dar mai am o intrebare:conteaza si elemntul de start nu?Adica ar trebui sa incepi cu cel pozitiv,nu?

[•Tabara]

Si apoi dupa ce calculezi toate sumele,retii maximul si il afisezi nu?

Si maximul ala ce ar trebui sa reprezinte ?

Dar mai am o intrebare:conteaza si elemntul de start nu?Adica ar trebui sa incepi cu cel pozitiv,nu?

Te referi la secventa de suma maxima sau la sumele partiale ?
 

[•k_ounu_eddy]

Pai maximul sumei(nu asta trebuia sa afisezi)?

Te referi la secventa de suma maxima sau la sumele partiale ?

Ma refer la suma maxima(la problema buline).Nu conteaza elementul de start.Spre exemplu daca ai numerele:
-1 2 3 4 5.
s[1]=-1,s[2]=1,s[3]=4,s[4]=8,s[5]=13.In cazul asta maximul este 13.Dar daca incepeam cu elementul 2,aveam:
s[1]=2,s[2]=5,s[3]=9,s[4]=14.Acum suma este 14,mai mare ca 13(din ex anterior).

[•Tabara]

Pai maximul sumei(nu asta trebuia sa afisezi)?

Te referi la secventa de suma maxima sau la sumele partiale ?

Ma refer la suma maxima(la problema buline).Nu conteaza elementul de start.Spre exemplu daca ai numerele:
-1 2 3 4 5.
s[1]=-1,s[2]=1,s[3]=4,s[4]=8,s[5]=13.In cazul asta maximul este 13.Dar daca incepeam cu elementul 2,aveam:
s[1]=2,s[2]=5,s[3]=9,s[4]=14.Acum suma este 14,mai mare ca 13(din ex anterior).

Poi tu zici bine, insa nu cred ca merge faza cu sumele partial pur si simplu calculate si afisat maximul.Trebuie sa calculezi secventa de suma maxima, care poate incepe oriunde in sir.
Dar ce spui tu e corect, numai ca nu asta e solutia problemei.

Si eu la "buline" lucrez acuma dar nu imi dau seama ce naiba gresesc. Imi da  "Suma Gresita" si am facut ca in solutie.  Still working on that! 

[•k_ounu_eddy]

Pai tu cum ai facut Barca Crisitian Mihai?

[•mocke]

Pei dupa ce am pus in coada primele N - 1 elem si am facut sume partiale...in deque o sa-mi bag suma partiala minima la un pas astfel incat secventa sa nu-mi depaseasca N elemente...si la fiecare pas i aleg si smax = MAX(S[ i ] - St[s1], smax) (unde St este deque-ul meu iar s1 primul pivot, pozitia sumei partiale minime, iar S este vectorul de sume partiale). In ce priveste constructia deque-ului ar trebui sa incerci pe o foaie sa vezi cum sta treaba. 

Ca sfat ti-as zice sa lucrezi problema Secventa...

[•k_ounu_eddy]

Chiar la asta lucram 

[•Florian]

Am gasit aproximativ aceeasi rezolvare k Barca Cristian Mihai.....da` iau 0 puncte o sa mai incerc:weightlift:

[•raduzer]

nu inteleg de ce iau numai 80 de puncte 
am facut cu sume partiale de la 1 la n (in vectorul s) si inca un vector (t) care are pe pozitia i maximul dintre sumele partiale pana la i, apoi am facut maximul dintre t[i-1]+s[n]-s[i-1] cu i=1,n ,  dar nu merge decat pe 8 teste 

[•gabitzish1]

eu iau doar primele 3 teste apoi imi da SIGSEV.. care e problema?? imi explica cineva si mie?

[•marcelcodrea]

http://infoarena.ro/documentatie/evaluator

Cod:

11(SIGSEGV): Segmentation fault. Asta in 99% din cazuri inseamna ca ai probleme cu accesul la memorie. Ai iesit din limitele unui vector, ai facut stack overflow, etc.

[•Florian]

nu inteleg de ce iau numai 80 de puncte 
am facut cu sume partiale de la 1 la n (in vectorul s) si inca un vector (t) care are pe pozitia i maximul dintre sumele partiale pana la i, apoi am facut maximul dintre t[i-1]+s[n]-s[i-1] cu i=1,n ,  dar nu merge decat pe 8 teste 

La fel patesc si eu. Iau WA pe testele 8 si 9. Poate cineva sa imi spuna ce as putea gresi? Pe testele mele imi da corect.

[•Mishu91]

Si eu patesc tot asa 

LE : Mi-am gasit greseala... acu iau si io 100

[•Addy.]

cred ca este o greseala in exemplu, la ordinea in care sunt asezate biletele.. sau nu am inteles eu bine.

[•Florian]

Nu ai inteles tu bine. 

[ Ti-as explica, daca ai spune cum 'intelegi' tu. ]

[•Addy.]

a, scuze. ma derutase numerotarea de la explicatie, credeam ca reprezinta numarul de buline

[•ssergiuss]

Exista vreun caz particular? Nu stiu de ce pic testele 8 si 9. Imi da suma gresita. Chiar nu stiu ce am putut gresi . Daca imi poate da cineva vreun test mai dubios i'as fii recunoscator.

[•Florian]

Eu picam testele 8 si 9, daca atunci cand faceam subsecventa de suma maxima, in for, puneam   "if(a[  i ] <= 0 ) " in loc de " if(sc<=0) ". [ if-ul ala care reseteaza suma curenta, daca aceasta este negativa]. Vezi, poate faci si tu aceeasi greseala. 

[•ssergiuss]

Mersi oricum, dar eu fac cu sume partiale .
[later edit]
A rezolvat cineva problema calculand secventa de suma minima?