ALTERSUM - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Authors: Lavish Gupta
Testers: Abhinav Sharma
Editorialist: Nishank Suresh

DIFFICULTY:

Easy

PREREQUISITES:

Prefix and suffix sums

PROBLEM:

The alternating sum of an array A is A_1 - A_2 + A_3 - \ldots + (-1)^{N-1}A_N. At most once, you can take an odd-sized subarray of A and move it to the end. What is the maximum possible alternating sum the final array can have?

EXPLANATION:

There are \mathcal{O}(N^2) odd-sized subarrays, so under the given constraints calculating the alternating sum when each one of them is moved to the end will be too slow.

Let’s analyze how the alternating sum changes when we move subarray [L, R] to the end. The array is now [A_1, A_2, \ldots, A_{L-1}, A_{R+1}, \ldots, A_N, A_L, \ldots, A_R].
Note that the array is effectively split into three parts - the prefix [1, L-1], the subarray [L, R], and the suffix [R+1, N].
Let’s look at the contribution of each of those parts to the alternating sum separately.

The prefix

The elements of the prefix don’t change their position whatsoever, and so the alternating sum of this part is A_1 - A_2 + A_3 - \ldots + (-1)^{L-2}A_{L-1} — exactly the same as its contribution to the alternating sum in the original array.

The suffix

The elements of the suffix [R+1, N] are moved such that A_{R+1} is at position L, A_{R+2} is at position L+1, and so on.
So, the alternating sum of this part is (-1)^{L-1}A_{R+1} + (-1)^L A_{R+2} + \ldots .
However, note that the length of the subarray is odd - i.e, R-L+1 is odd, which means that L and R have the same parity.
Thus, the above sum can also be written as (-1)^{R-1}A_{R+1} + (-1)^R A_{R+2} + \ldots + (-1)^{N-2}A_N.

However, alternating sum in the original array is (-1)^{R}A_{R+1} + (-1)^{R+1} A_{R+2} + \ldots — the sign of every element is flipped. Thus, this part contributes the negative of whatever it did to the original array.

The subarray

Let k = R-L+1 be the length of the subarray.
The elements of the subarray are moved such that they now start from position N-k+1 (because all the N-k elements outside the subarray are placed before it).
The alternating sum of this part is then (-1)^{N-k} A_L + (-1)^{N-k+1} A_{L+1} + \ldots (-1)^{N-k+R-L}A_R.
Now,

  • If (-1)^{N-k} = (-1)^{L-1}, the alternating sum of this part is exactly the same as its alternating sum in the original array, because all the signs will remain the same.
  • If (-1)^{N-k} \neq (-1)^{L-1}, the alternating sum of this part is the negative of its alternating sum in the original array, because all its signs flip.

When do these cases happen?
We know that k is odd, so N-k and L-1 have the same parity if and only if N and L have the same parity — equivalently, N and R have the same parity (because L and R have the same parity).

Putting it together, we know the following:

  • The alternating sum of the prefix stays the same.
  • The alteranting sum of the suffix is the negative of its alternating sum in the original array.
  • The alternating sum of the subarray is either the same or the negative, depending only on the parity of the endpoints of the subarray.

This gives us the following idea: suppose we fix the right endpoint R of the subarray. Let’s try to find the optimal left endpoint L such that moving [L, R] to the end gives us as large an alternating sum as possible. Computing this for every 1 \leq R \leq N will give us the answer.

Note that we are dealing with prefix and suffix alternating sums, so it is useful to precompute those.
Let

pref_i = A_1 - A_2 + A_3 - \ldots + (-1)^{i-1}A_i \\ suf_i = (-1)^{i-1}A_i + (-1)^{i}A_{i+1} + \ldots + (-1)^{N-1}A_N

Also note that once pref_i has been computed, the alternating sum of any subarray [L, R] can be obtained as pref_R - pref_{L-1}.

Now, fix the right endpoint R. There are two cases:

  • Suppose R and N have the same parity. Then, for any 1\leq L \leq R (where R-L+1 is odd), the prefix [1, L-1] and the subarray [L, R] have the same alternating sum as the original array, while the suffix [R+1, N] has its alternating sum negated.
    Putting this together, the total alternating sum is simply pref_R - suf_{R+1}, independent of choice of L.
  • Suppose R and N have different parities. Then, for any 1\leq L \leq R (where R-L+1 is odd), the prefix [1, L-1] has the same alternating sum, while the subarray [L, R] and the suffix [R+1, N] have their alternating sums negated.
    The total alternating sum is then pref_{L-1} - suf_{R+1} - (pref_R - pref_{L-1}), which equals 2\cdot pref_{L-1} - pref_R - suf_{R+1}.
    The latter two terms are independent of choice of L, so this expression is maximized when pref_{L-1} is maximized.
    However, we already computed all the values of pref_i, so this is simple to do — just compute prefix maximums of the pref array. Remember that L and R must have the same parity (which is different from the parity of N in this case), so be sure to compute the maximums only over those indices whose parity matches the parity of N.

