for context: problem link :link
my solution :link
Got RE in 35th case the python AC submissions for this problem are executed using bfs. I looked at some AC submissions in c++. looks like the logic is same. So the problem I guess is with python.
lets say I avoid recursive implementation and go for iterative ones..for example Bfs over dfs. but is it even possible in all cases? And also if you can provide a feasible way to execute deep recursions without runtime error I will be extremely grateful.
Please don't suggest to learn C++ right now. I know it is a great language. But I just can't afford the time now. I am currently working on learning new skills that will help me in web dev. I hope you understand my position.
Yes, there is a way to use recursions in python without stack overflow. Put below snippet in your code and then put @bootstrap over recursive function. And replace instances of return with yield. (Credit goes to pajenegod)
It was accepted in no time. thank you!! But i also needed do a slight modification. ~~~~~
~~~~~ without the modification yield was stopping the complete process if it was hitting the leaf node. So now it works. But the same modification if i do on a normal recursion the program is giving WA even for smaller values. I think it has to do something with being stackless. I am keeping this here just so that everyone keeps in mind some slight changes may be needed to be done if you use this version. Thanks again though. :) i am gonna use this code from now on.
Yes, you are right you have to use yield for accepting results from recursion call also. You can refer to examples in the below comment.
I'm trying to get this to work but can't seem to, trying to make it work with some very simple recursive functions and I just get errors. The following code gives me
TypeError: unsupported operand type(s) for +: 'generator' and 'generator'on both python 2 and 3:
An even more trivial function that dodges the above error will still error out with
File "main.py", line 18, in wrappedfunc to = stack[-1].send(to):
Is there something obvious I'm missing?
Actually you have to use yield for accepting results from the recursive call as well for returning the value also. It will be more clear from these examples.
Note that tail call optimization doesn't work in Python.
Here is a version of your solution getting Accepted: 86938135
The solution is wrapped into a function.
This function is run in a new thread.
Before that, the stack limit for new threads is updated.
The trick of starting a new thread to control the stack size in the contests is old.
I first saw it used for Java some time around 2010.
Wow that's really simple and clever!!
I am so glad I asked this question here. somehow when I searched it on google all answers were like switch to c++ or set recursion limit. But now when I dig deeper specially in codeforces blogs I found the topic of threading mentioned but very vague. All this blogs were about getting stuck on a specific problem statement. So I did not click on it before.
its sad that even it is an old trick its not very well known as no blog/resource actually exists dedicated to this topic. Thank you so much for answering :)
This code gives Memory limit exceeded in pypy3. You have any trick for pypy3?