Tiko's blog

Usaco December 2013 Bronze
By Tiko, 10 years ago, In English

In second problem of bronze division (Cow Baseball), solutions with O(n^3) have passed all the test, but limit of n is 1000. I checked it in ideone and it gives 0.94 sec. How is this possible? Here is link to my ideone attempt http://ideone.com/l7rezw

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it's because there's only an if and a "++", and the optimizations flags of the compiler (-O3) that makes the code run faster. Theoretically O(n^3) will spend much more than 1s when n is 1000. (I'm not completely sure about this, maybe someone can explain it better)

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

it's not very strange, we only have C(n,3) triples but C(1000,3) is about 166 millions which is not too much for USACO processors specially the O(N^3) codes have few constant operartions. this code even got AC in 254ms.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain me why my code: http://ideone.com/xqYiIn gives wrong answer on silver division's "Vacation Planning"?

→ Reply