ediston's blog

By ediston, 9 years ago, In English

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

  • Vote: I like it
  • +23
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the nice explanation. I had a small doubt in the second approach(the editorial one). I assumed the same dp states with the difference being, the implementation. I.e. I created an array of dp[n+1][m+1][b+1]. Doing the very same thing:

for(i=1;i<=n;i++){
		for(j=0;j<=m;j++){
			for(k=0;k<=b;k++){
				// either this ith programmer writes this line or doesnot
				dp[i][j][k]= dp[i-1][j][k]; // programmer doesnot write
				
				if(j>0 && (k>=bug[i-1]))
				dp[i][j][k]+= dp[i][j-1][k-bug[i-1]];  // programmer writes
				
				dp[i][j][k]%=mod;
			}
		}
	}

Is the above correct? Please, if possible, explain why not?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think there 's any mistake.

    But your solution will get rejected as it takes too much of memory.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, the solution may be rejected due to memory usage, but I just wanted t check my approach: http://ideone.com/PpcGob. It gives wrong answer, can you see and tell where it's wrong?

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The error is at the end,

        you don't have to sum up dp[i][m][j] for i,j.

        All you need is sum of dp[n][m][j], as you're summing the value for prev. person in the dp code itself.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

please give a recursive solution also. bottom up is hard for me. its easier to write bottom up code once u know topdown solution.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    11028522 may help

    it's about the same idea and i don't think that you can reduce the used memory here so you have to code it in a bottom up fashion to reduce the memory (i think it's called "rolling table" as every layer of dp[i][j][k] depends on the previous layer aka dp[i-1][j][k]) if you like this is my AC code after this operation 11035530 (where p is the current layer and !p is the previous one i.e (p stands for i and !p stands for i-1) )

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Spoiler
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the logic behind the solution, I am not able to understand the solution as to how the DP is generating the answer for each programmer. I dont want to understand the code, I want the logic behind it.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    let's imagine there is dp [] [] [] space we will be working on first dimension for the number of programmers used second one for the lines written third one for bugs now let's simplify things if programmer number (i) didn't write any line of code then we can depend this state is dp [i-1] [] [] as the last (i-1) programmers are the one who written the codes now we need the states where our programmer wrote 1 line 2 lines extra we can simply find that in dp [i] [j-1] [k — a[i]] as this also will contain dp [i] [j — 2] [k — 2 * a[i]] and so on and logically that right as in the calculation I calculated the the previous states that I need from the formula in the tutorial what is the need for iterating again on it ?! if you still didn't get it please let me know.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks man, this was really very helpful :)

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I really liked the simplicity and clarity of your solution. Thanks a lot!

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks alot

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

We can also decrease the amount of steps a bit if we sort the weights int a[n] and use j * a[i] as an upper boundary for the interval length of the innermost loop:

for (int j = 0, u = a[i]; j < m; j++, u += a[i])
{
    int s = min(b, u);
    for (int k = a[i]; k <= s; k++)
        dp[j + 1][k] = (dp[j + 1][k] + dp[j][k - a[i]]) % mod;
}

Even the slighest changes in the inner loops overall produce multiplicative effect.

Here is the submission: 12553068

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The further optimisation in the inner loop can help in reducing the time even more:

    dp[j + 1][k] += dp[j][k - a[i]];
    if (dp[j + 1][k] >= mod)
        dp[j + 1][k] -= mod;
    

    Comparison and subtraction are less costly operations than modulo operation — 12574069