Блог пользователя toss

Автор toss, история, 9 лет назад, По-английски

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
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +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.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

This handy table will answer all of your questions. (Reference: Competitive Programming 3)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I coded an O(n^3) solution (Floyd-Warshall) and it was fast enough (296 ms).

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        What is the complexity of my solution then? 2D BFS. Seems like O(N^2 + N^3) to me

        http://codeforces.me/contest/602/submission/14454922

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +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.

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится 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.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    is this for 1 sec or 2 sec?? @maximaxi

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Codeforces works fine with 100M operations for 1 secs, might need some optimization, though.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          because that is 10 billion operations

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 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.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Here is my answer to a similar question. I typically use 4·108 operations per second as a rule of thumb.