A.m-E.r's blog

E. Tetrahedron
By A.m-E.r, history, 6 years ago, In English

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 ? :)

Tags #dp
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 15   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you :D

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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,

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yeaa i got it now , sometimes bottom up approach is a must ;) , thank you :D

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply