061 Ferma

[•domino]

Aici puteţi discuta despre problema Ferma.

[cristi8]

hmm... solutia oficiala nu e cam complicata ?
..nu e nevoie de "deque with heap order" sau alte chestii gen max-heap...
eu am facut cu
a[j] = productivitatea maxima pentru a face i strangeri din primele j sectoare, strangand oua de pe sectorul j
b[j] = productivitatea maxima pentru a face i strangeri din primele j sectoare fara a strange de pe sectorul j

si la circularitate in loc de "pentru fiecare pozitie i<=N comparam rezultatul A(i, K)+S(N)-S(i) (adaugam la secventa care il contine pe 1 o bucata care il contine pe N) cu cel mai bun obtinut", se putea mari k-ul cu 1 si solutia era in a[k][n] (varianta mea)..

... e buna ideea mea ? ..sau am avut noroc cand am luat 100 ?

[•domino]

hmm... solutia oficiala nu e cam complicata ?
..nu e nevoie de "deque with heap order" sau alte chestii gen max-heap...
eu am facut cu
a[j] = productivitatea maxima pentru a face i strangeri din primele j sectoare, strangand oua de pe sectorul j
b[j] = productivitatea maxima pentru a face i strangeri din primele j sectoare fara a strange de pe sectorul j

si la circularitate in loc de "pentru fiecare pozitie i<=N comparam rezultatul A(i, K)+S(N)-S(i) (adaugam la secventa care il contine pe 1 o bucata care il contine pe N) cu cel mai bun obtinut", se putea mari k-ul cu 1 si solutia era in a[k][n] (varianta mea)..

... e buna ideea mea ? ..sau am avut noroc cand am luat 100 ?

Da, merge si asa.. mi-am dat seama dupa concurs  

[•bogdan2412]

Inca o chestie: nu e nevoie de "deque with heap order" nici in solutia prezentata in articol. Iti trebuie o singura variabila de maxim care o actualizezi pe parcurs.

[•Cosmin]

Probabil ca ai dreptate, nu m-am uitat pe articol. De obicei cand compui o problema sau o rezolvi, prima solutie cu complexitate multumitoare ramane solutia care o ai in minte si nu mai pierzi vreme ca sa simplifici solutia daca ea nu e complicata tare la implementare, deci genul acesta de scapari mi se par acceptabile si in creerea unei probleme si in rezolvarea ei.

[•silviug]

Nu sunt greseli, Cosmine. Sunt alte modalitati de rezolvare, e drept mai complicate. Baietii fac bine ce fac: propun solutii mai destepte in anumite locuri, chestii mai simple.. intr-un cuvant discuta.. nu cred ca a fost in intentia lor sa raporteze "greseli".

[•mariusdrg]

In solutie scrie
    * Ai,j = max(Ai,j-1, Ai-1,k + Sj - Sk), pentru fiecare k<j
Si defapt nu ar trebui sa fie ceva de genu     * Ai,j = max(Ai,j-1, Ai-1,k + Sj - min(Sk,S(k+1)....Sj) ), pentru fiecare k<j?
In alte cuvinte nu este neaparat sa acoperim tot intervalul intre j si k ... sau am inteles eu gresit problema? Caz in care singurul termen independent de j ar fi A i-1,k.... si ar trebui 2 stive,nu?
Am inteles eu gresit problema?

[•Robert29]

avem voie sa avem doua secvente adiacente sau se considera una singura? adica daca luam pozitiile 2, 3 si 4, 5 le putem considera doua secvente sau doar una singura?