Блог пользователя Mario

Автор Mario, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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