ikbal's blog

PA 2008 Cliquers [A] solution
By ikbal, 11 years ago, In English

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.

  • Vote: I like it
  • +8
  • Vote: I do not like it

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

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply