×

# Help required in Simple DP problem

 0 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 415●1●14 accept rate: 8%

 1 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) answered 21 May '15, 10:23 2★loch_ish 27 accept rate: 20%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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