×

# Codeforces Beta Round Dynamic Programming Problem

 2 Your code won't work in this test case. 1 20 100 50 1 5 1 100 1 Your answer: 2 RDRD Multiplication = 100. 2 Zeroes Correct answer: 1 DRRD Multiplication = 250. 1 Zero In your code, when you check min(x2,x5) and min(y2,y5) and compare these both, you miss one case. Which is, when they are equal. Here Your path for Array[1][1] would be RDR (Goes into else case in your code). You calculated, // 0 Based dp[1][1].p2 = 2 and dp[1][1].p5 = 1. But There is also one case where, dp[1][1].p2 = 1 and dp[1][1].p5 = 2. So we have another 5 in the path so in case 1 (p5 = 2, p2 = 2), zeroes = 2. But if we take the second one (p5 = 3,p2 = 1) zeroes = 1. So if you ignore the second case you'll get WA in some test cases. Now that you know your problem, it'd be easy to continue. Just add one equal case that's it. // EDIT Now we need to think if its possible to add an equal case without exceeding the time limit. You need to keep your p2 and p5 as integer vectors and not a single integer. So let's take a simple equal case. Here we have one pair of value from the left and one from the above, then we need to store both the pair of values at that position as we might not know which one of the case would bring us the optimum answer (As we see in the above example). Similarly, if we have n,m pairs from above and left respectively, then we need to store n+m pairs (Also neglect repeated pairs) at that position. Also, we need to backtrace a particular pair (best pair) at the end, to get the path. For backtracking, you need to start from the last and subtract the pair(Answer pair) by the pair at that position. Now to check if the remaining pair matches with any of the above pair or left pairs. And repeat the process. You can use Map for each of the dp[i][j]. Even if you manage to do all these, it'll not pass under that time. Interestingly you don't have to do any of these. Let's say our final answer pair would be p2,p5. Now, if this pair is selected which means there is no other pair p2x,p5x whose minimum is less than the minimum of p2,p5. In other words min(p2,p5) < min(Any pair). You need to use this property. Just calculate the path for minimum 2 and minimum 5 independently. Now we have 2 paths. One of minimum 2s and of 5s. So whichever is minimum from these two, is the answer. answered 04 Dec '18, 12:30 127●6 accept rate: 27% what conditions should I put in equals case? (04 Dec '18, 16:15) 1 I've edited the answer. (04 Dec '18, 18:11) 1 Thanks sire you helped me get AC. (04 Dec '18, 23:25)
 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,698
×2,085
×1,211
×655

question asked: 02 Dec '18, 12:55

question was seen: 158 times

last updated: 04 Dec '18, 23:25