AbdulAhadKhan's blog

By AbdulAhadKhan, history, 12 months ago, In English

The problem

Recently I came across an old coding problem which gave me runtime error. I tried looking at the usual:

out of bound memory accesses

variable size overflows

divide by zeroes

uninitialized variables but I couldn't figure out how to AC.

After a lot of grinding, as the title of the blog goes, I realized that my runtime error is due to a stack overflow.

So what happened? What did I figure out? Why should it concern you? Here's an explanation

On Codeforces, compilation command allots approximately 268MB of stack memory, you can check the entire command for C++17 here. This is a very large amount of memory and most of the times no one has to worry about stack overflow errors. On Hackerearth, I don't have any idea of how much stack memory is available through their compilation command.

But, a very common problem can take place almost anywhere (if you are not careful): Say, you have a recursive function that calculates an answer which you print. If you pass a lot of parameters to it, it may so happen that stack memory may run out. We know that in C++, int, char, long long variables are stored on stack, a vector declared as:

vector<int> v;

will store the variable v in stack but its contents will be in heap. The recursive function parameters are all in stack memory thus it may run out of space, giving a runtime error (stack overflow in this case)

Conclusion

Make sure you don't pass variables unnecessarily (or at least try to minimize) your function parameters. We usually take it for granted here on Codeforces as we get so much of it through its specific compilation command.

Thank you for reading my blog post, I'll try finding a few problems and submissions where you see this behaviour happening. Will update you when I do...

Full text and comments »

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