py_cpp_js's blog

By py_cpp_js, history, 4 years ago, In English

Greetings codeforces community! hope you all are doing well :)

So I was solving this problem and I stumbled upon quite a peculiar bug, here are two of my submissions : submission 1 and submission 2, the first one gives RE while the second one passes all test cases.

The only difference between the two is that I declared an array named dp inside main function in the first one where as in the second one it was declared in global scope. I don't really get how this makes any difference in the solution, it would be nice if someone could shed some light on this. Thanks!

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

array defined globally gets the default value of zero and array defined locally gets a garbage value. maybe this is the problem somewhere in array defined in main the default values gets used.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The address sanitizer tells me there is a stack overflow on this line:

ll dp[2 * 100001 + 1][(1 << 8)];

The array was probably to big for the stack. Putting static before it fixes it. I think putting static before it is equivalent to making it a global variable, but I'm not sure. Using vector also works.

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

    I think size of the array is the problem.

    Array locally can store 1e7 elements and globally 1e8, looking at the array size it looks likes it is 1e8.

    can anyone clear this thing??

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      It's called a stack overflow. Local variables are stored on a stack, which has a limited size usually of a few megabytes. Global variables aren't stored on the stack so they don't have this restriction. There could also be other issues with the OP's code that could cause the difference.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Stack size is increased on Codeforces. See the command line parameters here: https://codeforces.com/blog/entry/79

        So it should not have caused the problem. However it's possible that there is a bug in the judging command and the stack argument is used as is (256 MB) instead of setting it as per the memory limit in the problem, in which case stack can only grow to 256 MB, where these submissions are using >400 MB.

        Anyway, good thing I never use arrays, only vectors.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Vectors? why? are they not stored on stack?

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +18 Vote: I do not like it

            No, the elements of a vector are heap-allocated. While the vector itself is an automatic variable and is allocated on the stack, the constructor allocates memory for elements on the heap. Then when the vector goes out of scope, the destructor frees the heap memory.

            So you have a data structure which you can use as if it's allocated on the stack, without worrying about stack size limitations. It is, however a bit slower than arrays — but you should never face an issue on Codeforces. C++ is extremely fast, and time limits are set for slower languages.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I am aware that local variables are stored on stack and global on heap, but as pointed out by swapnilr, codeforces has increased stack size (equal to the limit on question), so I don't think that's the case, moreover this is the first time I have encoutered this issue on cf while I have used large arrays as local variables before. Anyway, thanks for your time.