Soluţia problemei Teste

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))

40 de puncte (O(n^{3)+O(sqrt(S))}, O(n2)+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.

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.