PROBLEM LINK:
Author: Sarthak Gupta
Tester: Anshu Garg
DIFFICULTY:
MEDIUM
PREREQUISITES:
You should be familiar with DP and optimisation with Bitset
PROBLEM:
Chef has three storage containers with capacities X, Y and Z respectively. Each container can store multiple flavors of ice cream. Since Chef does not know which flavors Chefina would order, he wants to store maximum number of flavors in the storage containers.
Chef has a total of N flavors. In order to store the i^{th} flavor, Chef must select exactly one container and fill it with C_i amount of flavor i.
Note that the total amount of ice cream filled in a container should not exceed its capacity.
Find the maximum number of flavors Chef can store in the containers.
QUICK EXPLANATION:
- Observe that if r flavours are to be selected, selecting the minimum possible r elements would be optimal.
- Create a three dimensional dp[i][j][k], where it is boolean denoting wheter it is possible to store i flavors with container of capacity j,k,Z. We report the first i, for which dp[i][j][k] is zero \forall j,k (0 based indexing ).
- We optimise memory by observing dp[i] is only dependent on dp[i-1] and optimise time complexity using bitset.
EXPLANATION:
We first observe that if r elements can be stored, the first r flavors in the ascending sorted order of capacity can also be stored. This can be easily proven using contradiction. This follows the conclusion that r flavors can only be stored if and only if the least r flavors can be stored.
- Therefore, sort the flavors according to their capacity
Now we create a dp solution for our problem. Let dp[i][j][k][l] denote a boolean if the least i
elements can be stored using containers with capacity j,k,l.
- Flavor i can be stored in one of the three containers
- It follows the recursive relation that
\space \space dp[i][j][k][l] = dp[i-1][j-C_i][k][l] \vee dp[i-1][j][k-C_i][l] \vee dp[i-1][j][k][l-C_i]
We optimise the above dp solution using the fact that the sum of first i elements must be \leq
(j+k+l). Therefore, keeping two dimensions is enough.
- Let sum of first i flavors be denoted by
- The new recursive relation followed is
\space \space dp[i][j][k] = (dp[i-1][j][k] \wedge (S_i \leq (j+k+Z))) \vee
\space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space dp[i-1][j-C_i][k] \vee dp[i-1][j][k-C_i]
This solution is still too slow to pass, we use bitset to optimise it further .
We create a bitset of length Y for each i and j.
- let e_i denote the first part ( S_i \leq (j+k+Z) ) we get \max(w_i = S_i - j -Z,0) ,
making first w_i elements as zero we get e_i = (dp[i-1][j]>>(w_i))<<w_i) - the second part is simply dp[i-1][j-C_i]
- the third part translates to dp[i-1][j]<<C_i
- performing the or operation on these three gives us dp[i]
As dp[i] is only dependent on dp[i-1] we can optimise space using this fact
TIME COMPLEXITY:
O(N \cdot X \cdot Y / 64) for each testcase.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n,x,y,z;
cin>>n>>x>>y>>z;
vector<int> a(n);
for(auto &u:a)cin>>u;
sort(a.begin(),a.end());
bitset<1501> w(0);
vector<bitset<1501>> dp(x+1);dp[0][0]=1;
for(int i=0;i<=y;++i)w[i]=1;
int sum=0;
for(int i=0;i<n;++i){
bool ch=0;
sum+=a[i];
int b=min(sum,x);
for(int j=b;j>=a[i];--j){
int r=max(0,sum-j-z);
dp[j] = (((dp[j]>>r)<<r)|(dp[j]<<a[i])|(dp[j-a[i]])) & w;
if(!ch)ch|=dp[j].any();
}
for(int j=min(a[i]-1,b);j>=0;--j){
int r=max(0,sum-j-z);
dp[j] = (((dp[j]>>r)<<r)|(dp[j]<<a[i])) & w;
if(!ch)ch|=dp[j].any();
}
if(!ch){
cout<<i<<"\n";
return;
}
}
cout<<n<<"\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(a) (ll)a.size()
#define F first
#define S second
#define INF 151000000000000000000
#define popcount(x) __builtin_popcountll(x)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define ld long double
template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; }
#ifdef LOCAL
#define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 2401
#endif
long long readInt(long long l,long long r,char end){
long long x = 0;
int cnt = 0;
int first =-1;
bool is_neg = false;
while(true) {
char g = getchar();
if(g == '-') {
assert(first == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if(cnt == 0) {
first = g - '0';
}
++cnt;
assert(first != 0 || cnt == 1);
assert(first != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && first > 1)));
}
else if(g == end) {
if(is_neg) {
x = -x;
}
if(!(l <= x and x <= r)) {
cout << x << "\n";
exit(0);
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
string readString(int l,int r,char end){
string ret = "";
int cnt = 0;
while(true) {
char g = getchar();
assert(g != -1);
if(g == end) {
break;
}
++cnt;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int sum_n = 0, mx_n = 0, mn_n = 1e9;
int _runtimeTerror_()
{
int n, x, y, z;
n = readIntSp(1, 2000);
x = readIntSp(1, 1500);
y = readIntSp(1, 1500);
z = readIntLn(1, 1500);
sum_n += n;
amax(mx_n, n);
amin(mn_n, n);
vector<bitset<1510>> dp(x + 1);
dp[0][0] = 1;
vector<int> a(n);
for(int i=0;i<n;++i) {
if(i < n - 1) {
a[i] = readIntSp(1, 1500);
}
else {
a[i] = readIntLn(1, 1500);
}
}
vector<bitset<1510>> f(y + 1);
for(int i=0;i<=y;++i) {
for(int j=i;j<=y;++j) {
f[i][j] = 1;
}
}
sort(all(a));
int sum = 0, ans = 0;
int val = n;
for(int i=0;i<n;++i) {
for(int j=x;j>=0;--j) {
bitset<1510> ans;
if(j >= a[i]) {
ans |= dp[j - a[i]];
}
ans |= dp[j] << a[i];
int tmp = max(0, sum - j + a[i] - z);
if(tmp <= y) {
ans |= f[tmp] & dp[j];
}
dp[j] = ans & f[0];
}
for(int j=0;j<=x;++j) {
if(dp[j].count()) {
ans = i + 1;
}
}
sum += a[i];
}
cout << ans << "\n";
return 0;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef runSieve
sieve();
#endif
#ifdef NCR
initncr();
#endif
int TESTS = 1;
TESTS = readIntLn(1, 200);
cerr << TESTS << "\n";
while(TESTS--) {
_runtimeTerror_();
}
cerr << sum_n << " " << mx_n << " " << mn_n << "\n";
assert(getchar() == -1);
return 0;
}
// check ans = 0
// check ans = n
// check maximal cases