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

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

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!

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

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

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          Vectors? why? are they not stored on stack?

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

            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 года назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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.