Execution time assessment

Revision en1, by DonSilvio, 2022-08-04 02:51:35

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.

Tags #timelimit, #asking, #advice

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English DonSilvio 2022-08-04 02:51:35 1423 Initial revision (published)