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
Lets $$$DP[i][j] =$$$ number of ways to share first $$$[i]$$$ children with $$$[j]$$$ used candies
Base case $$$(DP[0][0] = 1)$$$ and $$$(DP[0][x] = 0\ \forall\ x > 0)$$$ and ($$$DP[p][x] = 0\ \forall\ x < 0$$$)
At state $$$[i][j]$$$, you can share to the $$$[i]$$$ child $$$(0 \leq x \leq a_i)$$$ candies with $$$(DP[i - 1][j - x])$$$ ways to share
So we have $$$DP[i][j] = \underset{x = 0..a_i}{Sigma}(DP[i - 1][j - x])$$$
And the answer is $$$DP[n][k]$$$
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
void quickadd(int &res, int val) { if ((res += val) >= MOD) res -= MOD; }
int main()
{
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= k; ++j)
for (int t = max(0, j - a[i]); t <= j; ++t)
quickadd(dp[i][j], dp[i - 1][t]);
cout << dp[n][k];
return 0;
}
O(n * k) solution - Prefixsum DP
Lets $$$F[i][j] = \underset{x = 0..a_i}{Sigma}(DP[i - 1][j - x])$$$$
From the above base case, we also have $$$(F[0][0] = 1)$$$ and $$$(F[x][0] = 1)$$$ and $$$(F[0][x] = 0)$$$ $$$\ \forall\ x \in \mathbb{N}^*$$$
From the above formula, we also have $$$F[i][j] = F[i][j - 1] + F[i - 1][j] - F[i - 1][j - a_i - 1]$$$
From the above answer, we also have $$$F[n][k]$$$
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
void quickadd(int &res, int val) { if ((res += val) >= MOD) res -= MOD; }
void quicksub(int &res, int val) { if ((res -= val) < 0 ) res += MOD; }
int main()
{
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i)
{
dp[i][0] = 1;
for (int j = 1; j <= k; ++j)
{
dp[i][j] = dp[i][j - 1];
quickadd(dp[i][j], dp[i - 1][j]);
if (j > a[i]) quicksub(dp[i][j], dp[i - 1][j - a[i] - 1]);
}
}
cout << dp[n][k];
return 0;
}
O(n * k) solution - Online algo and space optimization
To compress to 1D array, notice that the current array is build from the previous array, we already having the path $$$F[i][x] = F[i - 1][x]\ \forall\ 0 \leq x \leq k$$$
First we subtract the $$$F[j - a_i - 1]$$$ path $$$\ \forall\ a_i < j \leq k$$$
Then we keep the prefixsum with $$$F[j] += F[j - 1]$$$
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
void quickadd(int &res, int val) { if ((res += val) >= MOD) res -= MOD; }
void quicksub(int &res, int val) { if ((res -= val) < 0 ) res += MOD; }
int main()
{
int n, k;
cin >> n >> k;
vector<int> f(k + 1, 0);
f[0] = 1;
for (int i = 0; i < n; ++i)
{
int x;
cin >> x;
for (int j = k; j >= x + 1; --j) quicksub(f[j], f[j - 1 - x]);
for (int j = 1; j <= k ; ++j) quickadd(f[j], f[j - 1]);
}
cout << f[k];
return 0;
}
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
/// If (x < k) then there is no way to share candies
/// Else there are exact (k - x + 1) ways to share
int solve1(ll x, ll k)
{
return max(0LL, k - x + 1) % MOD;
}
O(1) solution for N = 2
/// max(A.get) = x
/// max(B.get) = y
/// max(A.get + B.get) = k
/// * Take max(x) = min(x, k)
/// * Take min(x) = max(0, k - y) = k - min(y, k)
int solve2(ll x, ll y, ll k)
{
return solve1(k - min(y, k), min(x, k));
}
O(1) solution for N = 3
/// Sigma(i = 1..n) (1)
int f1(ll n)
{
return n % MOD;
}
/// Sigma(i = 1..n) f1(i)
int f2(ll n)
{
int t = abs(n) % 2;
if (t == 0) return 1LL * f1(n + 1) * f1((n + 0) / 2) % MOD;
if (t == 1) return 1LL * f1(n + 0) * f1((n + 1) / 2) % MOD;
}
/// Sigma(i = 1..n) f2(i)
int f3(ll n)
{
int t = abs(n) % 6;
if (t == 0) return 1LL * f1((n + 0) / 6) * f1((n + 1) / 1) % MOD * f1((n + 2) / 1) % MOD;
if (t == 5) return 1LL * f1((n + 0) / 1) * f1((n + 1) / 6) % MOD * f1((n + 2) / 1) % MOD;
if (t == 4) return 1LL * f1((n + 0) / 1) * f1((n + 1) / 1) % MOD * f1((n + 2) / 6) % MOD;
if (t == 3) return 1LL * f1((n + 0) / 3) * f1((n + 1) / 2) % MOD * f1((n + 2) / 1) % MOD;
if (t == 2) return 1LL * f1((n + 0) / 1) * f1((n + 1) / 3) % MOD * f1((n + 2) / 2) % MOD;
if (t == 1) return 1LL * f1((n + 0) / 1) * f1((n + 1) / 2) % MOD * f1((n + 2) / 3) % MOD;
}
int f1(ll l, ll r) { return (l < 0 || l > r) ? 0 : fix(f1(r) - f1(l - 1)); } /// sigma(i=l..r) i
int f2(ll l, ll r) { return (l < 0 || l > r) ? 0 : fix(f2(r) - f2(l - 1)); } /// sigma(i=l..r) f1(i)
int f3(ll l, ll r) { return (l < 0 || l > r) ? 0 : fix(f3(r) - f3(l - 1)); } /// sigma(i=l..r) f2(i)
/// * sigma(i=l..r) min(i, y)
/// = sigma(i=l..y-1) (i) + sigma(i=t..r) (y) | t = max(l, y)
/// = f2(l, y-1) + f1(t, r) * y
int g2(ll l, ll r, ll y)
{
minimize(y, r); ll t = max(l, y);
return (f2(l, y - 1) + y * f1(t, r)) % MOD;
}
/// Return the value in [0..MOD)
int fix(ll x) { x %= MOD; if (x < 0) x += MOD; return x; }
/// * max(a, b) = a + b - min(a, b)
/// * L = Take min(x) = k - min(k, x)
/// * R = Take max(x) = min(k, y + z)
/// -------------------------------------------------------
/// * Sigma(x = L..R) { solve2(y, z, x) }
/// = Sigma(x = L..R) { f1(max(0, x - y), min(z, x)) }
/// = Sigma(x = L..R) { f1(x - min(x, y), min(z, x)) }
/// = Sigma(x = L..R) { (1 - x + min(x, y) + min(x, z)) }
/// -------------------------------------------------------
/// > f1(L, R) = Sigma(x = L..R) (1)
/// > f2(L, R) = Sigma(x = L..R) (x)
/// > g2(L, R, y) = Sigma(x = L..R) min(x, y)
/// > g2(L, R, z) = Sigma(x = L..R) min(x, z)
int solve3(ll x, ll y, ll z, ll k)
{
ll L = k - min(k, x);
ll R = min(k, y + z);
if (L > R) return 0;
return fix(f1(L, R) - f2(L, R) + g2(L, R, y) + g2(L, R, z));
}
O(1) solution for N = 4
void quickadd(int &res, int val) { if ((res += val) >= MOD) res -= MOD; }
void quicksub(int &res, int val) { if ((res -= val) < 0 ) res += MOD; }
/// Return the value in [0..MOD)
int fix(ll x) { x %= MOD; if (x < 0) x += MOD; return x; }
/// f1(n) = sigma(i=1..n) (1) = n
/// f2(n) = sigma(i=1..n) (i) = n * (n + 1) / 2
/// f3(n) = sigma(i=1..n) f2(i) = n * (n + 1) * (n + 2) / 6
/// sqf1(n) = sigma(i=1..n) i^2 = n * (n + 1) * (2n + 1) / 6 = f2(n) * (2n + 1) / 3
int f1(ll n) { return n % MOD; }
int f2(ll n) { return 1LL * f1(n) * f1(n + 1) % MOD * inverse_2 % MOD; }
int f3(ll n) { return 1LL * f1(n) * f1(n + 1) % MOD * f1(n + 2 * 1) % MOD * inverse_6 % MOD; }
int sqf1(ll n) { return 1LL * f1(n) * f1(n + 1) % MOD * f1(n * 2 + 1) % MOD * inverse_6 % MOD; }
/// f1(l, r) = sigma(i=l..r) (1)
/// f2(l, r) = sigma(i=l..r) (i)
/// f3(l, r) = sigma(i=l..r) f2(i)
/// sqf1(l, r) = sigma(i=l..r) i^2
int f1(ll l, ll r) { return (l < 0 || l > r) ? 0 : fix(f1(r) - f1(l - 1)); }
int f2(ll l, ll r) { return (l < 0 || l > r) ? 0 : fix(f2(r) - f2(l - 1)); }
int f3(ll l, ll r) { return (l < 0 || l > r) ? 0 : fix(f3(r) - f3(l - 1)); }
int sqf1(ll l, ll r) { return (l < 0 || l > r) ? 0 : fix(sqf1(r) - sqf1(l - 1)); }
/// sigma(i=l..r) min(i, y)
int g2(ll l, ll r, ll y)
{
minimize(y, r); ll t = max(l, y);
return (f2(l, y - 1) + y * f1(t, r)) % MOD;
}
/// sigma(i=l..r) i * min(i, y)
int g3(ll l, ll r, ll y)
{
minimize(y, r); ll t = max(l, y);
return (sqf1(l, t - 1) + y * f2(t, r)) % MOD;
}
/// sigma(i=l..r) min(k - i, y)
/// = sigma(i=k-r..k-l) min(i, y)
int g2(ll l, ll r, ll y, ll k) { return g2(k - r, k - l, y); }
/// sigma(i=l..r) i * min(k - i, y)
/// = sigma(i=k-r..k-l) * min(y, i) * k + sigma(i=k-r..k-l) min(y, i) * k
int g3(ll l, ll r, ll y, ll k) { return g2(k - r, k - l, y) * k - g3(k - r, k - l, y); }
/// If (x < k) then there is no way to share candies
/// Else there are exact (k - x + 1) ways to share
int solve1(ll x, ll k)
{
return max(0LL, k - x + 1) % MOD;
}
/// max(A.get) = x
/// max(B.get) = y
/// max(A.get + B.get) = k
/// * Take max(x) = min(x, k)
/// * Take min(x) = max(0, k - y) = k - min(y, k)
int solve2(ll x, ll y, ll k)
{
return solve1(k - min(y, k), min(x, k));
}
/// * max(a, b) = a + b - min(a, b)
/// * L = Take min(x) = k - min(k, x)
/// * R = Take max(x) = min(k, y + z)
/// -------------------------------------------------------
/// * Sigma(x = L..R) { solve2(y, z, x) }
/// = Sigma(x = L..R) { f1(max(0, x - y), min(z, x)) }
/// = Sigma(x = L..R) { f1(x - min(x, y), min(z, x)) }
/// = Sigma(x = L..R) { (1 - x + min(x, y) + min(x, z)) }
/// = f1(L, R) - f2(L, R) + g2(L,R, y) + g2(L, R, z)
/// -------------------------------------------------------
/// > f1(L, R) = Sigma(x = L..R) (1)
/// > f2(L, R) = Sigma(x = L..R) (x)
/// > g2(L, R, y) = Sigma(x = L..R) min(x, y)
/// > g2(L, R, z) = Sigma(x = L..R) min(x, z)
int solve3(ll x, ll y, ll z, ll k)
{
ll L = k - min(k, x);
ll R = min(k, y + z);
if (L > R) return 0;
return fix(f1(L, R) - f2(L, R) + g2(L, R, y) + g2(L, R, z));
}
/// * max(x, y, z, t, z + t) <= R
/// * L = Take min(x + y) = k - min(k, z + t)
/// * R = Take max(x + y) = min(k, x + y)
/// -------------------------------------------------------
/// * Sigma(s = L..R) { solve2(x, y, s) * solve2(z, t, k-s) }
///
/// = Sigma(s = L..R) { min(x, s) - s + min(y, s) + 1 }
/// * { min(t, k-s) - k + s + min(z, k-s) + 1 }
///
/// = Sigma(s = L..R) { min(x, s) * min(t, k-s) - s * min(t, k-s) + min(y, s) * min(t, k-s) + min(t, k-s) }
/// + { min(x, s) * min(z, k-s) - s * min(z, k-s) + min(y, s) * min(z, k-s) + min(z, k-s) }
/// - { min(x, s) * k - s * k + min(y, s) * k + k }
/// + { min(x, s) * s - s * s + min(y, s) * s + s }
/// + { min(x, s) - s + min(y, s) + 1 }
///
/// = Sigma(s = L..R) A(k) + B(x) + B(y) + C(k) + D(z, x) + D(z, y) + D(t, x) + D(t, y)
///
/// With X = max(x, L)
/// A(k)> Sigma(s = L..R) { 1 - k + s * k-s * s }
/// = Sigma(s = L..R) (1 - k) + Sigma(s = L..R) (s * k) - Sigma(s = L..R) (s * s)
/// = f1(L, R) * (1 - k) + f2(L, R) * k - sqf1(L, R)
///
/// B(x)> Sigma(s = L..R) { min(x, s) * (s - k + 1) }
/// = (1 - k) * Sigma(s = L..X-1) min(x, s) + Sigma(s = L..X-1) min(x, s) * s
/// = (1 - k) * (f2(L, X-1) + f1(X, R) * x) + sqf1(L, X - 1) + f2(X, R) * x
///
/// C(k)> Sigma(s = L..R) { min(z, k-s) * (1 - s) }
/// = Sigma(s = L..R) min(z, k-s) - Sigma(s = L..R) min(z, k-s) * s
/// = g2(L, R, z, k) - g3(L, R, z, t)
///
/// D(z, x)> Sigma(s = L..R) { min(z, k-s) * min(x, s) }
/// = Sigma(s = L..X-1) min(z, k-s) * s + Sigma(s = X..R) min(z, k-s) * x
/// = g3(L, X - 1, z, k) + g2(X, R, z, k) * x
/// ---------------------------------------------------------------------------------------------------------------------------------
int solve4(ll x, ll y, ll z, ll t, ll k)
{
ll L = k - min(k, z + t);
ll R = min(k, x + y);
if (L > R) return 0;
minimize(x, R);
minimize(y, R);
ll X = max(L, x), Y = max(L, y);
int res = 0;
quickadd(res, fix(0LL + f1(L, R) * (1 - k) + f2(L, R) * k - sqf1(L, R))); /// A(k)
quickadd(res, fix(0LL + (1 - k) * (f2(L, X - 1) + f1(X, R) * x) + sqf1(L, X - 1) + f2(X, R) * x)); /// B(x)
quickadd(res, fix(0LL + (1 - k) * (f2(L, Y - 1) + f1(Y, R) * y) + sqf1(L, Y - 1) + f2(Y, R) * y)); /// B(y)
quickadd(res, fix(0LL + g2(L, R, z, k) - g3(L, R, z, k))); /// C(z)
quickadd(res, fix(0LL + g2(L, R, t, k) - g3(L, R, t, k))); /// C(z)
quickadd(res, fix(0LL + g3(L, X - 1, z, k) + g2(X, R, z, k) * x)); /// D(x, z)
quickadd(res, fix(0LL + g3(L, Y - 1, z, k) + g2(Y, R, z, k) * y)); /// D(y, z)
quickadd(res, fix(0LL + g3(L, X - 1, t, k) + g2(X, R, t, k) * x)); /// D(x, t)
quickadd(res, fix(0LL + g3(L, Y - 1, t, k) + g2(Y, R, t, k) * y)); /// D(y, t)
return res;
}
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 ?
I don't know answer now, but I just wanna say your blog formatting and quality has really improved!
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.
Unless there is some structure in $$$a_i$$$'s it would be surprising to solve the problem in $$$O(poly(N) polylog(K))$$$.