Leggasick's blog

By Leggasick, history, 7 weeks ago, In English

I have tried it using both adjacency matrix and dictionary but both are giving run time error on TC 3.Can anyone tell me what the problem in the code? (https://codeforces.com/contest/1534/submission/119406032)

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

For a case with n = 400000, odds are pretty good there's at least one cycle that runs deeper than python's default stack limits (~1000 calls deep?).

Also in this case, since the dfs pursues a singular path, there isn't a lot gained from using recursion rather than an ordinary loop.

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

    for n = 400000 also the recursion will atmost ~400000 calls deep.The same code is running in C++ but don't know why showing run time error in python

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

      You can write/generate your own testcase(s) with as big a cycle in it as you want to test with.

      I'm guessing your phrasing of 'at most' is in reference to trying to change python's default limits to accommodate deep recursion.

      Unfortunately, sys.setrecursionlimit is only part of it, there is also the issue of actual stack space and the fact that python's function calls are relatively heavy (compared to C at least) and there isn't a compilation step (for stuff like tail recursion optimizations), soooo even if you get it to work, it's gonna chew up memory.

      The search on this site isn't great, but you can use an external search engine and specify where to look e.g. "python recursion site:codeforces.com" works on google if you really want to dig into the rabbit hole (or look up bootstrap recursion).

      On a practical level, choose your pain point. As an old, python is still a win for me, personally. If I begin to accumulate massive amounts of pre-baked code, I suspect this all would be a bit less fun for me, but also, the tradeoff would likely swing back towards lower-level compiled languages (with arguably better support). Happy hunting!

»
7 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

tf is this language try c++ or c