I have a question about this CodeJam problem: Crossing the Road
I implemented dynamic programming solutions and compared results of running my program and first place winner's program on "B-small-practice.in".
My program gives correct answers (the same as first place winner's program) on all 100 test cases except just two: #5 and #6.
Let's look at the case #5:
2 2
1 1 0 10 1 6
10 1 0 1 10 10
There are 4 intersections. My answer is "17". The correct answer is "12". I can't understand how it's possible to get "12"; when I try to do it manually the best I can get is "17". What is the path with cost "12"?
something like this?
Yes, thank you. I wrongly assumed that only up and right moves are needed for the best solution. It's interesting that out of 100 test cases only two needs these "backward" moves.