raja_n's blog

Segementation Fault->TLE?
By raja_n, history, 4 years ago, In English

Hello everyone, I was solving today this graph problem : 598D - Igor In the Museum.

And below are my two submissions which only differs in size of an array, one is giving TLE and one is giving AC. According to me, there should be runtime error in 1st submission as array will go out of bound but how Codeforces is giving tle?

90809524

90816112

Here is the difference-checker screenshot for above two submissions:

Thanks,
spookywooky for the documentation.
Wild_Hamster for such a great way to help.
mallick630 for making it easy at last by amazing explanation.

  • Vote: I like it
  • -8
  • Vote: I do not like it

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

In C/C++ you do not get OutOfBoundException or anything like that. You get undefined behaviour. This basically means that anything can happen, there is no error handler.

https://en.cppreference.com/w/cpp/language/ub

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 7   Vote: I like it 0 Vote: I do not like it

    But in online gnu compiler, there is segmentation fault when I use out of bound index. So, I expected that there will be runtime error on Codeforces also.

    Annotation-2020-08-24-183616.png

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

      The behavior is undefined so C/C++ compiler won't need to inject bound checking instruments everywhere. That's why C/C++ is faster than Java. But the disadvantage is you can't predict what will happen, at all.

      → Reply
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it
Code

The code above should be RE, right? Try to guess why it's TLE.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    Output

    This was the output by running the code on custom test. So, that means q was allocated memory just after a[0], thus making the addresses of q and a[1] same. So q changes to 2000000000, explaining the TLE verdict. Am I right, sir??

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

    I have spent a lot of time thinking about this and this is wrong.

    Basically, the stack grows downward, decreasing in memory address. Your q has a lower memory address than a[0]. When you say a[1], that's a address higher than a[0], even further than q. You need to switch the order for having a chance of this. (I have experimentally checked code assembly and read the theory, this is correct.)

    Why does this work practically then? It doesn't work on my system (though it's to be somewhat expected from UB). I suspect it works because the compiler is reordering memory allocations (for some reason or another).

    → Reply