w0rth_it's blog

How do problem setters decide the time limit for a question?
By w0rth_it, history, 21 month(s) ago, In English

When I solve any problem, I just look at the constraints and figure out the time complexity the problem allows.

But, out of curiosity, how do problem setters decide how much time limit should be there?

  • Do they consider performances of languages other than C++?
  • How much difference can a time limit of 1 second and 2 seconds make?
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Do they consider performances of languages other than C++?

Depends. It is far more convenient to only consider C/C++ than to implement the very same solutions in other languages and balance the TL. Do note that there are already many (right or wrong) solutions to consider in problems.

How much difference can a time limit of 1 second and 2 seconds make?

A lot. Like, a lot. A TL multiplied $$$2$$$ times the ideal TL could let a $$$O(\frac{n^2}{16})$$$ solution pass when the intended solution is something like $$$O(n\sqrt{n})$$$.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the info.

    But how do they find the TL for the intended solution? How do they decide that the time limit should be exactly 1 second(when there are some people that can solve those questions in 15ms)? By just running it on different test cases?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It depends on the intended solution

      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is all a matter of balancing the input limit and the time limit based on the possible solutions. For example, if the difference between a correct solution and a wrong solution has a very minimal time complexity difference, say, $$$O(n \log n)$$$ and $$$O(n \log^2 n)$$$, then what the problemsetter can do is to increase the maximum value of $$$n$$$ to increase the gap between the two solutions, and then balance the TL to somewhere in between. Same goes for other situations, and you can of course make these changes flexibly to prevent what you want to prevent and allow what you want to allow.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

they go to the future to find the execution time of my solution and then set the time limit so my solution doesn't pass.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

If you experienced enough, you can estimate the time limit just by knowing the solution.

But the most right way — to write a C++ solution. Then you look at your solution time limit and set the time limit to the whole task. Remember, that most commonly time limit should be at least twice as big as author solution time limit.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    There are cases when you can't just estimate the solution's running time. For example, who would even think treaps get only 20 points on some romanian tst problem ? ( with n <= 1e5 )

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In general, ~3 times faster than model solution (assuming model code is optimized fairly well). If you want to cut slower solutions, you can make it tighter, it really depends.

→ Reply