maximus12793's blog

By maximus12793, history, 10 years ago, In English

http://codeforces.me/contest/378/submission/21474186

I have submitted the analogous code in c++ and it worked fine. Is there some reason why this does not work even having set the recursion limit to 20k? I have every time the time and memory is well within limit when it crashes. any ideas?

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

»
10 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it
  1. For a 500 × 500 grid, recursion depth can be as much as 250 000. Isn't it the case here? 20k won't help, then.

  2. To really increase the recursion limit, you may have to start a new thread, see KadiyalaSaiManoj's comment here for an example. Otherwise, you hit an implementation-specific limit which when I last checked was 1Mb on Windows.

  • »
    »
    10 years ago, hide # ^ |
    ← Rev. 5  
    Vote: I like it +10 Vote: I do not like it

    Thank you!

    so surprisingly this did not work for

    sys.setrecursionlimit(250000) threading.stack_size(10240000)

    but for sys.setrecursionlimit(280000) threading.stack_size(102400000)

    it did??? And do you know why it is the case that this sort of stack_size setting / recursion limit mods only work on python2.7 but not for pypy submissions? (I was always under the impression that pypy was better suited for time/memory constraints)

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

      I never used pypy, so can't say.

      As for 250000, perhaps 250000 + ε will be sufficient: 250000 calls of dfs and O(1) calls above and below, like the main function, thread init function, and so on.

      Edit: Ah, and that extra zero in 102400000 sure makes a difference. As a scripting language, Python is quite a memory hog, so I won't expect 250000 recursive calls of anything Pythonic to fit into 10Mb.