|
Titlul: 887 Rec Scris de: Paul-Dan Baltescu din Iulie 31, 2009, 20:33:33 Aici puteti discuta despre problema Rec (http://infoarena.ro/problema/rec).
Problema a fost adaugata de Vlad Gavrila. Mai multe detalii la Extinde arhiva (http://infoarena.ro/implica-te/extinde-arhiva). Titlul: Răspuns: 887 Rec Scris de: Maria Liviu Valentin din Ianuarie 08, 2011, 12:25:41 Observ ca nu se face cu bkt... ideei? :-'
Titlul: Răspuns: 887 Rec Scris de: Eugenie Daniel Posdarascu din Ianuarie 08, 2011, 16:49:41 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 :thumbup: .
Titlul: Răspuns: 887 Rec Scris de: Dan H Alexandru din Martie 01, 2012, 10:10:50 Ma puteti ajuta si pe mine cu o idee sau macar un pont, va rog ? :-k 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 ? Titlul: Răspuns: 887 Rec Scris de: Andrei Stanciu din Martie 25, 2013, 21:57:54 Am facut solutia de 80p cu memoizare. Ma poate ajuta cineva sa ajung la 100, sau trebuie schimbata metoda complet?
|