infoarena

Aici puteţi discuta despre problema Timbre (http://infoarena.ro/problema/timbre).

Completati timbre.in.

:oops: gata :)
spor !

am vazut ca unii useri (Airinei Adrian de ex.) au rezolvat problema in 0.01 si as vrea sa ii intreb daca nu cumva au gasit un greedy (eu am demonstrat (incomplet) ca nu exista si este posibil sa fi gresit   :oops: )
 :mrgreen:

E cam greu sa demonstrezi ca nu exista greedy la o problema, prezinta-ne si noua "demonstratia" ta.  :shock:

pai "demonstratia" se bazeaza pe reducere la absurd.
am presupus ca exista o rezolvare greedy (mai multe de fapt, toate avand la baza niste sortari si o observatie de bun simt) si ca tot romanu am gasit un exemplu pentru care nu merge aceasta metoda.
acest timp de exemplu a fost exploatat in 90% din teste.
admit totusi ca nu am epuziat toate greedy-urile existente care ar putea furniza o solutie la aceasra problema, deci am o demonstratie incompleta :P. am pus intrebarea de mai sus tocmai in ideea de am confirma sau infirma observatiile mele.
imi cer scuze pentru exprimarea incorecta de mai sus. nu detin o demonstratie completa (foarte greu de gasit una, dupa cum spune si greco), ci doar o demonstratie ce are la baza cateva cazuri de aplicabilitate a metodei greedy.

Deci ca s-o scurtam nu ai demonstrat ca nu merge greedy, ai aratat ca unele greedy-uri au contraexemple. Adica exact ceea ce ma asteptam sa fi facut.  :)

:) da varule :P. daia sunt tare curios sa vad ce cazuri imi scapa :) (ca in mod evident exista  :mrgreen: )

eu am rezolvat cu greedy.. nu am demonstrat insa riguros corectitudinea lui, m-am bazat doar pe niste chestii intuitive :P

p.s: daca vrei trimite-mi un pm si iti prezint detaliat metoda mea

u-92 : am dat pm si astept raspuns :P

damn, am dat-o in bara urat la faza asta (sa-mi fie rusine). eh, ma revansez cu a treia problema  :evil:  :evil:  :evil:
[veti regreta ca l-ati suparat pe balaur :P]

eu am obtinut timpi buni cu o rezolvare O((n div k)*m). initial am fost si eu uimit ca am luat 100. nu aveam timp sa implementez ceva mai complicat si am scris primul lucru ce mi-a venit in minte; 25 de randuri mi-a luat in total. ptr teste cu k mic, programul meu ar fi busit.

Exista intotdeauna solutie ?

Da

poate sa-mi dea cineva un hint despre ce e mai special la testul 8?
am observat ca mai multa lume a avut probleme cu testu 8 ???
multzam

later edit: nevermind, i got it  :)

Solutia cea mai buna e O( M log M) ?

Exista cazuri speciale la problema asta ?
Greedy-ul meu pica testele 4 si 8 si nu inteleg dc ](*,)
Aici e sursa mea :http://infoarena.ro/job_detail/842192
Sugestii ?

observ ca tu iei toate intervalele in ordinea crescatoare a capatului superior, si la fiecare pas cumperi o secventa din intervalul actual. exista posibilitatea ca aceeasi secventa (sa zicem [0, k-1], cat e cea pe care vrei sa o acoperi initial) sa poata fi cumparata din mai multe intervale, cu costuri diferite, si atunci nu are sens sa le folosesti pe toate.
in plus, pentru n = k (sau pentru valori apropiate), si intervale de genul [0,1] [0,2] [0,3], ..., [0,n], algoritmul tau parcurge si cumpara toate intervalele mici, oprindu-se doar cand a acoperit intreaga secventa [1,n]. in cazul asta e clar ca poti cumpara doar ultimul interval in intregime, cu un cost mult mai mic decat suma tuturor. aceeasi idee si pentru alte valori ale lui k: solutia nu consta intotdeauna in intervale alaturate, ci intr-o submultime formata din intervale care nu au neaparat legatura ca pozitie in sirul ordonat.

algoritmul meu se bazeaza pe o idee asemanatoare, doar ca incep constructia de la pozitia n, si folosesc sirul sortat descrescator. initial, e sigur ca exista cel putin un interval din care sa pot cumpara o secventa ce se termina pe pozitia n (altfel nu ar exista solutie). in caz ca exista mai multe astfel de intervale, il aleg pe cel cu costul minim si cumpar din el o secventa de dimensiune k (nu are rost sa cumpar una mai scurta).
la pasul urmator, voi avea de cumparat o secventa care se termina pe pozitia n-k, alegand-o din mai multe intervale. din nou, aleg intervalul cu costul minim, cumpar de acolo secventa de lungime k, pozitia noua pe care va trebui sa o acopar va fi n-2k. de aici se repeta tot procedeul.

mai trebuie avut grija la marcarea intervalelor folosite, ca sa nu cumperi 2 secvente din acelasi interval.
sper ca te-am putut ajuta.  :)

Cum se poate rezolva aceasta problema folosindu-te de un heap? Eu nu-mi dau seama de alta solutie in afara de greedy  :-k

Pai greedy, dar cum faci sa-ti intre solutia in timp fara heap?

Pai eu am complexitate M * (N/K). La fiecare pas iau din intervalul  (pe care inca nu l-am folosit) de cost minim pentru care capatul din dreapta este >= N, apoi marchez intervalul ca si folosit si actualizez N-ul: N -= K. Repet procedeul pana cand ajung cu N la 0.

Solutia cu heap e aceeasi, dar in loc sa cauti in timp liniar intervalul nefolosit de cost minim din dreapta, sortezi descrescator intervalele si le adaugi intr-un heap extragand la fiecare pas intervalul de cost minim. Complexitatea devine O(MlogM + NlogM) in loc de O(NM).

Cam ce cazuri particulare pot interveni? ( WA pe 4 si 8 )

M-am gandit la o rezolvare bazata pe o dinamica :

DIN[ i][j] -> costul minim pentru a rezolva sumbproblema pe [1..i] cu primele j dintre timbre.

Astfel avem relatia DIN[ i][j] =
   - DIN[ i][j-1], daca M[j] < i
   - DIN[max(0, i-k)][j-1] + C[j] , daca M[j] >= i si costul se imbunatateste (adica este mai mic decat DIN[ i][j-1])

Mentiune :
 - DIN[0][j] = 0, oricare j
 - DIN[ i][0] = infinit, oricare i >= 1

Rezolvarea nu imi iese din timp, in schimb da WA pe 3 dintre teste.
Ce am busit?

Păi îți merge pe exemplu dacă îl rescrii ca:

4 3 2
6 2
5 3
2 1

?

Poate sa imi dea cineva testul 8 (sau un test cu o structura asemanatoare)? Am vazut ca multi au avut WA pe testul 8 si chiar nu stiu ce sa repar...