028 Secventa 2

[•fluffy]

Aici puteţi discuta despre problema Secventa 2.

[•Twister]

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.

[•domino]

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:

Cod:

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

Output:

Cod:

1 13 -128489

[•Twister]

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

[•dany3dx]

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

[•Twister]

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

[•rss1987]

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

[•Twister]

multumesc frumos pentru sfat

[•dany3dx]

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)

[•domino]

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  

[•dany3dx]

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

[•Twister]

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)

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

[•cavendish]

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!

[•dany3dx]

nu incape in

Cod:

comp

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

[•domino]

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

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

[•teplesnescdenutevezi]

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.

[•Binary_Fire]

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:

Cod:

 
for (i=k;i<n;i++)
  { if ( v[i-1] > ( v[i-1] - a[poz] ) ) v[i]=v[i-1]+a[i];
    else {v[i]=v[i-1]-a[poz]+a[i];
          poz++;poz1=poz;}
    if (v[i]>max) {max=v[i];poz2=i;pozf1=poz1;}
    }

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

[u-92]

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

[•Binary_Fire]

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?

[u-92]

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

[•Binary_Fire]

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

[•dobre]

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

Cod:

poz   :  1  2  3  4 5  6  7  8 
v     : -3  1 -1  3 1 -2  8 -5
sum1  : -3 -2 -3  0 1 -1  7  2
ai suma maxim pe pozitia 7 
apoi faci suma de la 7 inspre 1
poz   :  1  2  3  4  5  6   7  8 
v     : -3  1 -1  3  1 -2   8 -5
sum2  :  7 10  9 10  7   6  8  0

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

[•Binary_Fire]

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

[•wefgef]

dobre, ptr urmatoarea intrare:

Cod:

6 2
1 2 3 -100 4 5

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.

[•dobre]

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