Google CodeJam "Crossing the Road" confusing test case

Question

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" (click "Solve B-small" to get the file).

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"?

Answer 1

The input can be translated into the following timing for the intersections, where NS indicates the time that the pedestrian is allowed to cross north or south, and EW indicates the time that the pedestrian is allowed to cross east or west.

A -- NS:0   EW:1  NS:2     EW:3
B -- NS:0-4 EW:5  NS:6-15  EW:16 NS:17-26
C -- NS:0-9 EW:10 NS:11-20
D -- EW:0-9 NS:10 EW:11-20

It's easy to see how you could end up with a time of 17, if you cross intersection B in the EW direction at time 16. But the key is that you never have to cross B in the EW direction.

Working backwards from a time of 12, the solution must cross intersection B in the NS direction at time 11. From there it's easy to work backwards to the start.