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

×

Help required in Simple DP problem

Problem Link http://www.codechef.com/problems/COUPON

Can anyone help me with this solution http://www.codechef.com/viewsolution/6986215 First tell what should I do to get 60 points and then 100 points.

I have got 20 points in this solution. I thought I would get TLE in rest of subtask but its giving WA. Can anyone tell me in which case I am getting WA

asked 20 May '15, 20:32

ankurverma1994's gravatar image

4★ankurverma1994
415114
accept rate: 8%

converted to question 20 May '15, 20:43


Your dp equation needs to be modified. You wrote dp[j][k] = dp[j - 1][k] + min(disc, min). I assume dp[j][k] denotes the total cost of j items with last item bought in the kth house. Then min(disc, min) is wrong. It should be only disc. And it it not necessary that he always gets a discount. It is also possible that dp[j][k] = dp[j - 1][h] + price[j][k] where h is anything from 1 to m.

So your final dp equation should be


dp[j][k] = min(dp[j - 1][k] + disc, val + price[j][k]) where val = min of all (dp[j - 1][h]) for h in range (1, m)

link

answered 21 May '15, 10:23

loch_ish's gravatar image

2★loch_ish
27
accept rate: 20%

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:

×2,212
×1,191

question asked: 20 May '15, 20:32

question was seen: 668 times

last updated: 21 May '15, 15:18