h2. Indicatii de rezolvare

Ideea "naivă" de rezolvare a acestei probleme presupune generarea tuturor permutărilor de ordin $n$ şi calcularea numărului de cicluri pentru fiecare din acestea. Această rezolvare are complexitate exponenţială şi va obţine $10$ puncte.

Ideea "naivă" de rezolvare a acestei probleme este determinarea răspunsului generând efectiv, prin metoda backtracking, fie toate permutările de ordin $n$ şi determinarea celor care au $m$ cicluri, fie toate partiţionările unei mulţimi de $n$ elemente în $m$ submulţimi nevide. Această rezolvare are complexitate exponenţială şi va obţine $10$ puncte.

În urma unor demonstraţii matematice (explicate pe larg în link-urile de mai jos), pentru funcţiile lui Stirling se pot obţine recurenţele :

În urma unor demonstraţii matematice (explicate pe larg în link-urile de mai jos), pentru funcţiile lui Stirling se pot obţine recurenţele:

<tex> s(n,m) = s(n-1,m-1) - (n-1)*s(n-1,m) </tex> şi <tex> S(n,m) = S(n-1,m-1) + m*S(n-1,m) </tex>.

h4. Recursivitate:

O primă metodă de rezolvare ce foloseşte observaţia de mai sus este determinarea valorilor $s(n,m)$ sau $S(n,m)$, implementând un algoritm recursiv ce modelează relaţiile de recurenţă prezentate. Această metodă obţine $50$ de puncte. O sursă pe această idee se găseşte 'aici':job_detail/429247?action=view-source.

Pentru un singur test, o metoda optima de rezolvare este cea care foloseste o functie recursiva si calculeaza la fiecare pas elementele necesare recurentei pasului actual. Totusi, daca nu este folosita memoizarea, la un numar mai mare de teste, aceasta rezolvare va iesi din timp. Aceasta metoda are complexitatea o(N*M*T). Folosind aceasta metoda veti obtine 50 de puncte, o sursa ce foloseste aceasta metoda poate fi gasita "aici":http://infoarena.ro/job_detail/429247?action=view-source.
 
h4. Programare dinamica:
 
Solutia optima a acestei probleme este cea care foloseste metoda programarii dinamice. astfel vor fi precalculate 2 matrici s[N][M] si S[N][M] cu semnificatia s[i][j]=s(i,j) si S[i][j]=S(i,j). Folosindu-se aceasta metoda, la fiecare test vom raspunde in o(1) la intrebare si deci complexitatea va fi o(N*M + T). Aceasta rezolvare obtine 100 de puncte si o sursa ce o foloseste poate fi gasita "aici":http://infoarena.ro/job_detail/429246?action=view-source.

Soluţia optimă pentru problema de faţă se bazează pe preprocesarea valorilor $s(n,m)$ şi $S(n,m)$, implemenând de asemenea relaţiile de recurenţă prezentate. Astfel, se va putea răspunde la fiecare test în timp $O(1)$, complexitatea totala fiind $O(N*M + T)$. Această rezolvare obţine $100$ de puncte. O sursa pe această idee se găseşte 'aici':job_detail/429246?action=view-source.

h4. Link-uri utile