harshalpamecha3's blog

By harshalpamecha3, history, 4 months 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

»
4 months 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 months 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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks

  • »
    »
    4 months 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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why 2*mod? Would you please tell me the logic behind this?

    • »
      »
      »
      4 months 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.