Once the prefix sums, suffix sums, and prefix maximums are computed, the answer for a given R can be found in \mathcal{O}(1). Thus, the algorithm as a whole runs in \mathcal{O}(N).

TIME COMPLEXITY:

\mathcal{O}(N) per test case.

SOLUTIONS:

Setter's Solution (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
 
/*
------------------------Input Checker----------------------------------
*/
 
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;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            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,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 100000;
const int MAX_N = 100000;
const int MAX_SUM_N = 1000000;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
int sum_n = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll z = 998244353;
ll dp[2500005] ;
 
void solve()
{   
    int n = readIntLn(3 , MAX_N) ;
    sum_n += n ;
    max_n = max(n , max_n) ;   

    ll arr[n] ;
    for(int i = 0 ; i < n-1 ; i++)
        arr[i] = readIntSp(1 , 1000000000) ;
    arr[n-1] = readIntLn(1 , 1000000000) ;

    ll suff[n] ;
    int mult = 1 ;
    if(n%2 == 0) 
        mult *= -1 ;

    suff[n-1] = mult*arr[n-1] ;
    mult *= -1 ;
    for(int i = n-2 ; i >= 0 ; i--)
    {
        suff[i] = suff[i+1] + (mult * arr[i]) ;
        mult *= -1 ;
    }

    ll ans = suff[0] ;
    int len = 0 ;
    for(int i = n-1 ; i >= 0 ; i--)
    {
        len++ ;
        if(len%2 == 1)
        {
            continue ;
        }

        ll diff = (-2 * suff[i]) ;
        ans = max(ans , suff[0] + diff) ;
    }
    cout << ans << endl ;
    return ;
}
 
signed main()
{
    // fast;
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif
    
    int t = 1;
    
    t = readIntLn(1,MAX_T);

    for(int i=1;i<=t;i++)
    {    
        solve() ;
    }
 
    assert(getchar() == -1);
    assert(sum_n <= MAX_SUM_N);
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    cerr<<"Sum of lengths : " << sum_n << '\n';
    cerr<<"Maximum length : " << max_n << '\n';
    // cerr<<"Total operations : " << total_ops << '\n';
    // cerr<<"Answered yes : " << yess << '\n';
    // cerr<<"Answered no : " << nos << '\n';
}
Tester's Solution (C++)
#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
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;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            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,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
 
int sum_len = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;

const ll MX=200000;
ll fac[MX], ifac[MX];

const ll mod = 998244353;

ll po(ll x, ll n ){ 
    ll ans=1;
     while(n>0){
        if(n&1) ans=(ans*x)%mod;
        x=(x*x)%mod;
        n/=2;
     }
     return ans;
}

void solve()
{   
    int n = readIntLn(3,1e5);
    sum_len += n;

    ll a[n];

    for(int i=0; i<n-1; i++) a[i] = readIntSp(1, 1e9);
    a[n-1] = readIntLn(1, 1e9);

    ll cur = 0;
    for(int i=0; i<n; i++){
        if(i&1) cur-=a[i];
        else cur+=a[i];
    }

    ll o_mx = -1e18, e_mx =-1e18;
    ll o_mn = 1e18, e_mn = 1e18;

    ll ans = cur;
    ll cur1 = 0;
    for(int i=n-1; i>=0; i--){
        if(i&1){
            o_mx = max(o_mx, cur);
            o_mn = min(o_mn, cur);
            cur+=a[i];
            cur1+=a[i];

            if(n&1){
                ans = max(ans, cur+cur1);
            }
            else{
               // ans = max(ans, cur+cur1+2*(o_mx-cur));
            }

        }
        else{
            e_mx = max(e_mx, cur);
            e_mn = min(e_mn, cur);
            cur-=a[i];
            cur1-=a[i];

            if(n&1){
                //ans = max(ans, cur+cur1+2*(e_mx-cur));
            }
            else{
                ans = max(ans, cur+cur1);
            }
        }


    }

    cout<<ans<<'\n';
}
 
