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

Автор Jostic11, 6 лет назад, По-русски

Я сделал 2 посылки по задаче которые отличались лишь тем, что в 1 я написал так:

dp[n] = mem(n/2)+y;

dp[n] = min(dp[n], mem(n-1) + x);

http://codeforces.net/contest/710/submission/54830139

а во второй вот так:

dp[n] = min(mem(n/2)+y, mem(n-1)+x);

http://codeforces.net/contest/710/submission/54830177

Это одно и тоже, но записанное по разному и как ни странно первая посылка получила "Ошибка исполнения на тесте 15", а вторая "AC"

С чем такое может быть связано?

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

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

возможно с тем, что порядок выполнения функций разный

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

    вроде тот же порядок.. я же не меняю порядок в функции min

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Порядок вычисления аргументов в функции неопределен в общем виде

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

        не знал этого.. чаще всего это бесполезно, но тут видимо как то на самом деле повлияло на процесс) буду знать

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

Больше предположений: компилятор по разному определяет, как будет распределяться стек памяти в ходе работы. В первом случае происходит явное задание не просто вычисления аргументов для min, но и то, где результат будет при этом храниться.

При этом все же возможно какой-то мини оверхэд памяти, но учитывая, что на макси тесте глубина рекурсии доходит до 5 млн вызовов, это будет очень сильно влиять.

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

    переписал dp нерекурсивно и задача заработала. я думаю это только подтверждает эту теорию, но так и так это забавно когда максимально похожий код из за каких то особенностей компилятора работает по разному