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.

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 :) )

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 distributingjcandies among the firstipeople. Now, say you are trying to calculatedp[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 thei'th person (in fact, deciding what to do with thei'th person is often the decision that must be made when your dp state deals with "something among the firstipeople"). So, say you want to give thei'th personkcandies, wherekis somewhere between 0 andmin(a_{i},j) (we can't give them more thana_{i}candies because of the problem constraint, and can't give them more thanjcandies because we only havejcandies). Then, we see that if we givekcandies to personi, then the number of ways to do that isdp[i- 1][j-k] (because we precisely want to find the number of ways to distributej-kcandies to the firsti- 1 people). If we sum up these numbers over all thekfrom 0 tomin(a_{i},j), then we should get the count fordp[i][j].You'll notice, though, that this results in

O(NK) states andO(K) operations per state, orO(NK^{2}) 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 inO(1). Can you think of what to do? Hint: all of the local decisions for a givendp[i][j] recurse into a contiguous block in thedp[i- 1] row.Is it possible to implement it in a topdown manner ?

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.

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 :)

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?

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 :)

Really great explanation! Thank you!

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.

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.

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.

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.

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.

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

alsoWA.My bad! You are absolutely right.

I made a shitty assumption while going through proof.

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

hey, does anyone have recursive solution for this problem ?