You are given N red candies and M blue candies.
Write a program to find the number of arrangements of candies in which not more than K candies of the same color are placed next to each other. Answer is large so use 1e9+7;
1<=T<=10
1<=N,M,K<=1000
input Format:
T
N M K
Sample Input:
1
1 1 1
2 1 1
Sample Output:
2
1
Explainations:
1-> RB, BR
2-> RBR
NOTE: https://ideone.com/A1Cldk i used this way but it lead to Memory Limit Exceeded as expected.
Question link
now if u know the dp you can get rid of k using prefix sum on rows and columns of previous layers to calculate contribution in O(1) time or you can use 2d Fenwick tree to calculate range contribution and update cells in n*m log(n)log(m) total complexity
this would be also a helpful reference
Sample test cases are giving wrong answers in your modified code
Because modulo is different,also here in your question k1 = k2 = k
you are using dp[n][m][k][2] where n, m, k <= 1000 so in worst case dp[1000][1000][1000][2] so memory limit exceeds
actually you don't need k use Dynamic Programming — Memoization Code
Could you explain the state transitions. I am not getting logic of the for-loop inside the recursive function.
Taking a continuous sequence of i elements of particular type ( 0 for red and 1 for blue or vice versa)
It will lead to time limit exceeded, as your complexity is n*m*k, see my n*m code above.
I think it is possible to solve this in O(n^2 + m^2) using combinatorics.
Let A[p] represent ways of p-tuples with each number in range 1 to k, such that they sum up to n.
Let B[p] represent ways of p-tuples with each number in range 1 to k, such that they sum up to m.
Now take two tuples such that:
Now, we can place elements from the two tuples alternatingly to form one required sequence.
So, answer is the sum of (A[i]*B[i-1] + A[i]*B[i+1] + 2*A[i]*B[i]) for all i from 1 to n.
A[p] and B[p] for one particular value of p need O(p) time to calculate if factorials and inverse factorials are pre-calculated.