harshhks's blog

dp doubt from SPOJ
By harshhks, 4 years ago, In English

Can anyone please tell me where I am going wrong with this? Whenever my last move is not air, I move to air and when the last move is air, I find the maximum time on performing water or fire move. I am a beginner at dp, so any suggestion would help. Thanks. Question | My submission

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

»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

in line 8, you should write 1 in place of 2 my solution

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

    It shouldn't matter, as long as it is not 0 it will produce the same output for (last!=0). Also, I ran your code , it gives the exact same result as mine but your code got accepted in SPOJ checker but mine didn't. Can anyone explain what is wrong with my code?

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

      Your code is working fine. For each testcase just reassign the DP array to -1. You only assigned it before taking the input . So for a particular H ,A your solve method is peeking into some other (H,A) previously calculated states. That's why your solution got wrong answer .

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

        It did work, thanks a lot. But I still have a doubt, wouldn't the answer from every state (i,j) be the same? I do not understand to reinitialize the dp vector, couldn't I reuse the dp vector from the previous test case and just fill in the empty states, building on top of the states that I have already calculated? Amit_kr31 's solution does the same thing(i.e. builds on previously calculated states) but it got accepted when I tried.

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

          He is assigning all states . See his Implementation carefully and furthermore increase your DP dimension to 3 (ex Dp[2000][2000][2] ) because answer will vary if last is 0 or 1 according to your Implementation. This way you might not need to reassign Dp to -1.

          → Reply