SPyofgame's blog

By SPyofgame, history, 4 years ago, In English

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 ?

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

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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