Блог пользователя kit1980

Google CodeJam "Crossing the Road" confusing test case
Автор kit1980, 10 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

something like this?

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    → Ответить