Блог пользователя A.m-E.r

E. Tetrahedron
Автор A.m-E.r, история, 6 лет назад, По-английски

Hello guys,

So recently i was solving this simple DP problem and i was confused when i got an MLE using a memoization table memo[1e7+1][2] however some other codes got Accepted using the same memory as mine .

here is my code , can anyone explain please ? :)

Теги #dp
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

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

Dear A.m-E.r,

It seems that the MLE error is not due to the size of the global two-dimensional array, as the program has already passed 12 tests.

The more plausible reason is that with n = 10,000,000, the maximum value for n, the program exceeded the stack size limit due to the large number of recursive calls.

Please keep in mind that each function call allocates a new stack frame in the program memory space. The size of the stack frame should be large enough to at store all the local variables declared inside the function, the arguments passed by value, and the present processor register values that the function changes their contents. Optimizing compilers often use Abstract interpretation at compile time to compute the minimal size for the stack frame of each function.

Best wishes

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

    Thank you :D

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

      With pleasure.

      The following is an iterative O(n) version of your algorithm.

      35538919

      The simple idea used to transform the recursive algorithm to an iterative algorithm is to reverse the direction of changing the variable (i), i.e. decrement (i) instead of increment it, provided that the final case dp[n][0] = 1 and dp[n][1] = 0 is known.

      Only two variables are sufficient to compute the final value dp[0][0], instead of reserving a two-dimensional array, as dp[i][0] and dp[i][1] are computed in terms of dp[i+1][0] and dp[i+1][1], and are used only once in the subsequent iteration of the loop.

      Best wishes,

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

Here is a nice video solution of this problem by rachitiitr. Hope it helps.

→ Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

With n <= 1e7, you shouldn't use memoization top-down. This can make you overflow due to many recursive calls.

Instead you should build bottom-up, f[i][j] is the number of ways to get j after i steps, so f[i][j] = sigma f[i-1][k] with k != j.

P/s: If n <= 1e9, you can solve this problem using matrix multiplication.

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

By the way, it's good to test such solutions at CUSTOM TEST here on Codeforces to see the amount of memory the solution uses since the biggest input in this problem is simple and not hard to be written by ourselves counter to most of the graph problems input, for example.

→ Ответить