When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

TheNoOneCoder's blog

By TheNoOneCoder, history, 3 years ago, In English

I was doing this problem in python. I am receiving Runtime error on test 3 with exit code -1073741571. I am not able to understand the fault in my code. Any help is greatly appreciated.

Link to my submission .

The main part of the code is below:


cnt = 1 d = defaultdict(lambda:0) travesal = [] subtreesize = defaultdict(lambda:0) def dfs(node,parent): global adj,cnt travesal.append(node) ans = 1 for child in adj[node]: if child==parent: continue d[child]=cnt cnt+=1 ans+=dfs(child,node) subtreesize[node]=ans return ans n,q = li() p = li() adj = [[] for i in range(200002)] for i in range(len(p)): adj[i+1].append(p[i]-1) # print(p[i]-1) adj[p[i]-1].append(i+1) dfs(0,-1) for i in range(len(travesal)): travesal[i]+=1 for i in range(q): u,k = li() u-=1 dis = d[u] x = dis+k-1 # print("x",x) if x>=len(travesal) or subtreesize[u]<k: print(-1) else: print(travesal[x])
  • Vote: I like it
  • +15
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by TheNoOneCoder (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

You are getting stack overflow.

The problem here is that sys.setrecursionlimit(10000) does not directly mean you can actually reach a recursion depth of 10000. CPython and PyPy both internally use the standard stack for recursion, which by default is pretty tiny. C++ would have the same problem too, but it doesn't because of the compile flag --stack=268435456.

So how do you get around this in Python? A while back made this bootstrapper to completely get around any issues with deep recursion. The way it works is kind of weird but it is pretty easy to use. Here is your submission getting AC using it 118526672.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot brother

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Hi pajenegod, can you please tell me how to remove runtime error from my Codejam Round 2 C problem. My code link. My code also uses recursion.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +18 Vote: I do not like it

      Here is how to use the bootstrapper in your case

      def find(l, r, val, inde):
          if l >= r:
              return 1
          x = inde[val][br(inde[val],r) - 1]
          return comb(r-l,x-l) * find(l,x-1,val,inde) * find(x+1,r,val+1,inde) % mod
      

      switch it to

      @bootstrap
      def find(l, r, val, inde):
          if l >= r:
              yield 1
          x = inde[val][br(inde[val],r) - 1]
          yield comb(r-l,x-l) * (yield find(l,x-1,val,inde)) * (yield find(x+1,r,val+1,inde)) % mod
      
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Thanks man, you are a python GOD

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        Dear sir pajenegod,

        I have a question, Which one is faster recursion code vs iterative code(bootstrap on that recursive code)

        I ran two codes in pypy3

        First recursive code: recursive It takes around 0.04 seconds every time I run

        Second iterative code of the same recursive code(using bootstrap): iterative It takes around 0.4 seconds every time I run

        The iterative code using bootstrap is slowing 10 times. So my question is does the bootstrap slow down the code. Or I am making some mistake.

        Also please tell us how to fasten bootstrap. The bootstrap is very fine library for large recursions. So I wanted to know how to optimise it.

        Thank you in advance for spending your precious time.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          The bootstrapper definitely slow things down. I've never suggested that it runs fast compared to native recursion. The role of the bootstrapper is to get around the issue of deep recursion. It also uses far less memory compared to native recursion.

          However, the overhead of using the bootstrapper is still surprisingly small. When I first designed it I thought it was going to be useless because of the overhead. But to my surprise it actually works pretty well.

          There is always going to be a trade off between usability and overhead. If you really want to lower the overhead, you can for example try this:

          Bootstrapper (without decorator)

          Another thing is that if you are ok with even more overhead, then in Python 3 you can do this:

          Bootstrapper (with returns)
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Hi pajenegod can you please tell me how to use bootstrapper in this solution since it does not have a return statement in my recursive function. Thanks in advance.

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              There are a lot of examples in this blog already. You should be able to learn from that. But here is your code bootstrapped 119799338.

              About having no return. The way Python works is that all functions have a return value. If you don't explicitly set a return value, then the function returns None. So to get the same behaviour with the bootstrapper you need to add yield None (or just yield) on the last line in the function.

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
            Rev. 2   Vote: I like it +5 Vote: I do not like it

            Thank you very much for the suggestion.

            I have one more question. I tried to do problem C of today contest using recursion. Using lru_cache it got runtime error due to python stack size as seen submission_runtime_error_stack_overflow

            I also tried to do using bootstrap method as seen here in submission But it got tled. How should I do only using recursion and python?

            Update: It got AC here but it will probably get hacked. Thanks in advance