Superty's blog

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

»
12 years ago, hide # |
← 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
  • »
    »
    12 years ago, hide # ^ |
     
    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