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

×

Codeforces Beta Round Dynamic Programming Problem

Problem Link :link

My code link: link

At every point in dp array I am storing the number of 2's and 5's in prime factorization of optimal product ending at dp[i][j]

I am getting wrong answer in test case 13. Also I know that I have to take care of case when there is at least one 0 in the matrix.For that case I have used flag variable in my code. Can someone please help me with my code. I know it is not easy to understand someone's code but if someone is willing to help me please help.

This question is marked "community wiki".

asked 02 Dec '18, 12:55

pavitra_ag's gravatar image

4★pavitra_ag
696
accept rate: 5%

wikified 02 Dec '18, 21:34


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.

link

answered 04 Dec '18, 12:30

black_truce's gravatar image

5★black_truce
1297
accept rate: 27%

edited 04 Dec '18, 18:11

what conditions should I put in equals case?

(04 Dec '18, 16:15) pavitra_ag4★
1

I've edited the answer.

(04 Dec '18, 18:11) black_truce5★
1

Thanks sire you helped me get AC.

(04 Dec '18, 23:25) pavitra_ag4★
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,719
×2,181
×1,249
×682

question asked: 02 Dec '18, 12:55

question was seen: 182 times

last updated: 04 Dec '18, 23:25