When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

hars123's blog

By hars123, history, 5 years ago, In English

I am finding it difficult to find the relation for transition from one state to another. i.e. if dp[i][j] represents no of ways of distributing j candies among positions [1,i]. Can someone explain what should i think to find that transition. Or i am just unable to observe the pattern.

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

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

Your dp state is correct, to do the transition in O(1) time you need to do the dp calculation iteratively and after you finish for some i, you need to make prefix sums in order to calculate the sum in range [l,r] for i-1 in constant time (O(1) ).

Here is how to implement it:

  • First set the base states, dp[0][0]=1 and dp[0][1...k]=0,

  • Iterate over i from 1 to n and do the following:

  • Make an array of size k and calculate prefix sums of dp[i-1][0...k],

  • Now for every j from 0 to k, you can calculate in O(1) the number of ways to get to state dp[i][j],

  • This is done by finding the sum of dp[i-1][max(0,j-a[i])...j] using the prefix sums.

Here is my implementation of the problem if you need it. (I added comments to the code so you can understand it better :) )

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

In general, DP problems can often be thought of as a decision making process, where you make some "local" decision and your state after that local decision becomes some state you have previously calculated the answer for. So, when you are on a given state, you try all the local decisions you can, and take the one that results in the best answer (or in this case, sum up the number for each local decision to get the total count for the current state).

Your dp state characterization is correct: dp[i][j] represents the number of ways of distributing j candies among the first i people. Now, say you are trying to calculate dp[i][j]. What is the "local decision" that you must make at this state? It will just be how many candies you want to give to the i'th person (in fact, deciding what to do with the i'th person is often the decision that must be made when your dp state deals with "something among the first i people"). So, say you want to give the i'th person k candies, where k is somewhere between 0 and min(ai, j) (we can't give them more than ai candies because of the problem constraint, and can't give them more than j candies because we only have j candies). Then, we see that if we give k candies to person i, then the number of ways to do that is dp[i - 1][j - k] (because we precisely want to find the number of ways to distribute j - k candies to the first i - 1 people). If we sum up these numbers over all the k from 0 to min(ai, j), then we should get the count for dp[i][j].

You'll notice, though, that this results in O(NK) states and O(K) operations per state, or O(NK2) runtime, which is too slow. There is something about the state transitions that allows you to calculate the sum over all the different local decisions much faster, in fact in O(1). Can you think of what to do? Hint: all of the local decisions for a given dp[i][j] recurse into a contiguous block in the dp[i - 1] row.

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

    Is it possible to implement it in a topdown manner ?

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

      I think it technically is, if you keep track of which states you've computed and calculate the prefix sum once you've gotten all of them... but it seems super complicated. Just do bottom up. If you don't usually do bottom up, good; this is a great opportunity to learn, since both top-down and bottom-up are useful to know.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Thank you very much for that detailed description. I would give 10 upvotes if I could. Using words instead of math makes my brain function better :)

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

    Just a quick question. When you see a problem and know its dp. What are your steps to coming up with the solution? I have a lot of trouble with bottom up but am very good at top down dp.

    For me, 1. Establish the state(pretty easy) 2. Establish transition(very difficult for me.. any tips?) 3. Establish base case(easy as well)

    I usually have to draw out the table on paper and try to see if I can find any patterns for the transition. How would you recommend going about finding transitions?

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

      So I think those three steps are pretty good; as for the transition, this is where the "local decisions" come into play. If, at a given state, you can break the problem down into making one of multiple choices (often times it's something as simple as "use this element or don't use this element", like in knapsack), then you look at what states you'll end up with in the case of each one of your choices.

      Also, as you get to more difficult DP problems, establishing the state starts becoming much harder. For example, for this problem, once you get the state down, the transition is pretty simple, but the state is pretty hard to come up with. In my mind, this is the toughest part :)

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

    Here, how do we decide for the base case?

    as in what should be the values for dp[i][j] when either of i or j are zero ?

    i figured, that dp[0][0] is 1, coz there is one way of giving 0 coins to 0 children. There will be 0 ways of giving 1 coin to 0 children. Right?

    I am new to dp too. so I am thinking my way through.

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

      Yup, so there should be 1 way of giving 0 coins to 0 children as you said, and 0 ways of giving $$$i > 0$$$ coins to 0 children. You don't need a separate base case for the case of $$$j = 0$$$, since that state should have a transition from dp[i-1][0] anyway.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks, chief. I just marveled at this explanation for a long time, as perfect as they come.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I have a non-dp solution to the problem. Here it is:

