INOI1501 - Editorial

editorial
, , , , ,
1

Contest

DIFFICULTY

Easy

PREREQUISITES

Prefix Sums, Prefix-Postfix Maximum

PROBLEM

Given two lists of N integers, a_1, a_2, \dots a_N and b_1, b_2, \dots b_N. For any pair (i, j) with i, j \in \{1, 2, \dots N\}, we define the segment from i to j, written as [i, j], to be i, i + 1, ..., j if i ≤ j and i, i + 1, ..., N, 1, 2, ...,j if i > j.
With each segment [i, j] we associate a special sum SSum[i, j] as follows:
if i=j, SSum[i,i] = a[i]
if i \neq j, SSum[i,j] = a_i + \displaystyle\sum_{k \in [i, j], k \neq i,j}{b_k} + a_j

Find the maximum value of SSum[i, j] over all segments [i, j].

QUICK EXPLANATION

We have to take maximum of SSum[i,j] over all possible intervals [i,j]. There are three type of intervals- (i) i<j, (ii) i>j, (iii) i=j. We can fix j and find maximum value of SSum[i,j] by picking the best i in each case. This can be easily done using prefix sum of b, prefix-postfix maximum of (a[i]-prefixSumB[i]).

EXPLANATION

Let’s consider three cases- (i) i<j, (ii) i>j, (iii) i=j.

Case - 1: i<j

When i<j, SSum[i,j] can be written as following -

SSum[i,j] = a[i] + (b[i+1] + b[i+2] + ... + b[j-1]) + a[j]

Lets’s denote it in terms of prefix sums of b. Let pb[i] denote prefix sum of b till index i. Here the sum b[i+1] + b[i+2] + ... + b[j-1] can be written as pb[j-1] - pb[i]. Hence the above formula can be rewritten as -

SSum[i,j] = a[i] + pb[j-1] - pb[i] + a[j]

Now for any fixed j, maximum value of SSum can be denoted as SSumMax1(j).

SSumMax1(j) = a[j]+pb[j-1] + max(a[i]-pb[i]) for all i<j

Let c[j] denoate max(a[i]-pb[i]) for all i<=j
We can calculate c as following -

c[1] = a[1]-pb[1]
c[j] = max(c[j-1], a[j]-pb[j]), for j>1

This array c can be calculated in linear time.
Now let’s write SSumMax1(j) in terms of c -

SSumMax1(j) = a[j]+pb[j-1] + c[j-1]

because term max(a[i]-pb[i]) for all i<j can be replaced as c[j-1].

So once we have arrays pb and c, we can calculate SSumMax1(j) in constant time. Then we can just loop through all j to find the maximum of SSumMax1(j).

Case - 2: i>j

When i>j, SSum[i,j] can be written as following -

SSum[i,j] = (b[1] + b[2] + ... + b[j-1]) + a[j] + a[i] + (b[i+1]+b[i+2]+...+b[n])

Now let’s write it in terms of pb that is prefix sum of b as mentioned in case-1.

SSum[i,j] = pb[j-1] + a[j] + a[i] + (pb[n] - pb[i])

Now for any fixed j, maximum value of SSum can be denoted as SSumMax2(j).

SSumMax2(j) = pb[j-1] + a[j] + pb[n] + max(a[i]-pb[i]) for all i>j

Let d[i] denoate max(a[i]-pb[i]) for all i>=j
We can calculate d as following -

d[n] = a[n]-pb[n]
d[j] = max(d[j+1], a[j]-pb[j]), for j<n

This array d can be calculated in linear time.
Now let’s write SSumMax2(j) in terms of d -

SSumMax2(j) = pb[j-1] + a[j] + pb[n] + d[j+1]

because term max(a[i]-pb[i]) for all i>j can be replaced as d[j+1].

So once we have arrays pb and d, we can calculate SSumMax2(j) in constant time. Then we can just loop through all j to find the maximum of SSumMax2(j).

Case - 3: i=j

When i=j, SSum[i,j] can be calculated as following -
SSum[i,j] = SSum[j,j] = a[j]

Now we can loop through all j and calculate maximum of SSum(j,j) in linear time.

Finally we have maximum from all three cases. And final answer is the maximum of all three cases.

TIME COMPLEXITY

It takes linear time to calculate arrays pb, c, d. Also to calculate max of all three conditions, we loop through all j = 1 ...n, it takes linear time only. Hence overall time complexity is O(n).

SOLUTION

C++ Code 

/***************************************************

@author: vichitr
Compiled On: 24th Aug 2020

*****************************************************/
#include<bits/stdc++.h>
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
using namespace std;

void solve(){
    int n; cin>>n;
    int a[n+1], b[n+1];
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];

    int pb[n+1], c[n+1], d[n+2];

    pb[0] = c[0] = d[n+1] = 0ll;

    for(int i=1;i<=n;i++){
        pb[i] = pb[i-1]+b[i];
    }

    c[1] = a[1] - pb[1];
    for(int i=2;i<=n;i++){
        c[i] = max(c[i-1], a[i] - pb[i]);
    }

    d[n] = a[n] - pb[n];
    for(int i=n-1;i>0;i--){
        d[i] = max(d[i+1], a[i] - pb[i]);
    }

    // case 3
    int ans = *max_element(a+1, a+n+1);

    // case 1
    for(int j=2;j<=n;j++){
        ans = max(ans, a[j]+pb[j-1]+c[j-1]); 
    }

    // case 2
    for(int j=1;j<n;j++){
        ans = max(ans, pb[j-1]+a[j]+pb[n]+d[j+1]);
    }

    cout<<ans;
}

signed main()
{
    fast;
    int t=1;
    // cin >>t;
    for(int i=1;i<=t;i++)
    {
        solve();
    }
    return 0;
}

/*****************************

5
2 3 2 3 1
3 4 4 6 3

18

**************************/

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Suggestions are welcome! :smile:

2 Likes