030 Secventa 3

[•fluffy]

Aici puteţi discuta despre problema Secventa 3.

[•rss1987]

poate cineva sa-mi dea un indiciu la problema asta  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...

[•domino]

Hint: cautare binara  

[•rss1987]

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

[•greco]

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?  

[•Matrix]

Am luat 100 cu  greedy  

[•greco]

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.  

[•Matrix]

apropo        greedy != brute force            

[•DeadStar]

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

[•greco]

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

Cod:

...

[•cavendish]

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

[•greco]

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

[•greco]

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

[•sarabogdan]

Dati-mi si mie un hint ce sa caut binar va rog ! N-am nici o idee  

[•Cosmin]

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.

[•sarabogdan]

Mersi Cosmin!

[•tm_radu]

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.

[cristi8]

..ai implementat gresit, evident

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

[•cos_min]

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

[tmac]

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.

[ditzone]

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

[tmac]

dap 100 p  . ce prost am fost ca nu miam dat seama. ms mult ! 

[•rmikeweb]

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  .

[•domino]

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  .

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

[•tm_radu]

Pana la urma cum era rezolvarea O(n)?