You are not logged in. Please login at www.codechef.com to post your questions!

×

Plz help solving Dish Distribution using DP

Dear codemates i am noob in solving DP problems. I tried to solve the above problem but failed. Can anyone explain how it works and the solving strategy.

http://www.codechef.com/OCT11/problems/DISHDIS

thanks in advance

asked 13 Apr '12, 13:41

rijin's gravatar image

2★rijin
15112
accept rate: 0%

edited 25 Apr '12, 23:53

tojochacko's gravatar image

2★tojochacko ♦
560101924

2

did you read the contest editorial for that specific problem ?

(14 Apr '12, 03:36) cyberax ♦2★

yea...but i dnt understand clearly ....thats wat i ask to explain with a specific case

(21 Apr '12, 13:59) rijin2★
1

what specific thing didn't you understand ?

(21 Apr '12, 22:21) cyberax ♦2★

can u explain how it contruct with 1, 3 2 ,0 3 ,1 3

(29 Apr '12, 15:02) rijin2★

This was the Easy problem for this month. The problem is a standard combinatorics problem which asks us to find the number of solutions possible for:

x1 + x2 + x3 + ........ + xm = n with the constraints ai<=xi<=bi

Though the problem can be solved using combinatorics, the constraints and the time limit of the problem allow a simple O(n3) dp solution to pass. The recurrence is straight-forward. Let dp[x][y] denote the number of ways of preparing y dishes by the first x cooks. Clearly, our answer will be dp[m][n]. The recurrence is as follows:

dp[i][j]=?dp[i-1][j-k] where x[i]<=k<=y[i]

A lot of people had a problem passing the time limit with a recursive solution. It's always better to write an iterative code for your solution, especially if the recurrence is simple.

can u exp. this with abv example?

link

answered 15 May '12, 19:08

rijin's gravatar image

2★rijin
15112
accept rate: 0%

Ok I am a beginner in dp as well.Can you illustrate on how you arrived at this recurrence. A little more illustration will help understand.

(23 Jun '12, 19:36) bknarendra1★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,402
×4

question asked: 13 Apr '12, 13:41

question was seen: 1,672 times

last updated: 23 Jun '12, 19:36