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 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | adamant | 164 |
| 3 | awoo | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 155 |
| 6 | maroonrk | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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)
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.
Can anyone please explain me why my code: http://ideone.com/xqYiIn gives wrong answer on silver division's "Vacation Planning"?