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

Автор SPyofgame, история, 4 года назад, По-английски

Original Problem

M-candies-problem. In this version, we need to calculate the number of ways to share exact $$$K$$$ candies for all $$$N$$$ children that the $$$ith$$$-child doesnt have more than $$$a_i$$$ candies.

And the constraints are

  • $$$1 \leq N \leq 100$$$
  • $$$0 \leq K \leq 10^5$$$
  • $$$0 \leq a_i \leq K$$$
O(n * k^2) solution - Standard DP
O(n * k) solution - Prefixsum DP
O(n * k) solution - Online algo and space optimization


Extended Version

But what if the constraints were higher, I mean for such $$$M, a_i \leq 10^{18}$$$ limitation ?

O(1) solution for N = 1
O(1) solution for N = 2
O(1) solution for N = 3
O(1) solution for N = 4

Those fully-combinatorics codes above suck and hard to gets a simplified formula. Though I think this problem can be solved for general $$$a_i$$$ and $$$k$$$ in $$$O(n)$$$ or $$$O(n\ polylog\ n)$$$ with combinatorics or/and inclusion-exclusion, but I failed to find such formula.

Can someone give me a hint ?

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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I don't know answer now, but I just wanna say your blog formatting and quality has really improved!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Thank you, it is not related to the blog to say but actually I want to format all my blogs just because I usually write editorials and dont want anyone to get confused and learned nothing after reading.

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

Unless there is some structure in $$$a_i$$$'s it would be surprising to solve the problem in $$$O(poly(N) polylog(K))$$$.