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!
learn c++
Here is one previous such question: https://codeforces.me/blog/entry/80158
How do I add @cache decorator after I have added the @bootstrap decorator? It doesnt seem to work.
No idea about bootstrap. Note however that the issue is solvable without it.
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++
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:
Consider using some other hash, or an ordered map.
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
to
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.
pajenegod Awesome Slove Brother❤️.