Diferente pentru algoritmiada-2010/runda-finala/solutii/lkperm intre reviziile #4 si #2

Nu exista diferente intre titluri.

Diferente intre continut:

Dacă plasăm elementul $n$ pe cea de-a $p$-a poziţie, $1 ≤ p ≤ K$ permutarea va arăta astfel:
$x{~1~} x{~2~} x{~3~} ... x{~p-1~} n x{~p+1~} x{~p+2~} ... x{~n-1~}$
Elementul $n$ va fi maximul pentru $p$ secvenţe, iar primele $p-1$ elemente nu vor fi maxime în nicio secvenţă. Prin urmare vor fi <tex>(n-1)*(n-2)*(n-3)*...*(n-P-1)*f(n-P)</tex> posibilităţi
Elementul $n$ va fi maximul pentru $p$ secvenţe, iar primele $p-1$ elemente nu vor fi maxime în nicio secvenţă. Prin urmare vor fi <tex>(n-1)*(n-2)*(n-3)*...*(n-P-1)*f(n-P)</tex>
Aşadar, <tex>f(n)=f(n-1)+(n-1)*f(n-2)+(n-1)*(n-2)*f(n-3)</tex><tex>+...+(n-1)*(n-2)*...*(n-K+1)*f(n-K)</tex>, dacă <tex>n>L</tex>
<tex>f(n)=n!</tex>, altfel
Implementarea directă a acestei formule aduce $40$ de puncte, deoarece are complexitatea $O(N*K)$. Pentru $100$ de puncte vom încerca să restrângem egalitatea şi observăm că
<tex>f(n-1)=f(n-2)+(n-2)*f(n-3)+...+(n-2)*(n-3)*...*(n-K)*f(n-K-1)</tex>
Deci <tex>f(n)=f(n-2)+(n-2)*f(n-3)+...+(n-2)*(n-3)*...*(n-K)*f(n-K-1)+</tex><tex>+(n-1)*f(n-2)+(n-1)*(n-2)*f(n-3)+...+(n-1)*(n-2)*...*(n-K+1)*f(n-K)</tex>
<tex>f(n)=n*f(n-2)+n*(n-2)*f(n-3)+...+n*(n-2)*(n-3)*...*(n-K+1)*f(n-K)</tex><tex>+(n-2)*(n-3)*...*(n-K)*</tex><tex>f(n-K-1)</tex>
<tex>f(n)=n*f(n-1)-(n-1)*(n-2)*...*(n-K)*f(n-K-1)</tex>
Aşadar, <tex>f(n)=f(n-1)+(n-1)*f(n-2)+(n-1)*(n-2)*f(n-3)</tex><tex>+...+(n-1)*(n-2)*...*(n-K-1)*f(n-K)</tex>

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.