Mario's blog

By Mario, history, 6 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?
»
6 years ago, hide # |
 
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.

»
6 years ago, hide # |
 
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
  • »
    »
    6 years ago, hide # ^ |
     
    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.

    • »
      »
      »
      6 years ago, hide # ^ |
       
      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.