PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester & Editorialist: iceknight1093
DIFFICULTY:
2786
PREREQUISITES:
Basic dynamic programming
PROBLEM:
You’re given two arrays A and B of length N each.
Use them to create an array C of length 2N, where A_i and B_i must be placed at positions C_{2i-1} and C_{2i} (in some order).
Alice first chooses a single i, and fixes the order of A_i and B_i in C.
Bob then fixes the order for the other N-1 indices.
Alice wants to minimize the maximum subarray sum of the resulting array; while Bob wants to maximize it.
Find the final value of the maximum subarray sum.
EXPLANATION:
Alice has 2N possible starting moves: she chooses one index x out of N, then chooses which of C_{2x-1} and C_{2x} should be A_x and which should be B_x.
Suppose Alice’s move is fixed. Let’s see what Bob will do.
Bob wants to maximize F(C), the maximum subarray sum of C.
Recall that the classical maximum subarray sum problem can be solved in linear time using dynamic programming..
Our problem can be solved by modifying that algorithm slightly, as follows:
- Let dp_{i} be the maximum sum of a subarray ending at index i of array C, if Bob makes his choices optimally.
- Given that there are two choices for where A_i and B_i go, we have the following considerations:
- At index 2i-1, Bob can choose either A_i or B_i; along with a subarray ending at index 2i-2.
So, dp_{2i-1} = \max(0, \max(A_i, B_i) + dp_{2i-2}) - At index 2i, Bob must choose the order of A_i and B_i as well.
If both A_i and B_i are included in the maximum subarray sum, then there’ll be a subarray ending at index 2i-2 as well.
If only one of A_i and B_i is included, it’s best to take the larger one.
So, dp_{2i} = \max\{0, A_i, B_i, A_i + B_i + dp_{2i-2}\}
- At index 2i-1, Bob can choose either A_i or B_i; along with a subarray ending at index 2i-2.
- Of course, for indices 2x-1 and 2x Alice has already fixed their values; so for these two indices alone the transition will be slightly different: Bob will not have a choice of A_i and B_i and must use the fixed values.
- F(C) will be the maximum value in the dp array.
Together, this gives us a solution in \mathcal{O}(N^2): for each of the 2N possible starting moves of Alice, we can compute Bob’s best F(C) in \mathcal{O}(N) time.
Taking the min across all these choices gives the final answer.
However, this is too slow for the given constraints.
To optimize it, notice that we can in fact reuse a lot of the information we need without having to recompute it each time.
Let’s first assume that Alice hasn’t fixed anything, and run the \mathcal{O}(N) algorithm for Bob as described above to compute all dp_i values.
Let’s also do the same thing, but in reverse (that is, compute rdp_i to be the largest subarray sum starting from index i).
Now, suppose Alice fixes index x, and the values of C_{2x-1} and C_{2x}. Then, considering all possible subarrays:
- First, there are subarrays that end before index 2x-1.
For these, the best value is \max(dp_i) across 1 \leq i \lt 2x-1.
As a prefix max of the dp array, this can be precomputed and hence found in \mathcal{O}(1). - Then, there are subarrays that start after index 2x.
Once again, this is \max(rdp_i) across 2x \lt i \leq 2N, and as a suffix max can also be precomputed. - Finally, we have subarrays that include indices 2x-1 and/or 2x. Again, there are three types here:
- Subarrays including only 2x-1: the best Bob can do is dp_{2x-2} + C_{2x-1}, i.e, take the best sum ending at 2x-2 and add C_{2x-1} to it.
- Subarrays including only 2x: similarly, the value here is C_{2x} + rdp_{2x+1}.
- Subarrays including both: the largest value is C_{2x-1} + C_{2x} + dp_{2x-2} + rdp_{2x+1}.
- Bob’s best value is the maximum among everything computed here.
Notice that after precomputation, each value we wanted could be obtained in \mathcal{O}(1) time.
So, we can try all 2N possible starting positions for Alice, find their F(C) values in \mathcal{O}(1) time, and take the minimum across them all.
This solves the problem in \mathcal{O}(N) time.
TIME COMPLEXITY
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define di(a) int a;cin>>a;
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define sis string s;
#define sin string s;cin>>s;
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
int power( int N, int M){
int power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum *= power;}
power = power * power;M = M >> 1;}
return sum;
}
int mss(int n,vi a,vi b,vi c,int t=0){
int mx = 0;int mn = 0;
// cout<<"hi"<<endl;
rep(i,1,n+1){
// cout<<c[i-1]+b[i]-mn<<" "<<c[i]-mn<<" "<<mn<<endl;
mx=max(mx,c[i-1]+b[i]-mn);
if(t==1)mx=max(mx,c[i-1]+a[i]-mn);
mx=max(mx,c[i]-mn);
mn=min(mn,c[i-1]+a[i]);
if(t==0)mn=min(mn,c[i-1]+b[i]);
mn=min(mn,c[i]);
}
return mx;
}
void solve()
{
di(n)
vi a(n+1);vi b(n+1);
rep(i,1,n+1)cin>>a[i];
rep(i,1,n+1)cin>>b[i];
rep(i,1,n+1){
if(a[i]>b[i])swap(a[i],b[i]);
}
vi c(n+1);
rep(i,1,n+1){c[i]=c[i-1]+a[i]+b[i];}
int ans = 0;
rep(i,1,n+1)ans=max({ans,a[i],b[i]});
int mx = mss(n,a,b,c);
int mn=0,l=0,r=0;
rep(i,1,n+1){
if(c[i-1]+b[i]-mn==mx){r=i;break;}
if(c[i]-mn==mx){r=i;break;}
if(a[i]+c[i-1]<=mn){l=i,mn=c[i-1]+a[i];}
if(c[i]<=mn){l=i,mn=c[i];}
}
// cout<<mx<<endl;
// cout<<l<<" "<<r<<endl;
swap(a[l],b[l]);
mn = mx;
mn=min(mn,mss(n,a,b,c,1));
// cout<<mss(n,a,b,c)<<endl;
swap(a[l],b[l]);
swap(a[r],b[r]);
mn=min(mn,mss(n,a,b,c));
// cout<<mss(n,a,b,c)<<endl;
ans=max(ans,mn);
cout<<ans<<endl;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef NCR
init();
#endif
#ifdef SIEVE
sieve();
#endif
di(t)
while(t--)
solve();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
best_till = [0]*(n+2)
best_from = [0]*(n+2)
pref = [0]*(n+2)
suf = [0]*(n+2)
for i in range(1, n+1):
pref[i] = max(pref[i-1], best_till[i-1] + max(a[i], b[i], a[i] + b[i]))
best_till[i] = max(0, best_till[i-1] + a[i] + b[i], a[i], b[i])
for i in reversed(range(1, n+1)):
suf[i] = max(suf[i+1], best_from[i+1] + max(a[i], b[i], a[i] + b[i]))
best_from[i] = max(0, best_from[i+1] + a[i] + b[i], a[i], b[i])
ans = 10**18
for i in range(1, n+1):
cur = max(pref[i-1], suf[i+1])
ab = max(best_till[i-1] + a[i], best_from[i+1] + b[i], best_till[i-1]+best_from[i+1] + a[i]+b[i])
ba = max(best_till[i-1] + b[i], best_from[i+1] + a[i], best_till[i-1]+best_from[i+1] + a[i]+b[i])
cur = max(cur, min(ab, ba))
ans = min(ans, cur)
print(ans)
