Akash_123's blog

By Akash_123, history, 5 months 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

»
5 months 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.

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

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

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

How about catching the exception and printing to console?

  • »
    »
    5 months 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.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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.

        • »
          »
          »
          »
          »
          5 months 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?

          • »
            »
            »
            »
            »
            »
            5 months 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++.

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

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

»
5 months 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).

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I am facing an issue while calling a function more than 10^4 times i am getting a runtime error. If i run this code on my computer it is working fine but on online compilers like ideone it is giving RTE. Same goes for Hackerrank. It is a simple code but I can't find any mistake. Here is the link of the code. https://ideone.com/CnjbJj