Superty's blog

O(N^3) running within 3 secs for N = 500? How?
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.

→ Reply
  • »
    »
    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?

    → Reply
    • »
      »
      »
      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.

      → Reply
      • »
        »
        »
        »
        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.

        → Reply