### toss's blog

By toss, history, 8 years ago,

Today I completed my second competition (#333) and an important question regarding time limits arose. I solved the B problem in O(n) time and after locking the problem, I saw that a participant in my room solved it in O(n^2) time. Consequently, I wanted to hack his solution based on the given time limit, but I wasn't sure if my challenge would succeed.

So my question is how do you generally estimate if your/someone else's solution would fit the time constraint? I am aware that constants get dropped in big-O, but I am looking for some general rules. For this example, the aforementioned user would perform at least n*(n+1)/2 operations in worst case with n being at most 100 000 and time limit of 2 seconds. Was it reasonable to attempt to hack his solution and what is your approach with regard to the time limit?

• +6

| Write comment?
 » 8 years ago, # |   +3 I just ran a few tests and found that the CF judging servers can do 2.45 * 10 ** 9 integer operations + updates and 1.225 * 10 ** 9 integer comparisons in 1 second (with GNU C++11).Just multiply the number of operations in a loop by the amount of times it loops and try to estimate using that. You might also want to test the speed of vector and other STL data structures.
 » 8 years ago, # | ← Rev. 2 →   +4 This handy table will answer all of your questions. (Reference: Competitive Programming 3)
•  » » 8 years ago, # ^ |   0 Wasn't it that in yesterdays Div1A problem with n <= 400 the O(n^3) solution failed and O(E + V) solution was the right one?
•  » » » 8 years ago, # ^ |   0 I coded an O(n^3) solution (Floyd-Warshall) and it was fast enough (296 ms).
•  » » » » 8 years ago, # ^ |   0 What is the complexity of my solution then? 2D BFS. Seems like O(N^2 + N^3) to mehttp://codeforces.com/contest/602/submission/14454922
•  » » » » » 8 years ago, # ^ |   +5 I'm not sure about the time complexity of your code, but constant factors are important, too. Floyd-Warshall is an efficient algorithm because it only contains three simple loops. Most O(n^3) algorithms are more complex and slower.In addition, Java is slower than C++ and LinkedList is slower than ArrayList.
•  » » » » » » 8 years ago, # ^ |   0 Used ArrayDeque instead of LinkedList — TLE on the same test. Yeah, maybe the constants are the problem.. But I really doubt it, as timelimit is usually 3-5 times higher than needed just to fit these constants.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 is this for 1 sec or 2 sec?? @maximaxi
•  » » » 5 years ago, # ^ |   0 Codeforces works fine with 100M operations for 1 secs, might need some optimization, though.
•  » » » » 5 years ago, # ^ |   0 But i dont get it .... sometimes in codeforces a problem where n=10^5 .. 2 sec limit ... can not pass O(n^2)..or am i wrong?.. the whole whole solution may contain other O(n) operations, like : getting n input with a for loop etc.
•  » » » » » 5 years ago, # ^ |   0 because that is 10 billion operations
•  » » » » » 5 years ago, # ^ |   0 It is not so different whether it is one second or two seconds. Since the time complexity ignores constant coefficients, the difference in constant times in the time limit is merely an error in most cases.
 » 8 years ago, # | ← Rev. 2 →   +2 Here is my answer to a similar question. I typically use 4·108 operations per second as a rule of thumb.
 » 4 months ago, # |   0 Can anyone know why do ee get cp limit exceeded while submitting a code?