ankitbisla21's blog

Doubt on an array bound
By ankitbisla21, history, 9 years ago, In English

Today while I was solving a problem based on dfs, I found something unusual and I am still in doubt, how did that happen!

Problem Link : http://codeforces.com/problemset/problem/463/D

My AC Solution : http://codeforces.com/contest/463/submission/13773175

Problem Faced : In my solution, I have used an array a[1123][10] to take input but in the second test case provided by judge, n = 66 and k = 4 , so my program is going to access some memory location at a[3][65] which is certainly out of bound! That's why I wonder, how my solution got AC?

Positive suggestions are welcome :)

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

Comments Comments (5)
| Write comment?
»
9 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Undefined behavior is undefined. Anything can hapen including your solution being accepted.

Most likely program accessed the same memory as a[9][5].

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

try this

#include <bits/stdc++.h>
using namespace std;
int a[10][10];
int main(){
    for (int i = 0; i < 100; ++i)a[0][i] = i;
    for (int i = 0; i < 10; ++i)
        for (int j = 0; j < 10; ++j)
            cout << a[i][j] << endl;
}
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's working fine! but why? can you suggest some reason?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +14 Vote: I do not like it

      That is how typical memory layout for multidimensional arrays work.

      A two dimensional array a[20][10] can be implemented as one dimensional array a[200]. When you need to access element a[i][j] in two dimensional array you access a[i*10+j] in 1D. C++ compilers usually don't check array bounds, it assumes that all the required checks are performed by programmer. In your sample 3 * 10 + 65 = 95 = 9 * 10 + 5

      Even though it might work that way in some situations, accessing beyond array limits is undefined behavior and compiler is allowed to do whatever it wants. Here is an example:

      void fun() {
   int l[2][5]={{1,2,3,4,5},{6, 0, 0, 0, 0}};
   int i = 0;
   while (l[0][i] > 0) {
     if (i > 4) printf("abcd");
     i++;
   }
   printf("%d %d\n", i, l[0][i]);
}

      What do you think the program will print. Following the logic above it should print "abcd6 0". Here is what I got at different optimization levels, your results may vary depending on compiler. As i said compiler is allowed to do whatever it wants.

      • -O0 "abcd6 0" Compiler did all the things written in code and it behaved as explained above.

      • -O1 "5 0" abcd disappeared and now it prints 5 0 instead of 6 0. Compiler figured out that l[1] isn't accesed so it only fills l[0] part.

      • -O2 "5 0" The same output as -O1 but if you look at disassembled code you can notice that if (i > 4) printf("abcd"); part is in -O1 but not -O2. Compiler figured out that when i>4 program would have to access l[0][5] which is out of bounds, that would be an error so it assumes that i>4 will never be reached and the line can be removed from code.

      • -O3 "4 5" Now the compiler doesn't even allocate memory for array l or perform the loop, it simply prints "4 5". Not sure why "4 5", but it is invalid program, so compiler can do whatever it wants.

      When compiled with GCC 5.1 and -fsanitize=undefined flag at runtime it prints a.cpp:8:17: runtime error: index 5 out of bounds for type 'int [5]' a.cpp:12:31: runtime error: index 6 out of bounds for type 'int [5]'

      You can play with different compiler versions, flags and see the generated code here. It has color coded lines so even people who don't understand assembler code can get some kind of idea what compiler is doing.

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

        Thank You! That's an answer what one expects, a detailed and clear one. Thanks again for such a wonderful answer as well as for the link provided :)

        → Reply