siddv's blog

By siddv, history, 10 years ago, In English

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.

Tags dp
  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?