l-.-l's blog

HELP with an UVa problem

By l-.-l, 14 years ago, In English

Hello, I was trying to solve the problem http://uva.onlinejudge.org/external/109/10913.html but i think that it has a mistake in the problem description, in according to the rules: - You can move left, right and down - You can step at most K times, and you can not step one cell more than once

For the first case:

n = 4, k = 1
  1    2    3  -5
-10    6    0  -1
-10  -10  -10   2
  0    0    0   1

I think that you can go for the next path: (1,1) -> (1,2) -> (1,3) -> (2,3) -> (2,2) -> (4,2) -> (4,3) -> (4,4) right right down left step_down right right

Getting as a maximum sum path : 1 + 2 + 3 + 0 + 6 + 0 + 0 + 1 = 13 But the sample output is 11.

Please, tell me if i am wrong, i do not sure that i understood the problem because to get 11 as output you can not go left :s

Thanks in advance.

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

»
14 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

You can't get from (2, 2) to (4, 2).

→ Reply
  • »
    »
    14 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +20 Vote: I do not like it

    → Reply
    • »
      »
      »
      14 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      So, what is the correct path??? And what does "at most K steps" mean? Does it mean "you can have at most k negative numbers in your path"?

      Thanks

      → Reply
      • »
        »
        »
        »
        14 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        You go 1, 2, 6, 0, -1, 2, 1. The sum is 11. How did you get (2,2) -> (4,2)?

        → Reply
        • »
          »
          »
          »
          »
          14 years ago, hide # ^ |
           
          Vote: I like it +3 Vote: I do not like it

          I was so wrong, I did not understand the problem, great mistake, before reading this problem, I was reading another one where you could jump, (go over some cells) and I confused some things with this problem. I am sorry.

          → Reply