Akash_123's blog

Runtime error on python solution for Codeforces Round #627 (Div. 3) F
By Akash_123, history, 5 years ago, In English

I submitted a Python solution for Codeforces Round #627 (Div. 3) F. I got Runtime Error on test 36. I thought the problem was stack overflow due to recursion limit. So I increased the limit. But that still gives me the same error.

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

The following is a slight update to your code that was accepted, but it is written in C++. 73182681

Hope this helps you in fixing your Python solution.

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

    Sorry, but I cannot find out what you have changed.

    → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How about catching the exception and printing to console?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Messing around with deep recursion in Python means opening a can of worms. The underlying issue is that recursion in Python by design uses a huge amount of memory.

In PyPy depending on what you set the recursion limit to PyPy tries to estimate how much memory it needs to allocate for its internal stack. Problem this time is that its estimate was too low, which is why you got RTE. You could in theory fix this by setting the recursionlimit higher but for this problem setting the limit higher causes MLE.

So how do you do deep recursion in Python without using a ton of memory? One way is to write everything iteratively using your own stack (which is what I usually do). Another way you could do it is to use this decorator I wrote a while back. The decorator abuses coroutines in Python to do recursion without actually doing recursion, see 73202667 (AC).

→ Reply