# | User | Rating |
---|---|---|

1 | Radewoosh | 3759 |

2 | orzdevinwang | 3697 |

3 | jiangly | 3662 |

4 | Benq | 3644 |

5 | -0.5 | 3545 |

6 | ecnerwala | 3505 |

7 | tourist | 3486 |

8 | inaFSTream | 3478 |

9 | maroonrk | 3454 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 174 |

2 | awoo | 168 |

3 | nor | 165 |

4 | SecondThread | 163 |

5 | BledDest | 162 |

5 | maroonrk | 162 |

5 | Um_nik | 162 |

8 | -is-this-fft- | 150 |

9 | Geothermal | 146 |

10 | TheScrasse | 143 |

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/08/2023 15:28:21 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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