Sumanto's blog

Interview Question: Dynamic Programming
By Sumanto, 4 years ago, In English

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.

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

Comments Comments (8)
| Write comment?
»
4 years ago, # |
← Rev. 5   Vote: I like it +10 Vote: I do not like it

Question link

Caesar legion original code in O(n*m*k) complexity
modified code in O(n*m) complexity using prefix sum

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

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

    Sample test cases are giving wrong answers in your modified code

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Because modulo is different,also here in your question k1 = k2 = k

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Could you explain the state transitions. I am not getting logic of the for-loop inside the recursive function.

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

      Taking a continuous sequence of i elements of particular type ( 0 for red and 1 for blue or vice versa)

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

    It will lead to time limit exceeded, as your complexity is n*m*k, see my n*m code above.

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

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:

  1. Their length differs by at most 1.
  2. One of them sums up to n, and other sums up to m.

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.

→ Reply