M-candies extended problem

Revision en2, by SPyofgame, 2020-11-16 19:41:28

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. I tried to find a better formula but I failed. 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

Can someone give me a hint ?

Tags combinatorics, math

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English SPyofgame 2020-11-18 03:18:16 0 Tiny change: 'rmula.\n\nCan so' -> 'rmula.\n\n\nCan so'
en5 English SPyofgame 2020-11-17 05:24:12 1309
en4 English SPyofgame 2020-11-16 20:10:33 70
en3 English SPyofgame 2020-11-16 19:53:07 87
en2 English SPyofgame 2020-11-16 19:41:28 153
en1 English SPyofgame 2020-11-16 19:38:38 13952 Initial revision (published)