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?
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
vectorand other STL data structures.This handy table will answer all of your questions. (Reference:
Competitive Programming 3)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?
I coded an O(n^3) solution (Floyd-Warshall) and it was fast enough (296 ms).
What is the complexity of my solution then? 2D BFS. Seems like O(N^2 + N^3) to me
http://mirror.codeforces.com/contest/602/submission/14454922
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.
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.
is this for 1 sec or 2 sec?? @maximaxi
Codeforces works fine with 100M operations for 1 secs, might need some optimization, though.
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.
because that is 10 billion operations
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.
Here is my answer to a similar question. I typically use 4·108 operations per second as a rule of thumb.