PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Utkarsh Gupta
Tester: Manan Grover
Editorialist: Lavish Gupta
DIFFICULTY:
Easy-Medium
PREREQUISITES:
PROBLEM:
You are given two arrays A and B, both of length N.
You would like to choose exactly K distinct indices i_1,i_2, \ldots, i_K such that \min(A_{i_1}+A_{i_2}+ \ldots + A_{i_K}, B_{i_1}+B_{i_2}+\ldots + B_{i_K}) is maximized. Find this maximum value.
QUICK EXPLANATION:
What all information do we need to describe a state of the problem?
Suppose we have seen first i indices. We will require the following information to describe the state:
- The number of indices j that we have chosen till now.
- Possible sum of values of array A for the chosen indices - let’s call it Sum_A
- Possible sum of values of array B for the chosen indices - let’s call it Sum_B
Interesting values of Sum_B, for a given Sum_A!
Let us analyze the state where will have seen first i indices, and have selected j indices out of the first i indices. Also, let say that one of the possible values of Sum_A is S_A.
Now for this value S_A there can be several possible values of Sum_B. Which of these values is interesting for our problem?
The answer is, the maximum possible value of Sum_B is the only value which is required to solve our problem!
The Final DP
Based on the above points, let us have dp[i][j][s], where i represents the number of indices that we have seen so far, j represents the number of indices that we have selected so far, and s represents the sum of values of array A for the chosen indices. The value of dp[i][j][s] represents the the maximum sum of values of array B possible when the sum of values of array A is s.
We can optimize the memory usage just like we do in the classical knapsack. We can remove the state i, and have dp[j][s], and update it as we iterate over i.
EXPLANATION:
So let us first start by counting the number of ways in which we can choose K elements, out of the N elements. We know that it is \binom{N}{K}. To get an estimate of it’s value, let us substitute N = 40, and K = 20. The number of ways turns out to be 1.38 \times 10^{11}, which is very large. So, we can’t try all possible ways and get our optimal answer!
In the problems which involves choosing exactly K elements out of N, and maximizing or minimizing something, it usually helps to think in the direction of Dynamic Programming.
A useful way to start thinking is, what happens when I have seen first i elements, and I have selected j elements out of them. What other information is required to completely describe this state?
In our current problem, we will need the list of all possible values of Sum_A and the corresponding Sum_B, where Sum_A represents the sum of values of A for the chosen j indices (and similarly for Sum_B)
Once we have all these information for all possible states, we can get our answer by iterating over all possible values of Sum_A and Sum_B when i = N, and j = K. However, calculating these value is not efficient, as it can take (40 \cdot 40 \cdot 1600 \cdot 1600 \approx 4\cdot 10^9 ) instructions for each test case, which is not feasible.
So, can we somehow reduce the possible number of states, and focus on the states which are interesting for us? Let us fix the values of i, j, Sum_A, and focus on all the possible values of Sum_B. Suppose there are two values S_1 and S_2, such that S_1 < S_2. Intuitively, it looks like we should always take S_2 for further discussions, because if Sum_A < S_1 and Sum_A < S_2, then S_2 is better, otherwise, Sum_A will be driving the answer, and therefore we can maximize Sum_B. This is just an intuitive statement. To prove it mathematically, we can make cases where
- S_1 < Sum_A and S_2 < Sum_A
- S_1 < Sum_A and S_2 > Sum_A
- S_1 > Sum_A and S_2 > Sum_A
and further analyzing with the new upcoming values of A_{i+1} and B_{i+1}. After this exercise, we can see that it is always better to choose maximum value of Sum_B.
Now, after this realization, we can have dp[i][j][s], where i represents the number of indices that we have seen so far, j represents the number of indices that we have selected so far, and s represents the sum of values of array A for the chosen indices. The value of dp[i][j][s] represents the the maximum sum of values of array B possible when the sum of values of array A is s.
We can optimize the memory usage just like we do in the classical knapsack. We can remove the state i, and have dp[j][s], and update it as we iterate over i.
So if we know value of dp[i][j][s], and now I take index i, I will be able to update the value of -
dp[i+1][j+1][s+A_{i+1}] = max(dp[i+1][j+1][s+A_{i+1}], dp[i][j][s] + B_{i+1}) and
dp[i+1][j][s] = max(dp[i+1][j][s] , dp[i][j][s])
To finally get our answer, we can iterate over all the possible values of s when i = N and j = K, and find the maximum value of min(s , dp[N][K][s])
TIME COMPLEXITY:
Sum_A and Sum_B are bounded by Max_{A_i} \cdot N.
We will iterate over i going from 1 to N, j going from 1 to K, and Sum_A going from 1 to Max_{A_i} \cdot N. Hence, Time Complexity per test case will be O(N^2 \cdot K \cdot Max_{A_i})
SOLUTION:
Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val) no. of elements strictly less than val
// s.find_by_order(i) itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=42;
bool vis[N];
vector <int> adj[N];
ll dp1[N][N*N],dp2[N][N*N];
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
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,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
void solve()
{
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
ll n=readInt(2,40,' ');
ll k=readInt(1,n,'\n');
ll A[n+1]={0};
ll B[n+1]={0};
for(int i=1;i<=n;i++)
{
if(i!=n)
A[i]=readInt(1,40,' ');
else
A[i]=readInt(1,40,'\n');
}
for(int i=1;i<=n;i++)
{
if(i!=n)
B[i]=readInt(1,40,' ');
else
B[i]=readInt(1,40,'\n');
}
memset(dp1,-1,sizeof(dp1));
memset(dp2,-1,sizeof(dp2));
dp1[0][0]=0;
dp1[1][A[1]]=B[1];
ll ans=0;
ans=max(ans,min(A[1],dp1[k][A[1]]));
for(int i=2;i<=n;i++)
{
for(int taken=1;taken<=k;taken++)
{
for(int j=0;j<N*N;j++)
{
dp2[taken][j]=dp1[taken][j];
if(j>=A[i] && dp1[taken-1][j-A[i]]!=-1)
dp2[taken][j]=max(dp2[taken][j],dp1[taken-1][j-A[i]]+B[i]);
if(taken==k)
{
ans=max(ans,min((ll)j,dp2[k][j]));
}
}
}
for(int taken=1;taken<=k;taken++)
{
for(int j=0;j<N*N;j++)
dp1[taken][j]=dp2[taken][j];
}
}
cout<<ans<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T=readInt(1,20,'\n');
int t=0;
while(t++<T)
{
//cout<<"Case #"<<t<<":"<<' ';
solve();
//cout<<'\n';
}
readEOF();
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int solve(int n, int k, int a[], int b[]){
int dp[2000][n][k + 1];
for(int i = 0; i < 2000; i++){
for(int j = 0; j < n; j++){
for(int l = 0; l < k + 1; l++){
if(l == 0){
if(i == 0){
dp[i][j][l] = 0;
}else{
dp[i][j][l] = INT_MIN;
}
continue;
}
if(j == 0){
if(i == b[j] && l == 1){
dp[i][j][l] = a[j];
}else{
dp[i][j][l] = INT_MIN;
}
continue;
}
if(l == i + 1){
if(b[j] > i){
dp[i][j][l] = INT_MIN;
}else{
dp[i][j][l] = dp[i - b[j]][j - 1][l - 1];
}
}else{
dp[i][j][l] = dp[i][j - 1][l];
if(b[j] <= i){
dp[i][j][l] = max(dp[i][j][l], a[j] + dp[i - b[j]][j - 1][l - 1]);
}
}
}
}
}
for(int i = 1999; i > -1; i--){
if(dp[i][n - 1][k] >= i){
return i;
}
}
return -1;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n, k;
cin>>n>>k;
int a[n], b[n];
for(int i = 0; i < n; i++){
cin>>a[i];
}
for(int i = 0; i < n; i++){
cin>>b[i];
}
int ans = max(solve(n, k, a, b), solve(n, k, b, a));
cout<<ans<<"\n";
}
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
#define ll long long
using namespace std ;
const ll z = 1000000007 ;
void solve()
{
int n, k;
cin >> n >> k;
int a[n] , b[n] ;
for(int i = 0 ; i < n ; i++)
cin >> a[i] ;
for(int i = 0 ; i < n ; i++)
cin >> b[i] ;
int dp[k+1][1601] ;
for(int i = 0 ; i <= k ; i++)
for(int j = 0 ; j <= 1600 ; j++)
dp[i][j] = -1;
dp[0][0] = 0 ;
for(int i = 0 ; i < n ; i++)
{
int val = a[i] ;
for(int j = k-1 ; j >= 0 ; j--)
{
for(int s = 0 ; s <= 1600 ; s++)
{
if(dp[j][s] != -1)
{
dp[j+1][s+val] = max(dp[j+1][s+val] , dp[j][s] + b[i]) ;
}
}
}
}
int ans = 0 ;
for(int s = 0 ; s <= 1600 ; s++)
{
// if(min(dp[k][s] , s) > ans)
// cout << "s = " << s << " new_ans = " << min(dp[k][s] , s) << endl ;
ans = max(ans , min(dp[k][s] , s)) ;
}
cout << ans << '\n' ;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif
int t;
cin >> t ;
while(t--)
solve() ;
return 0;
}