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://mirror.codeforces.com/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❤️.