Superty's blog

By Superty, 10 years ago, In English

My solution 8329406 to the problem 295B - Greg and Graph is O(N^3), but it runs within 3 seconds? How is it possible? N is 500.

  • Vote: I like it
  • -23
  • Vote: I do not like it

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

The code you shared took 1090 ms (i.e. almost 1 second) and got Accepted. It didn't take 3 seconds. 500^3 = 1.25*10^8.

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

    I meant less than 3 seconds. Actually time shown is twice of actual time so it takes half a second.

    How does 1.25*10^8 work in half a second?

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

      Nothing special, Codeforces servers can do sometimes about 4 * 108 operations per second.

      • »
        »
        »
        »
        10 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Hm... okay, I read somewhere it is 10^7. Thanks.