h1(#plangaciosi). 'Soluţia':jc2020/solutii/plangaciosi problemei 'Plangaciosi':problema/plangaciosi

h1(#plangaciosi). 'Soluţia':jc2020/solutii/plangaciosi problemei 'Plangaciosi':problema/plangaciosi
 
O primă observaţie este că pentru a rezolva problema trebuie să aflăm câte secvenţe de alegeri există pentru fiecare lungime posibilă.
 
h2. Subtaskul 1
 
Când numărul de secvenţe posibile este cel mult $2 * 10^6^$, problema poate fi rezolvată prin backtracking, generând toate secvenţele posibile.
 
h2. Subtaskul 2
 
Când $A{~i~} = 1$, pentru orice $i$, numărul de secvenţe de alegeri de lungime $L$ este $combinari(N, L) * L$.
 
h2. Subtaskul 3
 
Putem fixa, pe rând, tortul din care şi-ar dori să manânce $PlângăciosulNr1$. Fie acesta tortul $x$.
Vom folosi programarea dinamică pentru a calcula $dp[i][j] = în câte moduri putem alege j felii, considerând doar primele i torturi, astfel încât în fiecare tort să rămână un număr nenegativ de felii, iar din tortul x să nu fie luată nicio felie$.
Recurenţa pentru $i != x$ este: $dp[i][j] = suma (dp[i-1][j-t] * combinari(j, t))$, unde $0<=t<=a[i]$
Recurenţa pentru $i = x$ este: $dp[i][j] = dp[i-1][j]$
Apoi, putem calcula $cnt[x][i] = câte secvenţe de alegeri se termină cu tortul x şi au lungimea i$.
$cnt[x][i] = dp[n][i - a[x]] * combinari(i, a[x])$.
Obţinem complexitatea $O(N * S^2^)$, unde $S = sumă(A{~i~})$.
 
h2. Subtaskul 4
 
Putem îmbunătăţi soluţia anterioară observând că dacă torturile $x$ şi $y$ au acelaşi număr de felii, atunci $cnt[x][i] = cnt[y][i]$, pentru orice $i$. Astfel, putem rula dinamica anterioară câte o dată pentru fiecare valoare distinctă din $A$. În total, sunt cel mult $sqtr(2*sum(A{~i~}))$ valori distincte. Obţinem complexitatea $O(S^2^ * sqrt(S))$.
 
h2. Subtaskul 5
 
Vom construi o altă dinamică, $D[i][j][0/1] = în câte moduri putem alege j felii, considerând doar primele i torturi, astfel încât în fiecare tort să rămână un număr nenegativ de felii$. A treia dimensiune poate fi $0$ sau $1$, specificând dacă tortul din care şi-ar dori să manânce $PlângăciosulNr1$ se află între primele $i$ torturi. Recurenţa este:
 
$D[i][j][ 0 ] = suma (D[i-1][j-t ][ 0 ] * combinari(j, t))$, unde $0<=t<=a[i]$
$D[i][j][ 1 ] = D[i-1][j-a[i]][ 0 ] * combinari(j, a[i]) +  suma (D[i-1][j-t][ 1 ] * combinari(j, t))$, unde $0<=t<=a[i]$
 
 
Complexitatea acestei soluţii este $O(S^2^)$.