infoarena

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

poate cineva sa-mi dea un indiciu la problema asta :-k  Am avut impresia c-am facut-o da dupa ce am vazut 20p in fata ochilor mi-am dat seama ca nu merge. Banuiesc ca e N*logN da in nici un caz dinamica mea... ](*,)

Hint: cautare binara  :mrgreen:

Gata..gata.. nu mai zi ca mi-ai zis destul..chiar prea mult...thx :mrgreen:

Am aflat si eu solutia cu cautare binara.... dar la Secventa 3 s-au luat punctaje de 100 cu greedy. Exista vreun greedy demonstrat, sau s-a nimerit sa ia testele?  :roll:

Am luat 100 cu  greedy   :)

Detaliaza, impreuna cu demonstratia (cel putin o demonstratie intuitiva, sau lautareasca, cum ar spune proful meu de mate).

Stiu ca s-a mai luat 100 cu greedy, eu vreau sa stiu daca s-a luat pe bune 100 sau au fost testele in asemenea fel incat sa le treaca un program gresit.

Daca ai luat 100 nu inseamna ca ai si rezolvat-o.  :roll:

apropo        greedy != brute force            :evil:

Matrix.. astept si eu greedy-ul tau.. idea sau programul. Am luat 100..dar sunt curios!

Restrictiile de la problema asta sunt sigur bune? Mi se pare destul de dubios... fac cu cautare binara si iau doar 30 de puncte....

Chiar daca vrei s-o faci cu cautare binara, faci iterativ, apoi realizezi ca poti simplifica muult. distractie! :)

O problema era un overflow ca am un vector de sume partiale.... am ajuns la ``cota'' 70.  :(

Am gasit si a doua problema.... penibila de altfel.... nu afisam bine. Faceam printf ("%d.%d\n", sol/100, sol%100);
 ](*,)  ](*,)

Dati-mi si mie un hint ce sa caut binar va rog ! N-am nici o idee  ](*,)

Raspunsul simplu la intrebarea ta este: valoarea maxima a sumei, dar cred ca raspunsul asta nu te ajuta prea mult. Citeste problema de aici http://www.topcoder.com/rtables/viewThread.jsp?forum=7167&thread=396255&mc=20 care seamana cu secventa 3, si 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 . Acum ar trebui sa nu mai ai dificultati in rezolvarea problemei.

Mersi Cosmin!

Stiu ca algoritmul optim e cel cu cautare binara, dar vreau sa stiu ce e gresit la metoda mea.
A doua siruri : c si t care reprezinta costul total al elementelor de la 1 la i, respectiv timpul total. Calculez toate valorile posibile de lungime intre L si U  si retin valoarea maxima. Problema nu e ca imi iese din timp, ii ca primesc WA.

..ai implementat gresit, evident :D

..am scris si eu o solutie d-asta si ia 80 de punte.. cu 2 teste TLE.. nici vorba de WA

cristi8, de cat ti-ai declarat cele 2 siruri in care ti minte sumele? io iau numa 40 , la 5 teste imi da RUN ERROR - Invalid memory reference

cum fac afisarea k lumea la problema asta ca algoritmul e cel bun cu cautare binara, iau 70 p. sigur e de la afisare ... inmultesc nr cu 10000, ii verific ultimele 2 cifre daca s 9, dacas 9 il rotunjesc +=100, impart la 100, afisez nr/100, nr%100. si cu rotunjire si fara iau tot 70 .... cautarea binara o fac pana la final, nu rotunjesc numaru la fiecare pas. suma max o compar cu 0.0000001 resp -0.0000001. any ideas ? ale dreq nr reale ... memorez intru double evd.

Ai grija cum afisezi 101 de exemplu .. sa nu afisezi 1.1 in loc de 1.01

dap 100 p  ](*,) . ce prost am fost ca nu miam dat seama. ms mult !  =D>

Algoritmul in O(NlogN) la problema asta nu-i optim exista un algoritm in O(N) care ii usor de demonstrat si merge la prob asta. Am luat 80p cu el dar faza ii ca am gresit la implementare ca de obicei. Si faza ii ca nu-i greedy cum scria Matrix mai sus ci PD  :D.

Poti sa descrii algoritmul O(N)? Eventual trimite-mi un mesaj personal ca sa nu apara rezolvarea pe forum.

Pana la urma cum era rezolvarea O(n)?

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 :D
Din cate am inteles, tu nu iei in vedere decat secventele de lungime exact U...  :-k

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.

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.

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?

problema se numeste 'Sum'.

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

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

Eroare in evaluatorul problemei! http://infoarena.ro/job_detail/741631 (http://infoarena.ro/job_detail/741631)  :-'

Nu afisezi in fisierul corect.

S-a reparat problema cu evaluatorul.

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

Mai incearca putin, poate iei 1000! :D

Da, luai 1000 daca faceai totul bine. Fixed now :)

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