Блог пользователя TahsinArafat

Автор TahsinArafat, история, 4 часа назад, По-английски

During Codeforces Round 987 (Div. 2), I got Runtime Error on Test Case 59 (in Problem E. Penchick and Chloe's Trees). It shows Stack Overflow Error! But, the same code got AC on C++17 while upsolving!

  • C++20 Submission: 291655589 — Runtime Error on TC 59
  • C++23 Submission: 291671738 — Runtime Error on TC 61
  • C++17 Submission: 291671684 — AC

But, after a little modification on insider loop, it got AC in C++20: 291668944. But, I couldn't find any valid reason for stack-overflow, and how this submission solved this error!

Can you help me?

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
3 часа назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

It is stack overflow. To compile C++23 solutions, Codeforces uses the following command: g++ -Wall -Wextra -Wconversion -static -DONLINE_JUDGE -Wl,--stack=268435456 -O2 -std=c++23 program.cpp -lstdc++exp -- it gives 256 MiB for stack. But for this program it is not enough. 450 MiB fixes the issue: 291681903. I'd say that on a 32-bit architecture, the pointer consumes less memory, which is why there is enough stack.

  • »
    »
    3 часа назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks!

    But, what's about the modified code I've mentioned in the post? That code got AC on C++20, with no large change in code!

    • »
      »
      »
      3 часа назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      You made mp and perm global, it reduced stack memory consumption.

»
53 минуты назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Test program

It seems G++ 13.2 and 14.2 may preallocate the stack, for the above program, apparently the stack usage should be 128MB (2 calls of dfs, each results 64MB allocation), which conforms G++ 7.3 behavior. But with 13.2 and 14.2, the memory usage is 192MB, which seems it allocates when entering a dfs regardless if the variables are used or not.

Also the size of vector<ll> map<ll, ll> set<ll, greater<ll>> gets doubled in the 64-bit version to 24, 48, 48. Suppose the above preallocation is true, then each call of dfs results 24+48+48+100ish(function call and parameter)=220B, when multiplied 1e6, it's close to 256MB. If add some misc things, that could be an overflow.