harsh-apcr's blog

By harsh-apcr, history, 8 months ago, In English

Submission : https://mirror.codeforces.com/contest/1878/submission/252116337

I am new to python so I was practicing it on codeforces problems, the submission I referenced above is exceeding memory limits for very small values of $$$n$$$.

I think you don't need to really understand the problem statement, I suspect the problem is in implementation of segment tree. (as the solve() function really only has binary search which is implemented iteratively)

Any help will be appreciated

here is the code :

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

»
8 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

Interesting, it's something with pypy and sys.setrecursionlimit(...). If you make it smaller it will be fine. Though with standart python the memory is fine

Anyways, recursion in python is really bad, so it's better to replace it with a stack. Here you can check out a simple decorator for that

*Actually, you don't even need it because your recursion depth is very small and you can just remove setrecursionlimit

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    thanks, this issue is resolved, but apparently it got TLE

    submission : https://mirror.codeforces.com/contest/1878/submission/252135902

    The same code in C++ would've passed very easily, what I am doing wrong ? Is it due to python lists ? should I be using numpy arrays or is there some other fault

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      I'd say, it is just due to python speed :p

      I could reach TL10 (for example https://mirror.codeforces.com/contest/1878/submission/252137501) but i don't really know what to improve except changing the algo

      Maybe you can look through status page for some solution with the same idea that has passed in python

      For example there are some solves with segment tree from below, but maybe there are with standart too

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    From Differences between PyPy and CPython:

    • sys.setrecursionlimit(n) sets the limit only approximately, by setting the usable stack space to n * 768 bytes. On Linux, depending on the compiler settings, the default of 768KB is enough for about 1400 calls.

    So calling setrecursionlimit means that it tries to allocate enough memory for the call stack to perform recursions of approximately n in depth.