Soluţia problemei 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ă.
Subtaskul 1
Când numărul de secvenţe posibile este cel mult 2 * 106, problema poate fi rezolvată prin backtracking, generând toate secvenţele posibile.
Subtaskul 2
Când Ai = 1, pentru orice i, numărul de secvenţe de alegeri de lungime L este combinari(N, L) * L.
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 * S2), unde S = sumă(Ai).
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(Ai)) valori distincte. Obţinem complexitatea O(S2 * sqrt(S)).
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(S2).
