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

Usaco December 2013 Bronze
Автор Tiko, 11 лет назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

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

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)

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить