Python :- Exit code is -1073741571

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
37:13:24
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

View all →

→ Find user

→ Recent actions

Detailed →

TheNoOneCoder's blog

Python :- Exit code is -1073741571

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])

#python, #pypy3, #runtime, *1600, #help

TheNoOneCoder
3 years ago
11

Comments (11)

Write comment?

TheNoOneCoder

3 years ago, # |

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

→ Reply

pajenegod

3 years ago, # |

+22

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.

→ Reply

TheNoOneCoder

3 years ago, # ^ |

Thanks a lot brother

→ Reply

notTehlka

3 years ago, # ^ |

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.

→ Reply

pajenegod

3 years ago, # ^ |

← Rev. 2 →

+18

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

→ Reply

notTehlka

3 years ago, # ^ |

Thanks man, you are a python GOD

→ Reply

HETRAKESHFADIA

3 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

pajenegod

3 years ago, # ^ |

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)

from types import GeneratorType

def bootstrap(to, stack=[]):
    while True:
        if type(to) is GeneratorType:
            stack.append(to)
            to = next(to)
        else:
            stack.pop()
            if not stack:
                break
            to = stack[-1].send(to)
    return to

def fun(n):
    if n == 0:
        yield
    yield fun(n-1)
    yield

for i in range(10000):
    bootstrap(fun(400))

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

Bootstrapper (with returns)

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = stack.append(f(*args, **kwargs))
            while True:
                try:
                    to = stack.append(stack[-1].send(to))
                except StopIteration as e:
                    stack.pop()
                    to = e.value
                    if not stack:
                        break
            return to
 
    return wrappedfunc
 
@bootstrap
def fun(n):
    if n == 0:
        return 1
    return (yield fun(n-1)) + 1
 
for i in range(10000):
    fun(400)

→ Reply

vermakunal088

3 years ago, # ^ |

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.

→ Reply

pajenegod

3 years ago, # ^ |

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.

→ Reply

HETRAKESHFADIA

3 years ago, # ^ |

← Rev. 2 →

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

→ Reply