# MAXMINK - Editorial

Setter: Utkarsh Gupta
Tester: Manan Grover
Editorialist: Lavish Gupta

Easy-Medium

# PREREQUISITES:

Dynamic Programming

# 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];
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) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

assert(getchar()==EOF);
}
void solve()
{
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
ll A[n+1]={0};
ll B[n+1]={0};
for(int i=1;i<=n;i++)
{
if(i!=n)
else
}
for(int i=1;i<=n;i++)
{
if(i!=n)
else
}
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=0;
while(t++<T)
{
//cout<<"Case #"<<t<<":"<<' ';
solve();
//cout<<'\n';
}
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;
}

12 Likes

I had a solution which involved a 3D boolean dp. dp[x][y][k] will denote whether there exist i_1, i_2, \cdots i_k such that A_{i_1} + A_{i_2} + \cdots + A_{i_k} = x and B_{i_1} + B_{i_2} + \cdots + B_{i_k} = y. The transitions are

for(int i = 0; i < n; i++){
for(int x = N-1; x >= a[i]; x--){
for(int y = N-1;y >= b[i];y--){
for(int j = 1; j <= k; j++){
dp[x][y][j] |= dp[x-a[i]][y-b[i]][j-1];
}
}
}
}


I converted this to a long long int dp[x][y] by using individual bits of the integer as indicators and replacing the transition loop using bit-shift and bitwise or.

for(int i = 0; i < n; i++){
for(int x = N-1; x >= a[i]; x--){
for(int y = N-1;y >= b[i];y--){
dp[x][y] |= dp[x-a[i]][y-b[i]] << 1;
}
}
}


This solution very barely passes. Here is my submission

https://www.codechef.com/viewsolution/57167862

2 Likes

Your code can be optimized more if you take care of that N bound. The testcase which takes around 0.9 s will only take around 0.5 s then

can you tell me why my code is not working?
https://www.codechef.com/viewsolution/57210534

Tried using Backtracking.
This gives AC in 5/9 Test case and TLE in remaining 4.
Not able optimize it more.
Could it be done using Backtracking? by following below implementation or any other?
Or we have to do it with DP only?

/*
Author : Bhavya Kawatra
Institute : MAIT
Dept : CST
Email : bhavyakawatra6@gmail.com
CF handle : BhavyaKawatra13
*/
#include <bits/stdc++.h>
using namespace std;

#define db double
#define im INT_MAX
#define ll long long
#define mod 1000000007
#define vi vector<int>
#define vvi vector<vi>
#define vp vector<pair<int,int>>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mem(x, y) memset(x, y, sizeof(x))
#define SP(x) cout << fixed;cout << setprecision(x);
#define sz(x) (int)x.size()
#define fast  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define PI 3.14159265358979323846
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define getss(s) getline(cin, s);
#define in(n) int n;cin >> n;
#define arr(n) int arr[n];
#define in2(a, b) int a,b;cin >> a >> b;
#define in3(a, b, c) int a,b,c;cin >> a >> b >> c;
#define max_heap(pq) priority_queue <int> pq;
#define min_heap(pq) priority_queue <int, vector<int>, greater<int> > pq;
#define sorta(v) sort(v.begin(),v.end());
#define sortd(v) sort(v.begin(),v.end());
#define pn(p) cout<<p<<endl;
#define pt(p) cout<<p<<" ";
#define pt2(p,q) cout<<p<<" "<<q<<endl;
#define pt3(p,q,r) cout<<p<<" "<<q<<" "<<r<<endl;
#define pt4(p,q,r,s) cout<<p<<" "<<q<<" "<<r<<" "<<s<<endl;
#define vfor(v) for (auto i =v.begin() ; i!=v.end(); i++)
#define vbfor(v) for (auto i =v.rbegin() ; i!=v.rend(); i++)
#define ffor(i, a, b) for (int i = a; i < b; i++)
#define bfor(i, a, b) for (int i = a - 1; i >= b; i--)

