Recently in the div 4 contest (Codeforces Round 964 (Div. 4)), I tried to hack some people's problem E solution, and I find some strange things.
In problem E, the solution should be like this :
1. for all x from 1 to 2e5, precompute the number of operations needed for x to become 0
2. construct a partial sum array to store those information
3. for each query, use O(1) time complexity to answer with partial sum
(you can refer to the editorial for more)
I AC the task with time 109ms with the solution described above.
However, after the contest, I found that there are many people passed this task without using partial sum, instead they just use O(n) time complexity for each query. The time used by these solutions are about 800ms-900ms, which didn't cause TLE.
But why? If we use a test case that all query is 1 200000, the code will loop more than 1e4*2e5=2e9 times, which is not expected to pass, even with the pragma gcc optimize thing.
I have attempted to hack many of those solutions, but only one of it is successful hack.
submission
hack case
The above one is one of the submission that I got an unsuccessful hack. This solution passed the case in 827ms.
submission
The above one is one of the submission that I got an successful hack. (TLE)
Is that the compiler "helped" the author to make a fast range sum query automatically? If not why this happened?
Unfortunately, performing 2e9 operations in 1 second is actually feasible in modern computers, especially when these operations are 'light'. Summing up through an array in order is a very, very light task and it's not easy to hack them.
These ~900 ms solutions probably have almost identical binaries for the summing part, so theoretically they should take almost the same execution time. However, the speed is not very stable and may differ from execution to execution, and that's why you can sometimes hack them and sometimes not. If you attempt like 100 times on each of them it's very likely that they get TLE at least once.