kit1980's blog

Google CodeJam "Crossing the Road" confusing test case
By kit1980, 10 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

something like this?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    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.

    → Reply