How to use DP in this question?

In problem Problem - C - Codeforces, we are using DP. I don’t have much knowledge of using DP. So, plz explain in detail what actually has to be done in this question and how are we using DP over here.
Thanks in advance.

Think of the recursive way this manner: there are two cases for every programmer, either he contributes for the current line under consideration or he doesnot. So, the recursive function can go this way:

idx: used for indexing line numbers
m: total number of lines, thus idx<=m
n : total number of programmers
start: indexing programmers, thus start<=n
b: max allowed bugs
bug[]: input bug array
bugcount: sum of bugs for the lines numbered 1 to idx, i.e. for every recursive call, current sum of bugs of each line


int find( int bug[], int bugcount, int start, int n, int idx, int m, int b){
if(idx>=m){  // i.e. we have written all lines of code
	if(bugcount<=b) // required condition
	return 1;
	
	return 0;
}
if(start>=n)  // all programmers taken
return 0;

int p = find(bug, bugcount,start+1,n,idx,m,b);  // programmer numbered "start" doesnot write
int q = find(bug, bugcount +bug[start], start, n, idx+1,m,b); // he writes, so, bugcount changes

return p+q;  // return total possibilities of both the above 

}

Noe because this recursive solution will be too slow, think of the dp states as dp[i][j][k] which denotes i programmers have to write j lines of code where atmost k bugs are allowed.

So, dp[i][j][k]= dp[i-1][j][k] ; // the ith programmer doesnot write
    dp[i][j][k]+= dp[i][j-1][k-bug[i]]; // if he writes this line, the total number of ways are the same as it would have been when j-1 lines were written. Because k bugs are allowed, we need to look at the entry with k-bug[i]].

You can see this 3D DP code here. The memory allocated in this is 500X500X500X4 ~ 500 MB which is much greater than the memory allowed. Hence this solution will give Memory limit exceeded on test case 1 itself(I am allocating memory during compile time and not run time). You can allocate during run time to pass some test cases using this approach. To optimize this 3D DP code, notice, for every iteration, you only need track of (i-1)th iteration. For every programmer, the previous result is itself getting summed up at the current iteration. So, just allocate memory of 2X500X500. (This is very similar to space optimized version of LCS problem if you have done). Refer the submission number 11062816 on codeforces.

This can be further optimized this manner:

Assume two dp states : dp[i][j] which denotes the number of ways j lines of code can be written when i bugs are allowed. Now, think, if we haven’t written line numbered (j-1), we can’t reach line j. However, if we have, we can reach line j.

So, for all programmers,

for(i=0;i<n;i++){
   int allow = bug[i];
   for(int j=bug[i];j<=b;j++)
   {
      for(int k=1;k<=m;k++)
      {
         dp[j][k]+= dp[j-1][k-allow]);
         // do mod here
      }
   }
}

In the end calculate summation of dp[i][m] for all i= [0,b].

PS: There can be some mistake in the above explanation. Feel free to ask and correct.

1 Like

Thanks @damn_me for putting such a nice and detailed explaination, I wasnt able to solve it during contest, and than I asked a few members of codeforces but no one replied :frowning: .
Thanks bro… :smiley:

@deepak2015 “k-bugs[i]” denote that number of bugs that are done will increase by bugs[i] or in other words the number of bugs we can do from this state to any future state will be “k-bugs[i]”.
I hope its clear now, is IT??

Thanks for really nice explanation but I cannot get this statement:

dp[i][j][k]+= dp[i][j-1][k-bug[i]]; // if he writes this line, the total number of ways are the same as it would have been when j-1 lines were written. Because k bugs are allowed, we need to look at the entry with k-bug[i].

Can u plz elaborate what exactly u r trying to say over here.

That means, if i’th programmer contributes to j’th line(which means we are over with writing j-1 lines) and maximum allowed bugs are k, then, (j-1) lines will be having at max (k-bug[i]) bugs.

Hope it clears, if not, you may ask further.