dsanurag520's blog

Python run time error on recursive function
By dsanurag520, history, 10 months ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

learn c++

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is one previous such question: https://mirror.codeforces.com/blog/entry/80158

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

    How do I add @cache decorator after I have added the @bootstrap decorator? It doesnt seem to work.

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

      No idea about bootstrap. Note however that the issue is solvable without it.

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like 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++

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

          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.

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

          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.

          → Reply