dannyboy20031204's blog

By dannyboy20031204, history, 2 months ago, In English,

When I was working on two DFS problems(1304E and 1328E),I got RE on both problems using Python3(73088047 and 74608730),but after changing them into C++, they both accepted (73083388 and 74613021). I'm pretty sure the submissions have nothing different exept the programming language, so what's wrong with Python? According to my suspect, the bug is in the DFS functions, because they are Recursive functions. Did anyone faced the same problem or knows how to fix it?

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

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Relevant Stackoverflow thread

The default stack size in Python is really small compared to the input size, so I'm pretty sure the runtime error is about running out of memory to call another function. To resolve it, you can either use the function sys.setrecursionlimit() (I'm not sure if it works with Pypy) or change your DFS function to stack-based instead of recursive.

»
2 months ago, # |
  Vote: I like it +15 Vote: I do not like it

The issue is with Python's recursion stack limit — which is quite low ($$$1000$$$) by default. You can extend it by using

from sys import setrecursionlimit
setrecursionlimit(L) # L is the max depth of your recursion

But this results in RTE, MLE or TLE most of the times (RTE on CF the last time I used it). Bottom line being Python is bad for recursion and switch to C++ for that.

PS: This issue of recursion in Python has been discussed several times earlier on CF. A search with appropriate terms should bring up relevant results. A few of them are this and this.