### dsanurag520's blog

By dsanurag520, history, 2 months ago,

I am fairly new to codeforces. I wrote a recursive dp using python but I got a run time error on the 9th test case when the input is big. I am not able to figure out the error

For context, problem : problem my solution : solution

I even set recursion limit to 100000, but it doesnt seem to get rid of the error. Any help would be appreciated!

• 0

 » 2 months ago, # |   0 learn c++
 » 2 months ago, # |   0 Here is one previous such question: https://codeforces.com/blog/entry/80158
•  » » 2 months ago, # ^ |   0 How do I add @cache decorator after I have added the @bootstrap decorator? It doesnt seem to work.
•  » » » 2 months ago, # ^ |   0 No idea about bootstrap. Note however that the issue is solvable without it.
•  » » » » 2 months ago, # ^ |   +8 yeah I realised I can solve the problem without using dp However I did try memoization and python gave me TLE (using bootstrap) — python The same solution written in c++ passed — c++
•  » » » » » 2 months ago, # ^ |   0 Looks like the number of states for memoization is $n \cdot 2 \cdot 2 \cdot 2$, where $n$ is up to $10^5$. Well, that's $800\,000$ states, which are not fast to put into a map, even with a compiled language, as you can see.Note: the hash you use in the C++ submission is bad. It literally gives the same result for quadruples of inputs: $(x, 0, 0, 0)$, $(x, 0, 1, 1)$, $(x, 1, 0, 1)$, $(x, 1, 1, 0)$ have the same hash, $(x, 0, 0, 1)$, $(x, 0, 1, 0)$, $(x, 1, 0, 0)$, $(x, 1, 1, 1)$ have the same hash. Consider using some other hash, or an ordered map.
•  » » » » » 2 months ago, # ^ |   0 I tested running your code with @bootstrap in GYM. It takes 2.6 s / 2.0 s. So your solution is just slightly too slow.Btw there is a simple trick here to get around recursion (and bootstrap) in its entirety. By switching print(dp(0,False,False,False)) to for i in range(days)[::-1]: dp(i,False,False,False) print(dp(0,False,False,False)) you have essentially a bottom-up DP solution. Note that any recursive call done will be stored in the cache. Using this trick, your code gets AC in 1.2 s / 2.0 s 247814957.
•  » » » » » » 2 months ago, # ^ |   0 pajenegod Awesome Slove Brother❤️.