# | User | Rating |
---|---|---|

1 | tourist | 3509 |

2 | OO0OOO00O0OOO0O0…O | 3327 |

3 | Syloviaely | 3274 |

4 | Um_nik | 3237 |

5 | Petr | 3161 |

6 | fjzzq2002 | 3137 |

7 | LHiC | 3135 |

8 | Benq | 3130 |

9 | ko_osaga | 3115 |

10 | Swistakk | 3089 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 185 |

2 | rng_58 | 161 |

3 | tourist | 158 |

4 | Petr | 152 |

5 | Swistakk | 150 |

5 | Vovuh | 150 |

7 | Um_nik | 147 |

7 | PikMike | 147 |

9 | csacademy | 146 |

10 | Errichto | 145 |

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/25/2018 01:13:44 (d3).

Desktop version, switch to mobile version.

User lists

Name |
---|

Dear AmEr_Tinsley,

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

Thank you :D

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,

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

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

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.

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.