Milil's blog

Execution time assessment
By Milil, history, 2 years ago, In English

Hey guys.

I'd like to ask for an opinion of those experienced in solving difficult problems (rating 1900+) — how do you figure out if the solution you came up with will fit into the time limits set by the author of the problem? When I was in school, I was basically taught to assume that 10^6 operations is equal to 1 second of execution time. But later I found out that this is not always the case, particularly with super-fast data structures like bitset. Also, with the evolvement of computers, they now compute faster and some of the problems that earlier had a 2-second time limit, now usually have their TLs set to 1 second. I specifically ask for the opinion of those who have some degree of experience in solving rather difficult problems (for me this difficulty threshold is approximately problem D in Div. 2 rounds (B for Div. 1)) because recently I have been reading some editorials for the problems I haven't managed to solve and to my surprise found out that I discarded the correct approach because I thought it wouldn't fit into the TL and this often has to do with harder problems (almost never with simple ones). For the problems even harder, I sometimes come across their editorials and they frequently go like "you may think that it won't run fast enough but it will, since [blank]" which leaves we curious.

Appreciate all of the useful information you can provide.

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

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

The number that I have been taught is $$$10^8$$$, not $$$10^6$$$. The steps I use is still primitive: calculate the time complexity, plug in the numner, then compare to $$$10^8$$$.

But for a lot of times, the number pf operations should be calculated differently based on how the code is written. Your example is bitset, which usually have a factor of $$$1/64$$$ faster. Other example like when you jave a nested loops like this:

for i = 1 to n
  for j = i + 1 to n
    for k = j + 1 to n
      for l  = k + 1 to n

Then this has a factor of $$$1/24$$$. The tight bound for this is $$$\binom{n}{4} = \frac{n(n-1)(n-2)(n-3)}{4!}$$$.

Sometimes you need to calculate the complexity with amotized complexity, like when using stack for monotune chain algorithm.

To summarize, the way to calculate the complexity for my algorithm has evolved (as well as the way I came up with such algorithm is different) compared to the past me.

To answer your original question thl, using the constraints of the problem is the first pointer to derive the time complexity.

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

    So how do you evaluate a constant factor for a specific method/data structure?

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

      Ok, sorry for mislead this. No, usually I don't. But I always consider to calculate them if the it does give benefit. Though I don't recommend doing this for learning. In order to improve, you should come up with an algorithm with time complexity that is comfortable to pass the TL.

      There are people actually get up set when the intended solution is to use the constant factor. Imo it's felt cheap to do such kind of optimization. But it is still an approach.

      When I do ICPC with my teams, when idea with constant factor came up, we have learnt to measure the run time first with huge random input before submitting, and that is the thing should be done with such situation.

      But for your question, lots of algo/DS that I used are standard, and they have standard time complexity, so you should memorize that. Or even better, understand how they work to understand the time complexity.

      → Reply