/*-----------------begin---------------*/
int n,k;
int ans;
void check(vi a,vi b,vi s){
int x=0,y=0;
ffor(i,0,s.size())x+=a[s[i]];
ffor(i,0,s.size())y+=b[s[i]];
// pt2(x,y);
// pt2(x,y)
ans=max(min(x,y),ans);
}
void fun(vi s,vi a,vi b,vi dp,vi bound){
bool g=true;
ffor(i,0,k){
if(s[i]==-1){g=false;break;}
}
if(g){check(a,b,s);return;}
ffor(i,0,k){
if(s[i]>bound[i])return;
if(s[i]==-1){
if(s[i-1]==-1&&i>0)continue;
int x=0;
if(i>0)x=s[i-1];
ffor(j,x,bound[i]+1){
if(dp[j]==0){
dp[j]=1;
s[i]=j;
fun(s,a,b,dp,bound);
dp[j]=0;
s[i]=-1;
}
}
}
}
}

void solve()
{
cin>>n>>k;
ans=0;
vi a(n),b(n);
ffor(i,0,n)cin>>a[i];
ffor(i,0,n)cin>>b[i];
vi s(k),dp(n);
ffor(i,0,k)s[i]=-1;
ffor(i,0,k)dp[i]=0;
vi bound(k);
int y=0;
bfor(i,k,0){bound[i]=n-1-y;y++;}
fun(s,a,b,dp,bound);
pn(ans);
}
/*-----------------end---------------*/
signed main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

fast;
int t;
cin>>t;
while(t--)
{
solve();
}

return 0;
}


I tried your code with a maxtest for your N variable (A == B == [40]*40) and it took 3.4s on custom execution, so I think the test data is a bit weak, maybe it has some constraints on the sum of N. (Actually I was trying to get it to stack overflow, since you allocate dp[N][N] on the stack, not sure why it doesn’t)

I also did the same dp and optimized it by replacing K with N-K sometimes (in which case the objective function should be min(sum(A) - a, sum(B) - b)) to reduce K and also to get the dp to fit in 32 bits (better cache?) but it still fails the maxtest

I tried solving using a 2D dp where the value of the dp was pair<int,pair<int,int>> i.e. pair<bestValue<corresponding sum in a, corresponding sum in b>>.
It passes the given example test case but fail all other test cases.
I used knapsack intuition for this.
My solution

your memoization does not work here
consider this testcase:
1
4 3
8 8 9 5
1 6 9 8
here dp[4][3][22] = 18 will be memoized when index 0,2,3 are picked
but optimal solution comes when index 1,2,3 will be picked but the solution for this must also be stored at dp[4][3][22] but this has already been memoized so the optimal solution for this case won’t be saved in your table
I don’t think this simple memoization technique will work here as sum is not unique (will work if u can guarantee the time u memoized no greater sum can be obtained; i don’t know if that can be done though) . U can reach the same sum through different elements so memoization does not guarantee the sum of array b u memoized is max sum which can be achieved with sum of array a obtained

1 Like

Please, explain me where am I wrong.
#include <bits/stdc++.h>
#define ll unsigned long long int
using namespace std;
ll arr[41][41];
ll maxi(vector& a,vector& b,ll i,ll k,ll aa,ll bb,ll& n,ll g){
if(arr[i][g]!=0){
return arr[i][g];
}
if(g>=k){
return min(aa,bb);
}
if(i>=n){
return 0;
}
ll f=maxi(a,b,i+1,k,aa+a[i],bb+b[i],n,g+1);
ll o=maxi(a,b,i+1,k,aa,bb,n,g);
return arr[i][g]=max(f,o);

}

int main() {
ll t,a,b;
cin>>t;
while(t–){
cin>>a>>b;
ll e;
vector v,d;
for(ll i=0;i<a;i++){
cin>>e;
v.push_back(e);
}
for(ll i=0;i<a;i++){
cin>>e;
d.push_back(e);
}
memset(arr,0,sizeof(arr));
ll g=0,h=0;
cout<<maxi(v,d,0,b,g,h,a,0)<<"\n";
}
return 0;
}

https://www.codechef.com/viewsolution/57258855

Thanks, Man Got it now. So you mean there is no way we can solve this problem using the memoization technique?

someone did implement memoization but used binary search along . Anyways in my opinion simple memoization like yours won’t do , u need to do something extra to make memoization work

My recursive solution https://www.codechef.com/viewsolution/57495096

I don’t understand what does dp[i][j][sumA] represent here… I approached this like a knapsack with weight as k.
in that I know dp[i][j] contains optimal solution if we limit us to i elements and j capacity.
So what does dp[i][j][sumA] even mean?
Here is my solution
https://www.codechef.com/viewsolution/57869912
It passed 5 but TLE for 4.