383 2sec

[•filipb]

Aici puteţi discuta despre problema 2sec.

[•vanila0406]

la problema asta extrag secventa de suma minima si apoi secventa de suma maxima din jumatatea de dupa ea....am 60 pte....gresesc cu ceva?
va rog spunetimi 

[•gabitzish1]

eu procedez cam la fel.. secventa de gasesc suma minima din sir, apoi pe cea cu suma maxima de dupa secventa cu suma minima.. si fac diferenta....primesc doar 70p si WA pe testele 4, 8, 10.
Sugestii?? posibile greseli???

[•Florian]

Nu am rezovat ink problema, insa cred k stiu unde gresesti! Cat iti da pt:

Cod:

7
-10 -20 -30 200 300 -80 100

Cred k iti da 20...iar raspunsul corect este 440... Sper sa nu gresesc....[

[•gabitzish1]

imi da 580.. dar nu vad dc ti'ar da 440

[•cos_min]

Pentru testul anterior raspunsul este 580.

@gabitzish1

Ai putea face ceva de genu secv de suma minima pana i si secv de suma maxima care se termina in i si verifici pentru fiecare i(luand maximul diferentei dintre cele 2 secvente mentionate anterior). Cel putin eu asa am facut si am luat 100.

[•Florian]

Da..facusem adunare in loc de scadere..greseala mea..dar s`ar putea sa fie din cauza k pozitia de sfarsit a sumei minime sa fie kiar pozitia n..

[Edit later] Am incercat si eu problema..iau doar 40 de puncte cu TLE pe ultimile 6 teste....

[•gabitzish1]

Ai putea face ceva de genu secv de suma minima pana i si secv de suma maxima care se termina in i si verifici pentru fiecare i(luand maximul diferentei dintre cele 2 secvente mentionate anterior). Cel putin eu asa am facut si am luat 100.

am incercat.. iau TLE p ultimele 6 teste...

[•Tabara]

Ai putea face ceva de genu secv de suma minima pana i si secv de suma maxima care se termina in i si verifici pentru fiecare i(luand maximul diferentei dintre cele 2 secvente mentionate anterior). Cel putin eu asa am facut si am luat 100.

am incercat.. iau TLE p ultimele 6 teste...

ai O(n) ?

[•gabitzish1]

nu... nu m'am prins cum sa fac cu O(n) la sugestia lui cosmin.. ce am inteles eu e : pt un i=1 pana la n, sa gasesc secv d suma minima d la 1 la i si secv de suma maxima care se termina in i....

[•Tabara]

nu... nu m'am prins cum sa fac cu O(n) la sugestia lui cosmin.. ce am inteles eu e : pt un i=1 pana la n, sa gasesc secv d suma minima d la 1 la i si secv de suma maxima care se termina in i....

Calculezi pentru fiecare element in parte,
secventa de suma minima care se termina pe pozitia i si
secventa de suma maxima care incepe pe pozitia i

iar apoi doar cauti pozitia i in care diferenta intre ele este maxima.
 

[•Florian]

Calculezi pentru fiecare element in parte,
secventa de suma minima care se termina pe pozitia i si
secventa de suma maxima care incepe pe pozitia i

iar apoi doar cauti pozitia i in care diferenta intre ele este maxima.
 

Am incercat asta si iau doar 40...cu TLE....esti sigur k intra in timp o rezolvare k asta?  S`ar putea sa-mi scape ceva...dar totusi e TLE, nu WA

[•Tabara]

Calculezi pentru fiecare element in parte,
secventa de suma minima care se termina pe pozitia i si
secventa de suma maxima care incepe pe pozitia i

iar apoi doar cauti pozitia i in care diferenta intre ele este maxima.
 

Am incercat asta si iau doar 40...cu TLE....esti sigur k intra in timp o rezolvare k asta?  S`ar putea sa-mi scape ceva...dar totusi e TLE, nu WA

Eu cred ca e imposibil sa se scoata mai putin de O(n)....
Singurul lucru pe care ti l-as sugera e sa faci citirile in C. ( freopen )
 

[•cos_min]

Pai iti precalculezi tu doua siruri
A(i) - secv de suma minima care se termina in i
B(i) - secv de suma maxima care incepe in i

Pentru asta ai O(n).

Dupa care mai faci o verificare in O(n), luand maxim(B(i)-A(i)) .

[•Florian]

In felul asta am facut si eu..numai k nu am pastrat cele doua siruri (A si B)...faceam la fiecare pas compararea cu diferenta maxima pana in acel moment...cat despre citire, citesc cu fscanf, deschizand cu f=fopen(...); cred k o sa reiau implementarea de la inceput...akum iau 50 de puncte...e un salt totusi  Multumesc mult de ajutor 

[•Florian]

Ei bine...kred k mi`am dat seama ce gresesc...nu cred k am facut o parcurgere o(n)..deci ..pt fiecare element i parcurgeam sirul de la 1 la i pt suma minima si de la i+1 la n pt suma maxima...deci nu e complexitae liniara...insa nu vad cum as putea face kestia asta in o(n)...cum pot face pt fiecare pozitie i , smin si smax fara inca o parcurgere ,,,,cred k aici greseam...

[•devilkind]

faci intai o parcurgere in calculezi A - suma minima ptr primele i si apoi ink o parcurgere ptr B - suma maxima ptr ultimele i elemente.

[•Florian]

Intr`adevar! Am reusit sa fak o implementare buna! dar iau KBS 11! Mi se pare normal, intrucat am trei vectori de 1 milion! Am trimis o sursa cu vectorii declarati de 500000 si iau 70 de puncte! Multumesc tuturor de ajutor!  Am avut ce invata din problema asta!

[•Dastas]

Este memorie, mie mi-a intrat lejer cu 3 vectori de 1 milion. De la altceva trebuie sa fie...

[•Florian]

Nu prea are ce altceva sa fie...gandeste`te k trimit aceeasi sursa , insa cu vectori de 500.000 si iau 70! Iar cand o trimit cu vectori de 1 milion iau KBS...amazing...

[•Dastas]

Ai incercat sa-i declari dinamic, cu new? de exemplu, in loc de int a[NMAX], sa ai int *a = new int[NMAX];

Desi mie imi merge daca nu-i declar dinamic... esti sigur ca nu faci nimic altceva?

[•Florian]

In sfarsit!!! A intrat cu alocarea dinamica!    Multumesc mult de ajutor! [ps: Nu stiam faza cu alocarea dinamica. Si mai mijto e faptul k, eu desi in lucrez in borland, nu`mi mai da eroarea "Array size too large" dak aloc dinamic...] 

[•Dastas]

Inca o sugestie: foloseste compilatorul GCC. Cu asta se evalueaza si pe site, si nu degeaba, este mult superior borland-ului. Pentru IDE ai mai multe variante: rhide (interfata asemanatoare cu cea din borland), DevCPP, Code::Blocks...

[•Pepelea_Flaviu]

Buna!! Am si eu o intrebare pentru ce-i care stiu free pascal. Ce inseamna "Program exited with exitcode = 0", "Error within GDB Error Code = 0" ] ? Am facut si eu problema excursie de la nationala si am luat 95 de puncte. La al doilea test imi dai non-zero exit status. Ma poate ajuta cineva?

[•CezarMocan]

Pentru prima intrebare. Cred ca ti s-a stricat debuggeru. Si eu am patit aia acum cateva zile si am reinstalat pascalu. Nu stiu daca e solutia cea mai buna...