030 Secventa 3

[•marcelcodrea]

Si eu am facut-o in O(n) si am luat 100 din prima deci sigur e greseala de implementare la rmikeweb...nu stiu daca merge pe toate testele insa am facut-o exact ca pe Secventa2 +verficarea cu limita superioara mutand startul cu unu daca nr de el din secventa este mai mare decat maximul de el din care poate fi alc secventa recalculand valoarea cu startul mutat(in O(1) calculez suma de la x la y deci am preprocesat),chestie care nu trebuia facuta la Secventa2(unde se verifica doar limita inferioara).Ori sunt testele prost alese ori e chiar buna solutia...insa eu mizez pe a doua optiune!!! 

[•amadaeus]

Si eu am facut-o in O(n) si am luat 100 din prima deci sigur e greseala de implementare la rmikeweb...nu stiu daca merge pe toate testele insa am facut-o exact ca pe Secventa2 +verficarea cu limita superioara mutand startul cu unu daca nr de el din secventa este mai mare decat maximul de el din care poate fi alc secventa recalculand valoarea cu startul mutat(in O(1) calculez suma de la x la y deci am preprocesat),chestie care nu trebuia facuta la Secventa2(unde se verifica doar limita inferioara).Ori sunt testele prost alese ori e chiar buna solutia...insa eu mizez pe a doua optiune!!! 

Eu mizez pe prima
Din cate am inteles, tu nu iei in vedere decat secventele de lungime exact U... 

[•anamaria1]

prima mea rezolvare lua 50 pcte si faceam raportul dintre suma costurilor si suma timpurilor o singura dupa ce selectam raportul maxim comparand produsul mezilor cu extremi. la a doua rezolvare fac raportul de fiecare data cand determinam o noua suma si iau 70 pcte. nu e mai corecta prima solutie, mai multe impartiri ducand la propagarea erorilor.

[•gabitzish1]

Avand in vedere ca la prima varianta iei WA + TLE.. iar la a doua iei doar TLE, inseamna ca in primul caz e ceva gresit.

[•tm_radu]

Am citit din postul de pe forumul TopCoder cum s-ar rezolva dinamic subproblema determinarii unei secvente de suma maxima cu minim A elemente. Este vreo metoda de a rezolva tot dinamic si restrictia ca lungimea secventei este <= B?

[•fireatmyself]

mai citeste enuntul problemei ciclu de aici http://www.ginfo.ro/revista/13_8/probleme.pdf si solutia ei de aici http://www.ginfo.ro/revista/14_1/solutii2.pdf.

problema se numeste 'Sum'.

[•amadaeus]

Am citit din postul de pe forumul TopCoder cum s-ar rezolva dinamic subproblema determinarii unei secvente de suma maxima cu minim A elemente. Este vreo metoda de a rezolva tot dinamic si restrictia ca lungimea secventei este <= B?

Cu un deque, in care pastrezi ultimele B elemente (sau cate ai nevoie, dupa caz).

[•sima_cotizo]

Si eu iau 70p cu WA : afisez numerele de forma x01 in x.01, fac cu deque pt a gasi valoarea aia maxima, am un vector de sume partiale de forma S[ i ]=S[ i-1 ] + A[ i ] - B[ i ]*v (v din cautarea binara), am inmultit numerele cu 100... nu imi dau seama unde gresesc 

Exista cazuri speciale?

LE: am gasit, nu luam in considerare unele secvente...

[•valentin.harsan]

Eroare in evaluatorul problemei! http://infoarena.ro/job_detail/741631 

[•bogdan2412]

Nu afisezi in fisierul corect.

S-a reparat problema cu evaluatorul.

[•valentin.harsan]

uitati un borderou de evaluare http://infoarena.ro/job_detail/741833 
9 teste cu WA si un singur test corect care valoreaza 100 pct 
chiar am luat WA pe testele alea sau e facut la misto in evaluator

[•gabitzish1]

Mai incearca putin, poate iei 1000!

[•dushmi]

Da, luai 1000 daca faceai totul bine. Fixed now

[•marinutza]

eu am doar 90 de puncte si imi da wrong answer...poate sa.mi dea cineva un exemplu pe care nu ar merge...la cele date de mine imi da raspuns corect.eu fac rezolvarea cu vector de sume partiale ...