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 0 Vote: I do not like it

    How? I put everything in a try block and tried to print the Exception, but it didnt print it.

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

    https://codeforces.me/contest/1324/submission/73183628

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

      The best I could do was to make the RTE become WA. But the WA output looks strange though. I think the next best thing would be to generate large random test to stress test your solution.

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

        His code gets AC if you just get around Python's horrible built in recursion 73202667.

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

          Shall I use this decorator whenever I want to do recursion with python?

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

            You could, but it is kinda slow. Better (if you want to continue using Python) is probably to learn how to write recursion iteratively. Or just switch to C++.

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

              Can you send some good link on how to write recursion iteratively?

              → 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