| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Does someone know a special fact about this conjecture that could help to get a complexity lower than O(180*n), which is the one you get using a dp approach, I tried these two codes:
http://ideone.com/XN4td http://ideone.com/cWhNR (tried to use pointers to speed it up)
but both give me TLE.
I've just got AC.
You should use these two ideas to get AC.
Use shouldn't solve the general knapsack problem to get the first answer for the test case. Surprisingly, the Pollock's conjecture will help you to solve this problem efficiently :) Consider the fact, that possible answers are 1,2,3,4,5. So you can just brute-force the answers for 1,2 and 3. Then you can add tetrahedral number for every x that d[x] = 3, thus finding all the y that d[y] = 4. The answer for the remaining numbers is 5.
There are only 45 odd tetrahedral numbers and there are no any conjectures about them. So you should use the most general dp approach.
If you have any more questions about this solution feel free to ask them :)
Thanks, I haven't thought about how to deal with the case of d[y] = 4. Nice!