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

PA 2008 Cliquers [A] solution
Автор ikbal, 11 лет назад, По-английски

statement

Problem is actually asks calculate number of partitons of n.

Is there anyone knows something better then O(n^2) approach?

UPD: Thank you for O(n sqrt(n)) solution fchirica , but i need proof too.

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

»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

I know an O(n * sqrt(n)) approach, but I don't know its proof. I think proving it is difficult, so just take it as magic :)

Let P(n) = number of partitions of n.

Then, P(n) = P(N — 1) + P(N — 2) — P(N — 5) — P(N — 7) + ...

The k-th term of sum in absolute value is P(N — x[k]). The signs of sum's terms alternate from 2 to 2, so they are ++--++--++-- and so on. By x[k] I noted k-th pentagonal number . By formula of pentagonal numbers it's easy to see that when calculating P(n) you add about sqrt(n) numbers (because there are about sqrt(n) pentagonal numbers <= n) so complexity is O(n * sqrt(n)).

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

    Well, proving it is reading the Wikipedia article on pentagonal numbers :D Aside from that, an approach should pass comfortably.

    → Ответить