h1. 'Soluţia':incalzire2020/solutii/teste problemei 'Teste':problema/teste

h1(#teste). 'Soluţia':incalzire2020/solutii/teste problemei 'Teste':problema/teste
 
h3. 20 de puncte $(O(n^k)+O(sqrt(S)))$
 
Generăm toate şirurile cu proprietaţile cerute folosind backtracking, adunăm toate elementele la $S$ şi numărăm divizorii lui $S$ în $O(sqrt(S))$
 
h3. 40 de puncte $(O(n^3)+O(sqrt(S))$, $O(n^2)+O(sqrt(S))$, $O(n)+O(sqrt(S)))$
 
La această grupă, putem în continuare să calculam explicit divizorii lui $S$, dar trebuie să găsim o metodă mai rapidă de a găsi suma $S$. O metoda poate fi programarea dinamică, calculând $sum(l)(val)$ - suma tuturor elementelor şirurilor de lungime $l$ cu ultimul element egal cu $val$ şi $nr(l)(val)$ -numărul de şiruri de lungime $l$ cu ultimul element egal cu $val$. Recurenţa va fi:
 
* $sum(l)(val)=suma(sum(l-1)(i),i=1..n)+suma(nr(l-1)(i)+i=1..n)*val)$
* $nr(l)(val)=nr(l-1)(val)$
 
$S$ va fi egal cu suma din $sum(n)(i) 1<=i<=n$$.
Această dinamică poate fi optimizată obţinând diverse complexităţi, dar forma de mai sus este suficientă pentru a obţine 40 de puncte.
 
h3. 100 de puncte O(sqrt(n)+sqrt(k))
 
Pentru a reuşi să obţinem un algoritm a cărui complexitate nu depinde de $S$, trebuie să exprimăm $S$ într-un mod mai simplu. Pentru a găsi o soluţie începem prin a fixa o valoare pe o poziţie şi a vedea în câte şiruri apare, la $S$ adăugandu-se produsul între valoare şi număr de apariţii. Dacă fixăm numărul de pe poziţia $poz$ ca fiind $val$, şirul
va arăta astfel:
Pozitie $|1 2.. poz ... n|$
Valoare $|? ?.. val ... ?|$
Observam ca numarul de siruri in care $val$ apare pe pozitia poz este numarul de moduri de a inlocui $n-1$ caractere $?$ cu numere de la $1$ pana la $k$. Acest numar este egal cu $k^(n-1)$. Daca fixam doar pozitia $poz$ si facem suma pentru toate numerele $val$ de la $1$ la $k$, vom obitne $k^(n-1)*k*(k+1)/2$. Deoarece expresia este aceeasi indiferent oricare din cele $n$ pozitii va fi $poz$, $S$ va fi $n*(k^(n-1)*k*(k+1)/2)$.
Observăm ca în formula anterioara apar doar puteri ale lui $n$, $k$ şi $k+1$ (şi $2$, pe care trebuie să îl reducem de unde este posibil), deci putem precalcula factorii primi ai acestora, şi observând la ce puteri apar cele 3 numere în formula pentru $S$, putem obţine factorizarea lui $S$ "combinând" cele 3 factorizări. Răspunsul va fi produsul puterilor (la care se adauga $1$) la care apar factorii primi ai lui $S$ în factorizarea lui.

private

protected