Moody_in_a_hoodie's blog

By Moody_in_a_hoodie, history, 4 weeks ago, In English,

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.

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please add the URL as a clickable link. This way: link

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Moody_in_a_hoodie (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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)

Spoiler
  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It was accepted in no time. thank you!! But i also needed do a slight modification. ~~~~~

    def dfs(node,m):
        visited[node]=1
        if a[node-1]==1:
            m=m+1
        else:
            m=0
        if m>k:
            yield 0
        for v in g[node]:
            if visited[v]!=1:
                yield dfs(v,m) #it was just dfs(v,m) before
        if node in leaf:
            leaf[node]=1
        yield 1
    

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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:

    fibonacci recursive function

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

    trivial recursive function

    Is there something obvious I'm missing?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      Example 1
      Example 2
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Note that tail call optimization doesn't work in Python.

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

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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