dvdg6566's blog

About Constant Time TLE
By dvdg6566, 4 years ago, In English

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.

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

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

Auto comment: topic has been updated by dvdg6566 (previous revision, new revision, compare).

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

Auto comment: topic has been updated by dvdg6566 (previous revision, new revision, compare).

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

Auto comment: topic has been updated by dvdg6566 (previous revision, new revision, compare).

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

Honestly, I don't think that's an issue. Isn't correct and efficient implementation part of solving the task? You may claim that it's unfair, because many people with brilliant ideas are limited by their knowledge of programming, but in the end of the day it is competitive programming. Ability to optimize the code and squeeze it into the time limit is valuable skill that should be rewarded. Otherwise we shouldn't call it "competitive programming", but "algorithmic problem solving" or something like that.

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

    Well, your idea of correct and efficient implementation of worse time complexity goes a lot beyond letting an extra log pass. If you give register instructions directly, you can optimise the code a lot more. Well, given your views, I would recommend learning these to get more efficient implementation 96187495.

    Well, this would inevitably be the meta for competitive programming if we thought the best code is the one which works fastest on our measly small data.

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

    I think we should call it algorithmic problem solving.

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

      I agree. I think algorithmic problem solving is another name for the same thing (especially since the class I took on cp was called that).

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

      And I did called like that for 7 years

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

    In my opinion, penalizing for small minute optimisations is a bit much (personal opinion only)

    However, maybe it would be more fair to say tell you your runtime if it's slightly above the TL? Like if the TL is 2s and your code runs in <2.5s maybe it could give you your runtimes? Just a suggestion.

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

This should not be a problem. Sure, there could be many solutions to a single problem. That is not a problem. It shows diversity through the submissions. Imagine a problem in which no other approach is AC. That would be horrible. You are good in some areas and worse in others. Let there be multiple solutions to a problem. I think that it is fine.

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

    Multiple solutions is fine, but I think sometimes a slower and less elegant solution may be a problem.

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

Honestly, I'd prefer a world in which problemsetters just don't try to fail $$$O(N \log N)$$$ solutions when the intended complexity is $$$O(N)$$$. Especially when languages other than C++ get involved, it seems overwhelmingly rare for the slowest $$$O(N)$$$ solution to be faster than the fastest $$$O(N \log N)$$$ solution until $$$N$$$ gets very large, at which point I/O bottlenecks start to become a risk. Additionally, it's often unclear whether $$$O(N \log N)$$$ is meant to pass, and even worse, it's frequently difficult to construct the strongest possible tests to fail slower solutions, which means that $$$O(N \log N)$$$ solutions typically either FST or just get AC due to weak tests. This problem is a perfect example: among the $$$O(N \log N)$$$ solutions, some FSTed, some passed due to weak tests, and few failed pretests.

Turning an $$$O(N \log N)$$$ solution into an $$$O(N)$$$ one is often a very interesting theoretical exercise, but it's just extremely difficult to determine whether a solution runs in $$$O(N)$$$ using an online judge. Because of that, I think the vast majority of such problems aren't suitable for CF, and if they are used, $$$O(N \log N)$$$ solutions ought to be admitted.

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

    I think for some it could really be quite sad, you think of such an elegant linear time solution and then someone uses say, segment tree beats.

    But I agree with you that yes its very unfair if there are things like FST and AC with weak tests for complexities that may or may not get AC.

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

I have a random idea for OI-style contests. I was thinking that for subtasks with tight time limits, problem setters can impose partial scoring by time. For example, if the problem has a time limit of 1 second, then solutions that run between 1 second and 2.5 seconds can get a partial score for that subtask based on how fast their solution is. This will also help people know if their solution is close to getting AC and is worth optimizing or if they should just give up and find a faster approach.

This could also be used to tiebreak scores, but tiebreaking by who has the better constant time optimizations (or worse, based on random luck because of judge inconsistencies) seems abit questionable to me.

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

    I think Polish Olympiads in Informatics used do this (maybe it still does?). You'd get full score on a subtask if it runs entirely in the time limit, and the score decreases linearly down to 0 points at 2x of the time limit. Seems like a decent compromise.

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +47 Vote: I do not like it

This is the rule I use:

  • Implement the intended solution(s), which contains the clearest manifestation of your idea: Here, you should try to avoid constant optimization ideas that you use in contests. You also don't have to follow the usual pitfalls that increase the constant factors, either.
  • Implement suboptimal solutions that you want to fail. Here, try to constant optimize as much as possible.
  • Set TL as 5 * (running time of intended solution).
  • If suboptimal solutions still pass, try to increase both input size and the TL.
  • If suboptimal solutions still pass, reduce the constant, but not less than 3.
  • If suboptimal solutions still pass, your "optimal algorithm" sucks. Accept the harsh reality.

I don't think this rule should be taken very strictly, but to break it there should be a strong reason.

I think the biggest issue with tight TL is that it may render model solutions incorrect. Usually people just set the time limit by running some handmade random tests in polygon and calculate, but if time limits are very strict, counterexamples are frequently discovered that make model solutions TL on possible tests. While it's usually not hard to prove asymptotic, that doesn't means you formally proved that the solution works in TL. Proving that seems very hard and also meaningless, so we should just give it lenient as possible to prevent creating unsolvable problems.

That being said, I don't see any real problem for failing solutions because of non-asymptotic reasons, or accepting solutions that have worse complexity. The rule of the algorithm contest is to pass the tests in the given time limit. If the complexity doesn't correspond to actual execution time, then it just shows the weakness of asymptotic analysis in the specific case, not else. We shouldn't confuse the means with results.

Constant optimizations are usually not interesting, but that's more like a matter of taste. Sometimes you have to learn things you don't like. (But they are not in my taste, so I usually try to stay away from them)

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

    I feel like one possible argument against this could be the age-old argument of O(NlogN) against O(NrtN). Since O(NlogN) solutions may require segment trees, sets, or other data structures, they could have significantly high constant factor, despite possibly being a very elegant solution. On the other hand, an O(NrtN) solution could prune or have mainly for loops and be much faster.

    Do you still think it should be considered that 'If suboptimal solutions still pass, your "optimal algorithm" sucks. Accept the harsh reality.'

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

      Exactly. Whatever good theoretic properties it may have, it just doesn't work that well — well enough to claim it's better than other ones. And algorithmic problem solving works with real-life machines. That's all.

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

    recently saw a problem with $$$1 <= Tests <= 100,000$$$ and $$$1 <= K, N <= 5 * 10^6$$$ with a 0.5second time limit. Real deadly. Clearly didn't want to allow any solutions to pass except the intended.

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

      lol, IOI had a subtask with T=2000 N=100,000 into 1 second

      → Reply