Блог пользователя Akash_123

Runtime error on python solution for Codeforces Round #627 (Div. 3) F
Автор Akash_123, история, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

How about catching the exception and printing to console?

→ Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить