ttrkaya's blog

Why don't we get stack-overflow at 429/A?
By ttrkaya, history, 9 years ago, In English

I have just solved this great problem: http://mirror.codeforces.com/problemset/problem/429/A

I have solved the problem by using DFS on the given tree, like most others did, and like the editorial suggests.

As I was coding the solution, I was sure that I would get a stack-overflow, and then I would reimplement the solution using BFS. But I did not..

In the problem, it is very possible that the tree is a path (a unary tree where each node has at most one child), and its depth could be 10^5. In fact the test case #2 is a path.

A stack of depth 10^5 should be an overflow right? I have not used any linker settings to increase the stack size.

So what I'm wondering is: is it just a missing test case? Or does codeforces compilers do something special so that we don`t get a stack overflow even at depth 10^5?

I`m wondering this, because lots of times, it is easier to code the recursive DFS solution than iterative BFS solution. If possible I wish not to care about the stack-overflows.

Thank you in advance.

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

»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Default stack size in codeforces is 256MB

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That explains it. Thank you very much :)

    So a typical codeforces problem will have the memory limit of 256MB. It is heap memory right? So in total we have 256MB heap + 256MB stack = 512 MB memory?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      No,we don't.12693743 shows that stack memory also counts. (memory shown:262144KB=256MB,while this program only used 150MB heap memory)

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        nice practical proof! thank you :)

        → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

this post by MikeMirzayanov says that the g++ compile option is g++.exe -static -DONLINE_JUDGE -lm -s -x c++ -Wl,--stack=268435456 -O2 -o {filename}.exe {file} in that,-Wl,--stack=268435456 says that the stack size is 268435456 bytes(=256MB) which is far more than what your program will use. (In worse case, your program will use 100000*3*4=1200000 bytes)

→ Reply