Picture this: Your algorithm is the correct complexity, but the verdict is TLE. You make some constant time optimizations and AC, or worse, only get an AC after contest. I think the issue of constant time TLE is something many people have faced.
Where does this stem from? The main issue surrounding this is scam solutions. Problemsetters hope that only intended, or similar to intended solutions get an AC verdict. Sometimes, it can be difficult to differentiate between highly-optimized slow code (say NlogN) and unoptimised fast code (say O(N)).
I've personally faced this issue in a big way 3 times. Twice as a problemsetter, once as a contestant. I thought I should share about some of my experiences:
Contestant: IOI 2020, biscuits, 77 points subtask My situation: I had managed to optimize from O(200,000Qlog(10^18)) to O(200,000Q), I was highly expecting to get the points. TLE. I reasoned that recursion is slow, and recoded it iteratively. Still TLE. Finally, I gave up and coded STL queue with 2 pointers on an array. Finally an AC, which ended up deciding my medal colour. Why is such a high-stakes contest down to who listened during a lecture about C++ STL being slow?
Problemsetter: Codeforces Raif Round 1, problem E Fruit Sequences
Our situation: Intended solution is O(N), but fast O(NlogN) implementations with array-based segment trees still got AC. In the end, we allowed the segment trees to AC.
Problemsetter: Problem called collaboration for school contest
Problem: Find the number of pairs of nodes in a tree distance K apart in O(N)
Solution: O(NlogN) centroid decomposition, O(N) set merging
What we did: We set N=3,000,000 and TL as 6s. This only worked because the contest only had C++ submissions, and centroid decomposition could not pass the limit.
Ending thoughts: Is there any way we could help mitigate this issue? As someone who almost had an IOI silver changed into a bronze because of this, I can't help but feel that someone somewhere should try to find a solution.
Personally, I feel that Atcoder's idea of template libraries may make sense. Another thought is banning GCC pragmas and similar optimisations to make it harder to optimise slow code? Honestly, I have no clue. Willing to hear anyone's thoughts and experiences on this.