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?
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.
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
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.
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.
The code above should be RE, right? Try to guess why it's TLE.
... 0x1054febc 0x1054febc 2000000000 1999999999 1999999998 1999999997 1999999996 1999999995 1999999994 1999999993 1999999992 1999999991 1999999990 1999999989 1999999988 1999999987 1999999986 1999999985 1999999984 1999999983 1999999982 1999...
Invocation failed [TIME_LIMIT_EXCEEDED]
===== Used: 15000 ms, 3628 KB
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??
Thanks,
spookywooky for the documentation.
Wild_Hamster for such a great way to help.
mallick630 for making it easy at last by amazing explanation.
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).