MarioYC's blog

TJU 3787 — Pollock's conjecture
By MarioYC, 12 years ago, In English

Link

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.

Tags math, dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thanks, I haven't thought about how to deal with the case of d[y] = 4. Nice!

    → Reply