signed main()
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w" , stdout);
    #endif
    fast;
    
    int t = 1;
    
    t = readIntLn(1,1e5);
        
    for(int i=1;i<=t;i++)
    {    
       solve();
    }
    
    assert(getchar() == -1);
    assert(sum_len<=1e6);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    cerr<<"Sum of lengths : " << sum_len << '\n';
    cerr<<"Maximum length : " << max_n << '\n';
    // cerr<<"Total operations : " << total_ops << '\n';
    //cerr<<"Answered yes : " << yess << '\n';
    //cerr<<"Answered no : " << nos << '\n';
}
Editorialist's Solution (Python)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    suf = 0
    pref = 0
    mxpref = 0
    for i in range(n):
        if i%2 == 0:
            suf += a[i]
        else:
            suf -= a[i]
    
    ans = suf
    for i in range(n):
        if i%2 == 0:
            suf -= a[i]
            pref += a[i]
        else:
            suf += a[i]
            pref -= a[i]

        if i%2 != n%2:
            ans = max(ans, pref - suf)
            mxpref =  max(mxpref, pref)
        else:
            ans = max(ans, 2*mxpref - pref- suf)
    print(ans)
7 Likes

I have a little simpler (to implement) solution than the editorial (at least I would like to think so :stuck_out_tongue_winking_eye:).

I multiplied every a_2, a_4, a_6... with -1.
Then I took the suffix sums and the prefix sums for the array.
Now for each suffix of even length, the answer would be prefix[n-x]+suffix[x] where 0 <= x <= n

Link to my accepted solution

6 Likes

How did you reach this idea that only suffix of length even will be able to improve ans.

If you work out all the possible cases (even suffix length, odd suffix length etc), it will boil down to the following observation -

The answer can be written as max(pref[i-1]-suff[i]) for all even length suffixes.

All that remains is to compute prefix and suffix alternating sums (taking care of signs) and compute the above statement.
Refer my code for clearer understanding.

Submission

1 Like

But what’s the intuition?

2 Likes

Suppose that I only want to alter the sign of last element, can I do that?
Answer is no because whatever segment we choose is gonna be having its sign altered too due to odd no of suffix elements.

We can only choose subarray of odd length, So now lets generalise it:
if we choose even no of elements in suffix then only suffix is gonna be altered not the segment we choose(its signs are gonna be same).
if we choose odd no of elements in suffix then both suffix and segment signs will be altered and as segment we choose is going to be of odd length the combined elements whose signs altered are again of even length.

hence we came to conclusion that only even length suffix is gonna be altering our ans.

I don’t know if it makes much sense but that was my thought process while solving this problem.

can anyone please tell me what was wrong in this code . I tried for every test case that is possible but I did’nt get right answer.

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
vectora(n);
ll sum=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
ll currsum=0;
ll minsum=0;
ll l=1;
ll r=n-2;
ll prefsum[n];
ll suffsum[n];
prefsum[0]=a[0];
if(n%2==0)
{
suffsum[n-1]=-a[n-1];
}
else
{
suffsum[n-1]=a[n-1];
}
ll ans=0;
for(int i=1;i<=n-1;i++)
{
if(i%2==0)
{
prefsum[i]=prefsum[i-1]+a[i];
}
else{
prefsum[i]=prefsum[i-1]-a[i];
}
}
for(int i=n-2;i>=0;i–)
{
if(i%2==0)
{
suffsum[i]=suffsum[i+1]+a[i];
}
else
{
suffsum[i]=suffsum[i+1]-a[i];

        }
    }
    for(int i=0;i<=n-1;i++)
    {
        if(i%2==0)
        {
             currsum+=a[i];

        }
        else
        {
            currsum-=a[i];
        }
       
      if(currsum<minsum)
      {
          l=i;
          minsum=currsum;
          
      }
      else
      {
          r=i-1;
          int val=r-l+1;
          if(val%2==1)
          {
          ll sum1=prefsum[r]-prefsum[l-1]+prefsum[l-1]+suffsum[r+1];
          ll sum2=-prefsum[r]+prefsum[l-1]+prefsum[l-1]-suffsum[r+1];
          ll max1=max(sum1,sum2);
          ans=max(ans,max1);
          }
          currsum=0;
          minsum=0;
      }
        
    }
    cout<<ans<<"\n";
    
    
}
return 0;

}

beacuse if we take odd length of l prefix of l-1 will be more than this

Can you explain briefly the approach behind how you got max(pref[i-1]-suff[i])?