learner_cf's blog

How to solve following problem using DP ?
By learner_cf, 10 years ago, In English

Problem: We are given N boxes in a row. We have to place minimum balls in boxes such that each M consecutive boxes have at least K balls. Find the number of ways of placing balls in boxes. Given N, M, K. 1<=K<=M<=50 M<=N<=10^9 If N = 3, M = 2, K = 1 Ans : 1 If N = 6, M = 3, K = 2 Ans: 6 What is the state of DP ?

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

Comments Comments (4)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please post the question link ?

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

You can't use dynamic programming. The problem will be solved using matrix exponentiation.

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

are you sure if N = 3, M = 2, K = 1 Ans : 1 ?

all boxes must have at least 1 ball ? you didn't say that !

did you mean each M consecutive boxes or at least one ? ? ? you did not say any thing !

→ Reply