chubakueno's blog

Getting WA on test 13 of Gym problem
By chubakueno, history, 10 years ago, In English

Problem A of Gym is giving me a lot of trouble. I have reviewed my code multiple times and after several Wrong Answers I can't see the mistake. Any help is appreciated :) My submission

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You did offset to avoid negative weights, but you actually don't avoid wmax > 802.

For example, in test

10000 500
1 1 100
1 1 100
...
// p[i] = 1, w[i] = 1, d[i] = 100 for all items

You will have in process states with wmax = 500 + 300 + 99 and 500 + 300 + 99 * 2, but your dp has sizes 10002 x 802 x 3. It is not good because you have line in your code:

if(dp[pos][wmax][left] >= 0) return dp[pos][wmax][left];

So you need to change second dimension of dp to m + 2 * 300 or something about it.

P.S. Actually, this code with increasing of second dp dimension gives TL, because check

if(dp[pos][wmax][left] >= 0) return dp[pos][wmax][left];

doesn't return "-INF" results and process "-INF" states every time. You need to change this code to:

if(dp[pos][wmax][left] != -1) return dp[pos][wmax][left];

to process only "-1" states.

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

    Understood! Thank you very much, accepted now :) I will have more care with these "weird jumping" DP excercises the next time.

    → Reply