So I recently solved this problem and learned a lot. Being not an expert in DP, I struggled to understand the editorial. So I read the comments and found ediston's blog on this problem. Even though I understood his blog, somehow I thought there is a need to complement his writing so here I have a more detailed explanation of the problem.

The most naive approach for this problem.

dp[i][j][k] = ways of using first i programmers to write j lines of code and have k total bugs.

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
		for (int k = 0; k <= b; k++) {
			dp[i][j][k] = dp[i - 1][j][k];
			for (int l = 1; l <= j; l++) {
				if (k - (l * bpp[i - 1]) >= 0) {
					dp[i][j][k] += dp[i - 1][j - l][k- (l * bpp[i - 1])];
				}
			}
			dp[i][j][k] = dp[i][j][k] % MOD;
		}
	}
}

This one will TLE & MLE both. Lets optimize it till it passes the time and memory constraints. To overcome TLE lets modify it to the following code snippet:

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
		for (int k = 0; k <= b; k++) {
			dp[i][j][k] = dp[i - 1][j][k];
			if (k - bpp[i - 1] >= 0) {
				dp[i][j][k] += dp[i][j - 1][k - bpp[i - 1]];
			}
			dp[i][j][k] %= MOD;
		}
	}
}

So in the above snippet, when we iterate for the ith programmer, either he writes 0 lines which correspond to dp[i][j][k] = dp[i — 1][j][k] OR he writes 1 or more lines which correspond to the if statement inside the innermost for loop. This if statement needs more explanation.

Since the ith programmer has already written at least one line of code, we add dp[i][j — 1][k — bpp[i — 1]] (instead of dp[i — 1][j — 1][k — bpp[i — 1]]) to dp[i][j][k]. It's like we have already used 1 to i programmers.

Even though we have optimized the time constraints, we haven't optimized the memory constraints. From the snippet it should be clear that we only need the current 2D array and the previous 2D array, so we can replace dp[n][m][b] with dp[2][m][b] and it should get accepted.

However we can further reduce the memory to just dp[m][b]. And this is precisely the approach explained by ediston in his blog.

Hi friends,

I am solving this problem. Here is my code:

		int n = reader.readInt();
		int k = reader.readInt();
		int[] val = new int[n];
		int c0 = 0;
		int mxv = 0;
		for (int i = 0; i < val.length; i++) {
			val[i] = reader.readInt();
			if (val[i] == 0) {
				c0++;
			}
			if (val[i] > mxv) {
				mxv = val[i];
			}
		}
		int[][] dp = new int[n][k];
		int[] num = new int[mxv + 1];
		int mod = 5000000;
		for (int i = 1; i <= n; i++) {
			dp[i - 1][0] = 1;
		}
		num[0] = c0;
		for (int j = 2; j <= k; j++) {
			for (int i = 2; i <= n; i++) {
				if (val[i - 2] > 0) {
					int tmp = val[i - 2];
					while (tmp < num.length) {
						num[tmp] += dp[i - 2][j - 2];
						if (num[tmp] >= mod) {
							num[tmp] -= mod;
						}
						tmp += (tmp & -tmp);
					}
				}
				int tmp = val[i - 1] - 1;
				int sum = num[0];
				while (tmp > 0) {
					sum += num[tmp];
					if (sum >= mod) {
						sum -= mod;
					}
					tmp -= (tmp & -tmp);
				}
				dp[i - 1][j - 1] = sum;
			}
			Arrays.fill(num, 0);
		}
		int sum = 0;
		for (int i = 1; i <= n; i++) {
			sum += dp[i - 1][k - 1];
			if (sum >= mod) {
				sum -= mod;
			}
		}
		writer.println(sum);

I get wrong answer. Where am I going wrong. Any help will be appreciated.

Hi Guys,

I am trying to understand the editorial for this problem on prefix and suffix. The editorial is not very clear OR maybe it is clear and I am not able to understand it. What is prefix function p of string s ? It will be great if someone can explain the approach with an example.