Setter: Taranpreet Singh
Tester: Abhishek Pandey
Editorialist: This person




Dynamic Programming will do the trick.


Given an array B of length K and and an integer N, Find number of ways to partition N into K parts represented by A, such that 0 \leq A[i] \leq B[i] for every 1 \leq i \leq K.


  •   Use DP state (i, sum) representing number of ways to select first i values, such that their sum is sum, and each of them follow constraint imposed by B.
  •   DP transition is represented by checking every combination of sum and value for current partition size, for each position.
  •   Final answer is simply $DP[K][N]$, implying sum of first $K$ partitions having sum $N$.


Quick explanation was all!!!

First assume we have a function f(pos, X) which tells us the number of ways to select values for partition [1, pos] such that their sum is X. Suppose we select 0 \leq y \leq B[pos] as value of (pos)th partition. Now, we need to count number of ways to select values of partitions [1, pos-1] such that their sum if X-y, which is same as f(pos-1, sum-y).

So, This means that we can iterate over every possible value of every partition and calculate result this way, the final answer being f(k, n).

But, Above solution has exponential complexity in worst case, which will not pass main subtask. Dynamic Programming comes to our rescue.

In above solution, we can notice that f is called various times with same arguments, which we can calculate once and for future, we can just look up from there.

Idea is, whenever you compute a result, store it. Whenever you answer a query, check if it isn’t already calculated.

We can also represent DP transition iterative way as

DP[i][sum] += DP[i-1][sum-j] for every 0 \leq j \leq B[i]

This way, every state pair (pos, sum) will be filled, and there can be B[i] iterations for each calculation, resulting in O(N*K*max(B[i]) time complexity, which easily passes the last subtask.

Time complexity: O(N*K*max(B[i]))
Memory Complexity: O(N*K) , can also be reduced to O(S) by noticing that for current position, only previous position values matter.


Setter’s solution
Tester’s solution

Feel free to share your solution or ask any doubts. :slight_smile:

The unusual MOD value of 1e9+9 ate up 15 min of my time :P. Had a hard time figuring out where I went wrong only to realize the MOD value wasn’t 1e9+7. Kudos to the setter for such an innovative mixup of general values

Why is this giving a sigabrt error??

Plz do explain.