MAXABC - Editorial


Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester & Editorialist: iceknight1093




Basic dynamic programming


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.


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}\}
  • 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.


\mathcal{O}(N) per testcase.


Author's code (C++)
#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;
        // cout<<c[i-1]+b[i]-mn<<" "<<c[i]-mn<<" "<<mn<<endl;
    return mx;

void solve()
    vi a(n+1);vi b(n+1);
    vi c(n+1);
    int ans = 0;
    int mx = mss(n,a,b,c);
    int mn=0,l=0,r=0;
    // cout<<mx<<endl;
    // cout<<l<<" "<<r<<endl;
    mn = mx;
    // cout<<mss(n,a,b,c)<<endl;
    // cout<<mss(n,a,b,c)<<endl;

signed main(){
    #ifdef NCR
    #ifdef SIEVE
    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)

Why Alice can select only one postition to make changes i.e only at x (consider 1 to n for array a and b), for array C this corresponds to 2x and 2x-1?

Alice can make changes at two postion in one move

by selecting any i (1<= i <=n ) Alice can fix a position of 2i and 2i-1 (in array C), so Alice can fix two position in one move.
whoever make changes to the positions (1<= i <= n) first gets to make it permanent in array C (that is position 2i and 2i - 1).

for any subarray l to r (for array a and b, l < r && 1 <= l,r <= n) sum of subarray (in array C) only depends on placing of value at the end points, i.e on the places 2l, 2l-1 and 2r, 2r - 1.

Since the value in the middle elements (from 2l+1 to 2r - 1) are constants (i.e sum of a[i] and b[i], l < i < r ) when calculating the subarray sum, since how they are placed does not matter.

So in one move Alice can disrupt (by putting value before bob) the maximum_sum_subarray and reduce the answer (on the left side(l = 2l,2l-1) or right side(r = 2r,2r-1) , only if any one or both elements of both array is negative), if this reduces our answer in just one move (otherwise do one more change on the other end point)
Alice picks next subarray which has maximum and reduces it. Now whatever be the next max subarray Bob will be able to make it in his favour


by the time Alice made two moves to and make changes to maximum subarray, Bob fixed third maximum subarray by making changes to its end points, Bob can also get second max subarray as the answer if both the changes were made to first max subarray, and even get max subarray as answer if it still is greater even after making changes to its end points

So like this I have come to conclusion that Alice has two places where she can try making minimum.

Where am I getting this wrong?

excellent problem and solution,
i initially thought right but instead of using kadanes/dp i used map and got stuck.

It can be solved with the prefix sum over kadane algorithm. No dp is needed. CodeChef: Practical coding for everyone

1 Like

Kadane’s algorithm is dynamic programming :slight_smile:

1 Like

why the you say that difficulty level of this problem is easy