Mario's blog

By Mario, history, 4 years ago, In English

Getting Wrong Answer!! Question — https://cses.fi/problemset/task/1093/ My Solution — https://ideone.com/uwVSBp

  • Vote: I like it
  • -6
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your mod calculation is wrong, you cannot simply divide by 2 in the end.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You cannot divide 2 directly because it is modulo value of answer. So you should take inverse of 2 and then simply multiply with the answer in the end.

Top Down Dp
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As an alternative you can do the whole dp calculations with %(2*mod)

    This works because the factor 2 is fairly small, and 2*mod is still within the bounds of an integer. Then the division by 2 in the end yields the correct result.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      No offense, but this approach seems very risky. I think "properly" multiplying with modinverse(2) should be the only approach suggested.