Imagine that you have no constraints at first. What would that mean? The problem can be viewed as a variation of statement "There are k distinguishable urns and n in-distinguishable candies. Find the number of ways to put candies in urns." The answer is $$$(n+k-1)C(n)$$$.

Ofc, we have over-counted.

Now, consider the constraints. Subtract all the possibilities that gives $$$a_i + 1$$$ candies to $$$ith$$$ child.

My intermediate solution is bit time consuming but I think, it can be easily optimized.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    The problem with this is that you will be double subtracting as well. For example, suppose $$$n=2$$$ and $$$a_1=3$$$, $$$a_2=2$$$, and say the number of candies to distribute is $$$7$$$, you will be subtracting the case of distributing candies [4, 3] twice, among others. This would require some inclusion exclusion to fix, and its not clear how that would be implemented here.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it -8 Vote: I do not like it

      No that would not happen.

      I have submitted solution with this logic at atcoder, it gave me 8 test cases correct and in rest of them (total 16 test cases) it gave me TLE.

      The example you provided is an invalid test case (The answer would be 0).

      However with a valid example, $$$sum(a_i) >= k$$$. We can do some simple algebraic maipulations and convince ourselves that multiple subtraction would not happen.

      Your code here...
       #include<iostream>
      #include<cmath>
      #include<unordered_map>
      #include<math.h>
      #include<vector>
      #include<queue>
      #include<set>
      #include<algorithm>
      #include<iomanip>
      #include<string>
      #include<map>
      #define PI 3.14159265
      #define mod 998244353  
      #define mod1 1000000007  
      using namespace std;
      
      // A Dynamic Programming based solution to compute nCr % p 
      
      
      // Returns nCr % p 
      int nCrModp(long long n, long long r, long long p) 
      { 
      	// Optimization for the cases when r is large 
      	if (r > n - r) 
      		r = n - r; 
      
      	// The array C is going to store last row of 
      	// pascal triangle at the end. And last entry 
      	// of last row is nCr 
      	long long C[r + 1] = {0}; 
      	  
      
      	C[0] = 1; // Top row of Pascal Triangle 
      
      	// One by constructs remaining rows of Pascal 
      	// Triangle from top to bottom 
      	for (int i = 1; i <= n; i++) { 
      
      		// Fill entries of current row using previous 
      		// row values 
      		for (int j = min((long long)(i), r); j > 0; j--) 
      
      			// nCj = (n-1)Cj + (n-1)C(j-1); 
      			C[j] = (C[j] + C[j - 1]) % p; 
      	} 
      	return C[r]; 
      } 
      
      
      void func(){
          long long n , k ;
          cin >> n >> k ;
          //k is the total chocos and n is total no. of student.
           
          long long ans =  nCrModp((n + k - 1) , k , mod1) , arr[n];
          //cout << ans << " ";
          for(int i = 0 ; i < n ; ++i){
              cin >> arr[i];
          }
          long long sum = 0;
          for(int i = 0 ; i < n; ++i){
             // cout << (n + k - 1 - arr[i]) << " " << k - arr[i] << "\n";
              if(arr[i] == k){
                  continue;
              }
              else
               sum += nCrModp((n + k - 2 - arr[i]) , k - 1 - arr[i] , mod1);
          }
      
         
          cout << (ans - sum) % mod1 << "\n";
      }   
      
      int main(){
      int t = 1 , cnt = 0 ;
      //cin >> t;
      
      while(t--){  
          func();
      }
      }
      
      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        My initial example was bad, but your logic is still incorrect and does double subtract; I'm not sure what algebraic manipulations you used to convince yourself that this wouldn't happen. I ran your code on the case $$$n=3, k=25, a_1=a_2=a_3=10$$$. My code output $$$21$$$, and yours output $$$-9$$$.

        Word of note: just because your code TLE'd doesn't mean it wouldn't also WA.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          My bad! You are absolutely right.

          I made a shitty assumption while going through proof.

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

My solution Done via bottom-up approach by calculating prefix sums for 1 less number of persons present.

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

hey, does anyone have recursive solution for this problem ?