PROBLEM LINK:
Setter: Taranpreet Singh
Tester: Abhishek Pandey
Editorialist: This person
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic Programming will do the trick.
PROBLEM:
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.
SUPER QUICK EXPLANATION
-
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$.
EXPLANATION
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.
Complexity:
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.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Feel free to share your solution or ask any doubts. 