In this problem one of the things that is new(for me) is the fact that number of times you can reach a state i,j only depends on number of ways of reaching this state from the previous programmers and the current pogrammer. In other words, a new programmer can only effect the count for previous counts to reach a stage of dl, bugs. (dl is done lines).
A 2D DP solution will look like this
#include <bits/stdc++.h>
using namespace std;
int main() {
long long dp[501][501];
long b, a[500];
long long n, m;
long long mod;
long long ans = 0;
cin >> n >> m >> b >> mod;
for(int i=0; i<=500; i++)
for(int j=0; j<=500; j++)
/// we initialize that we can never write any line with any error
dp[i][j] = 0;
/// we can write 0 line with 0 error only in 1 way.
/// if you are doubtful ask yourself in "how many ways I can write no line?"
/// answer will be 1 way i.e. do not write the line.
dp[0][0] = 1;
for(int i=0; i<n; i++) {
cin >> a[i];
for(int ld=0; ld<m; ld++){ /// ld is lines done or lines written
for(int bugs=0; bugs+a[i]<=b; bugs++){
/// bugs is the count of bugs we can have, we cannot have more than b bugs.
/// if stage(ld, bugs) has never been reached before, i.e. dp[ld][bugs] = 0
/// this programmer also cannot reach stage(ld+1, bugs+a[i])
/// i.e. dp[ld+1][bugs+a[i]] will not change.
/// but if some previous programmer has reached this stage i.e. dp[ld][bugs] >0
/// then we can also reach ld+1, bugs+a[i]
dp[ld+1][bugs+a[i]] = (dp[ld+1][bugs+a[i]] + dp[ld][bugs])%mod;
}
}
}
for(int i=0; i<=b; i++) {
/// now for each possible stage(m, bugs) add it to answer.
/// Note that stage(m, i) means that some how we were able to have written all
/// m lines with bugs = i in total.
/// so dp[m][0] means m lines were written with no bug in any line. this is only
/// possible if atleast one programmer can write a line of code with 0 error and
/// if he writes all the lines 'm', then he will never add any error;
ans = (ans+dp[m][i])%mod;
}
cout << ans << endl;
/// Do not understand something? Feel free to send me a message or comment below
return 0;
}
Lets look at the solution from editorial
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
const int N = 505;
int a[N];
/// as we know that current programmer can only impact count of previous programmer
/// so basically we can store two instances, we can store previous instance and
/// then the current instance.
/// If you do not use two instances, you cannot differ between current and previous instance
/// more details below
int z[2][N][N];
int main() {
int n, bl, bugs, md;
scanf("%d %d %d %d", &n, &bl, &bugs, &md);
forn(i, n)
scanf("%d", &a[i]);
/// we can conclude that we can write 0 line with 0 bugs in 1 way.
/// that way is not to write anything.
z[0][0][0] = 1;
for(int it = 1; it <= n; it++){
// i will store which instance are we in
// if 'it' is odd then i is 1 else i is 0
int i = it & 1;
for(int j = 0; j <= bl; j++) {
for(int k = 0; k <= bugs; k++){
/// j is the count of lines written and k is the count of bugs
/// first we make current instance value equal to previous instance
/// i^1 (xor) will give us 0 if i is 1, otherwise 1 if i is 0. basically
/// i^1 gives the same result like (!i), if i can be 0 or 1.
z[i][j][k] = z[i ^ 1][j][k];
/// now we check that if j > 0 and bugs k is more or equal than
/// the bugs(a[it-1]) possible by current programmer.
/// if k < a[it-1] then k - a[it-1] < 0, which is not possible
if (j > 0 && k >= a[it - 1]){
z[i][j][k] += z[i][j - 1][k - a[it - 1]];
/// if you are asking yourself but why are we only subtracting
/// this programmers a[i] for the current instance, then think like this
/// if the current programmer changed the count of (j-1, k-a[i]) in the current
/// instance then that new value should be added here else the value from previous
/// instance should be added. This is because we are making
/// current [j-1][k-a[i]] equal to previous [j-1][k-a[i]]
/// at this line: z[i][j][k] = z[i ^ 1][j][k];
}
/// here we take care of the mod
while(z[i][j][k] >= md)
z[i][j][k] -= md;
}
}
}
int ans = 0;
for(int i = 0; i <= bugs; i++) {
/// now we add all the values for the last programmer's instance
/// Note that stage(bl, i) means that some how we were able to have written all
/// 'bl' lines with bugs = i in total.
/// so [bl][0] means all 'bl' lines were written with no bug in any line. this is only
/// possible if atleast one programmer can write a line of code with 0 error and
/// if he writes all the lines 'bl', then he will never add any error;
/// also we need to add the value of the instance written by the nth (last) programmer
ans += z[n & 1][bl][i];
/// taking care of the mod
while (ans >= md) ans -= md;
}
printf("%d\n", ans);
}
Hopefully this will help some one. Also if someone can write a recursive solution that would be great. Sorry for any grammatical mistakes.
Thanks Ediston
