AHHOUSE test case were added after i correctly submitted my code

general
,
1

my code was correctly submitted on 18/07/2017 but later some test cases were added in the question and my code was not submitted after rejudge . my code is https://www.codechef.com/viewsolution/14610262 . Can anyone help me in finding me the error in my code. I have tried many test cases . But it’s giving me correct answer for every test cases i provide it to them. Please help me.!

2

Looking at your code it seems like you have implemented a DP approach to find the solution where the only moves allowed are DOWN or RIGHT. But it’s nowhere mentioned in the problem statement. You can rather go UP, DOWN, LEFT or RIGHT.

For e.g., see the following test case. (For simplicity, consider only the PF matrix)

1
5 5
1 1 1 9 9
9 9 1 9 9
1 1 1 9 9
1 9 9 9 9
1 1 1 1 1

In this case, the correct path is the one consisting of only 1's costing 13. But, your code outputs 17, taking the wrong path.

Correct Path             Your Path
[1] [1] [1]  9   9       [1]  1   1   9   9 
 9   9  [1]  9   9       [9]  9   1   9   9
[1] [2] [1]  9   9       [1]  1   1   9   9
[1]  9   9   9   9       [1]  9   9   9   9
[1] [3] [1] [4] [1]      [1] [5] [1] [6] [1]

Considering each cell as a vertex in a graph, this problem can be solved by using:-

  1. Dijkstra’s Algorithm: Since we want to find the single source shortest path and the edge weights are positive, we can use Dijkstra’s algorithm in this problem. See the following link that explains the same. http://www.geeksforgeeks.org/minimum-cost-path-left-right-bottom-moves-allowed/
  2. Floyd-Warshall Algorithm: Since the number of cell in the grid is small, we can also use Floyd-Warshall algorithm to solve this problem. The only difference in this problem is that the cost now has two attributes - PF and PT. We have to keep the total PF value minimum and break ties with PT values.

You can refer to my solution for the second approach. https://www.codechef.com/viewsolution/14636918

1 Like
3

Amazing… Thanks for this elaborated example and finding my error . I was thinking that by traversing right and down i can find optimal value.But i was wrong. Again Thanks :slight_smile:

1 Like
4

I’m glad that you liked it. However, there is no need of awarding points, by doing this you are losing karma points. You should rather upvote and accept an answer. By this, you will gain karma points and also be grateful to the other person.