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.
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.
what conditions should I put in equals case?
I’ve edited the answer.
Thanks sire you helped me get AC.