SAKT's blog

By SAKT, 11 years ago, In English

Hi everyone.
In Codeforces Round 212 (Div. 2), I saw one of my room codes and he was using the -1 position of an array (A[-1]). And it did'nt get Runtime Error.
Why? Unfortunately, I had 2 Unsuccessful hacking attempts because of this.
Here is the submission: 5102143 and here is the link of problem: 362B - Petya and Staircases
In the line 22:
if (dirty[0] == 1 || dirty[m-1] == n)
...
and if you put m = 0 ... .
Could anyone answer why this code is Accepted?

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

»
11 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

It depends on compiler. Most compiler doesn't check the exceeded using of array and they take a[-1] as a[len-1].For example, if array a consists 3000 elements. then a[-1] == a[2999], you can check it out on your own computer. I think most compiler does that. For more details, search it in the internet. If something I said is wrong, please tell me, I'm also ignorant about the deeper reasons. :D

  • »
    »
    11 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Sorry, I check it out on Codeblocks IDE on my windows computer. What I said is wrong. I print the address of a[-1] and a[0], they are close. a[-1] takes the place right before a[0] in the cache.(which means a[-1] != a[len — 1], What I said is terribly wrong, sorry for that.) So I think the reason why the code doesn't cause a RE is that maybe compiler doesn't check if you use an invalid array elements, and in the most of time cache a[-1] isn't used.

    Happily to learn something new. :D. Thank you.

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

      yes, in particular, a[k] means *(a + k) where a is pointer of beginning of the array, so a[-1] is 1 cell before the beginning of array...but I still don't know why this cell is 0, because I tried a[-6] in custom test and it wasn't 0!

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

        I think this is codeforces fault.

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

      Actually, it doesn't depend on the compiler, it is something about running the program. Okay maybe you are right and the cache a[-1] isn't used but codeforces shouldn't let the code to use cache and any other place on the memory except the place that is for program, I think you agree with me that in this situation he must got Runtime Error.