887 Rec

[•pauldb]

Aici puteti discuta despre problema Rec.

Problema a fost adaugata de Vlad Gavrila. Mai multe detalii la Extinde arhiva.

[•unknownliviu]

Observ ca nu se face cu bkt... ideei?

[•eudanip]

De obicei la problemele care iti cer numarul total de solutii te gandesti in primul rand la programare dinamica. Tine minte, sigur o sa mai dai peste astfel de probleme .

[•danalex97]

Ma puteti ajuta si pe mine cu o idee sau macar un pont, va rog ?   Cea mai buna solutie pe care am gasit-o are complexitate mult prea mare. Un O(N*S) mi se pare ca ar fi solutia mea ...  

Ma folosesc de faptul ca S=x[1]+x[2]+...+x[n] , unde x[1]>=x[2]>=..>=x[n] , deci putem recrie ecuatia asa:
S=(y[1]-F+1)+(y[2]-F+1)+(y[3]-F+1)+ ... + (y[n]-F+1) + (F-1)*N , deci S-(F-1)*N=y[1]+y[2]+...+y[n].
Astfel am simplificat problema din a face suma S de N nr. descresctoare >=K in suma S de N nr. descrescatoare >=1.

Apoi fac o matrice A[][] care se construieste in felul urmator: A[j][k]=A[j-1][k/2]+ A[j-1][k/2+1]... + A[j-1][k/2+N-1] .
Solutia va fi A[ S ][ N ].

Ce e pana aici e O(N*S^2) si pentru a optimiza am facut sume partiale. Se poate optimiza si mai mult sau ideea mea de pornire e gresita ?

[•assa98]

Am facut solutia de 80p cu memoizare. Ma poate ajuta cineva sa ajung la 100, sau trebuie schimbata metoda complet?