Night_Lord's blog

By Night_Lord, history, 2 months ago, In English

Hello,as I am beginner in dp ,I am facing problem with this problem.Anyone help me understand the states and base cases for this problem?

The statement: When monkeys are given some fire-crackers, they have only thing in the mind — to blow things up. Small boxes were easy to blow up, and thus mailboxes became a popular target. Now, a small mailbox manufacturer is interested in how many fire-crackers his new mailbox prototype can withstand without exploding and has hired you to help him. He will provide you with k identical mailbox prototypes each fitting up to m fire-crackers. However, he is not sure of how many fire-crackers he needs to provide you with in order for you to be able to solve his problem, so he asks your help.

The constraints are:

  1. If you blow up a mailbox, you can't use the mailbox again, so if you have only k = 1 mailboxes, you would have to start testing with 1 fire-cracker, then 2 fire-crackers, and so on until it finally exploded. In the worst case, that is if it does not blow up even when filled with m fire-crackers, you would need 1 + 2 + 3 + ... + m = m * (m + 1)/2 fire-crackers.

  2. If a mailbox can withstand x fire-crackers, it can also withstand x-1 fire-crackers.

  3. Upon an explosion, a mailbox is either totally destroyed (blown up) or unharmed, which means that it can be reused in another test explosion.

Now the manufacturer wants you to find the maximum number of fire-crackers that his mailboxes can withstand. Before doing that you have to buy some fire-crackers to test that. So, you need to find the minimum number of fire-crackers you need to buy to test the mailboxes.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Night_Lord (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't this problem similar to Egg-dropping puzzle?