# PMA - Editorial

Tester: Anshu Garg

SIMPLE

None

# PROBLEM:

Given an array A of size N.
Operation: You can select two indexes i and j ( i \lt j ) and swap A_i and A_j.
Alternating \space Sum = S = |A_1| - |A_2| + |A_3| - |A_4| + \ldots (-1)^{N-1}\cdot |A_N|
With atmost one operation find the maximum Alternating \space Sum.

# EXPLANATION:

Since,
S = |A_1| - |A_2| + |A_3| - |A_4| + \ldots (-1)^{N-1}\cdot |A_N|

It can be observed that using an operation is useful if and only if i and j are of different parity.
Let,
S_1 = \sum_{i \space is \space odd}A_i
S_2 = \sum_{i \space is \space even}A_i
Then,
S = S_1 - S_2

Letās suppose we swap A_i and A_j, where i is odd and j is even and new alternating sum will become S'. Then,
S' = (S_1 - |A_i| + |A_j|) - (S_2 + |A_i| - |A_j|) = S + 2 \cdot (|A_j| - |A_i|)
So, to maximize S', we need to maximize |A_j| and minimize |A_i|.
Let,
|A_i|_{min} be minimum value of |A_i| where i is odd.
|A_j|_{max} be maximum value of |A_j| where j is even.
then maximum Alternating \space Sum = \max(S, S + 2 \cdot (|A_j|_{max} - |A_i|_{min}))

# TIME COMPLEXITY:

O(N) for each test case.

# SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
#define ll long long int
using namespace std;

void solve(){
int n;
cin>>n;
vector<ll> a(n);
ll sum = 0;
ll mini = INT_MAX, maxi = INT_MIN;

for(int i = 0; i < n; i++){
cin>>a[i];
if(i % 2 == 0){
sum = sum + abs(a[i]);
mini = min(mini, abs(a[i]));
}
else {
sum = sum - abs(a[i]);
maxi = max(maxi, abs(a[i]));
}
}

cout<<max(sum, sum + 2LL* (maxi - mini))<<"\n";

}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)solve();
return 0;
}

Tester's Solution
#include<bits/stdc++.h>
using namespace std ;

#define ll              long long
#define pb              push_back
#define all(v)          v.begin(),v.end()
#define sz(a)           (ll)a.size()
#define F               first
#define S               second
#define INF             2000000000000000000
#define popcount(x)     __builtin_popcountll(x)
#define pll             pair<ll,ll>
#define pii             pair<int,int>
#define ld              long double

template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; }

#ifdef LOCAL
#define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 2401
#endif

long long readInt(long long l,long long r,char end){
long long x = 0;
int cnt = 0;
int first =-1;
bool is_neg = false;
while(true) {
char g = getchar();
if(g == '-') {
assert(first == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if(cnt == 0) {
first = g - '0';
}
++cnt;
assert(first != 0 || cnt == 1);
assert(first != 0 || is_neg == false);

assert(!(cnt > 19 || (cnt == 19 && first > 1)));
}
else if(g == end) {
if(is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
string ret = "";
int cnt = 0;
while(true) {
char g = getchar();
assert(g != -1);
if(g == end) {
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){
}
}
}

int _runtimeTerror_()
{
int mx_N = 0, mn_N = 1e6, sum_N = 0;
for(int i=1;i<=T;++i) {
vector<vector<int>> g(2);
amax(mx_N, N);
amin(mn_N, N);
sum_N += N;
ll ans = 0;
for(int i=1;i<=N;++i) {
int x;
if(i != N) {
}
else {
}
g[i & 1].push_back(abs(x));
if(i & 1) {
ans += abs(x);
}
else {
ans -= abs(x);
}
}

sort(all(g[0])), sort(all(g[1]));
ans = max(ans, ans + 2 * g[0].back() - 2 * g[1][0]);
cout << ans << "\n";
}
cerr << T << " " << mn_N << " " << mx_N << " " << sum_N << "\n";
assert(sum_N <= 2e5);
assert(getchar() == -1);
return 0;
}

int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef runSieve
sieve();
#endif
#ifdef NCR
initncr();
#endif
int TESTS = 1;
//cin >> TESTS;
while(TESTS--) {
_runtimeTerror_();
}
return 0;
}


can i get the test cases for the problem
i wrote the code below although it is matching the normal test cases but still giving wrong ans please helpš„

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void swap (int a, int b, int[] mainArr){
int t = mainArr[a];
mainArr[a] = mainArr[b];
mainArr[b] = t;
}
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0)
{
int min=Integer.MAX_VALUE;
int max=Integer.MIN_VALUE;
int mi=0;
int ma=0;
int sum=0;
int size=sc.nextInt();
int a[]=new int[size];
for(int i=0;i<size;i++)
{
a[i]=sc.nextInt();
}
for(int i=0;i<size;i++)
{
a[i]=Math.abs(a[i]);
}
for(int i=0;i<size;i=i+2)
{
if(min>a[i])
{
min=a[i];
mi=i;
}
}
for(int i=1;i<size;i=i+2)
{
if(max<a[i])
{
max=a[i];
ma=i;
}
}

swap(ma,mi,a);
for(int i=0;i<size;i=i+2)
{
sum=sum+a[i];
}
for(int i=1;i<size;i=i+2)
{
sum=sum-a[i];
}
System.out.println(sum);

}
}
}


1
3
4 1 4

Take this input Your code giving output 1
But the actual output is 7 ā +4-1+4=7

2 Likes

i performed the correct algorithm, and iām getting correct answer for every of my own test cases.

can anyone point out, why my code is showing WA in the submission.

using namespace std;

int main(){
int t;
cin >> t;
while(t--){
int N;
cin >> N;
if(N>1){
int nums[N];
for(int i=0;i<N;i++){
int k;
cin >> k;
nums[i] = abs(k);
}

//algorithm

//storing highest negative as negatived index a neg, similarly for positive
int pos=0,neg=1;
for(int i=0;i<N;i++){
//for positive, storing the positve index on the array
if( i %2 == 0){
if(nums[i] < nums[pos]){
pos = i;
}
}
else{
if(nums[i] > nums[neg]){
neg = i;
}
}
}

//calculating initial sum
int sum_i=0;
for(int i=0;i<N;i++){
if(i%2==0){
sum_i += nums[i];
}
else{
sum_i -= nums[i];
}
}

//swapping the highest negative with lowest positive in the array itself.
int temp=0;
temp = nums[pos];
nums[pos] = nums[neg];
nums[neg] = temp;

//calculating the optimized sum
int sum=0;
for(int i=0;i<N;i++){
if(i%2==0){
sum += nums[i];
}
else{
sum -= nums[i];
}
}
cout<<max(sum,sum_i)<<endl;
}
else{
//if only one element
int k;
cin >> k;
cout << k<<endl;
}
}

}

Same here!

Can anyone please tell me whatās wrong with this code? It worked for the testcases given in the question but failed in the submission.

import math
t = int(input())
for _ in range(t):
n = int(input())
arr = list(map(int,input().split()))
arr = list(map(abs,arr))
ans = 0
m1,m2 = -1,-1
mi = sorted(list(arr[::2]),reverse=True)
ma = sorted(list(arr[1::2]))
for i,j in zip(ma,mi):
if i>j:
arr.remove(i)
arr.remove(j)
m1 = j
m2 = i
break

for i,j in enumerate(arr):
if i%2==0:
ans+= j
else:
ans -= j
if not (m1==-1 or m2==-1):
ans+=(m2-m1)
print(ans)


Thanks.

#include <iostream>
#include <climits>
#include <cstdlib>
using namespace std;
long n;
long idx1, idx2;
long long mx, mn, sum;
void swap(long long a[], long id1, long id2)
{
long long  temp = a[id1];
a[id1] = a[id2];
a[id2] = temp;
}
int main()
{
int t;
cin >> t;
while (t--)
{
mx = -1;
mn = 1000000007;
sum = 0;
cin >> n;
long long a[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
if (a[i] < 0)
a[i] = abs(a[i]);
if ((i % 2) != 0)
{
if (a[i] > mx)
{
mx = a[i];
idx1 = i;
}
}
else
{
if (a[i] < mn)
{
mn = a[i];
idx2 = i;
}
}
}
if (n == 2)
{
sum = a[0] - a[1];
}
else
{
if (mn < mx)
swap(a, idx1, idx2);
for (int j = 0; j < n; j++)
{
if (j % 2 != 0)
sum -= a[j];
else
sum += a[j];
}
}
cout << sum << endl;
}
return 0;
}


Can anyone tell me why this code is not passing for 3rd test case

Since, -10^9 \leq A_i \leq 10^9, alternating sum may not fit in int. You have to use long long, to avoid overflow.

@deathcrate @phantom1sa
You also did the same mistake. You have to use long in java.

    if(n == 2){
sum = a[0] - a[1];
}


Only this part is wrong.
it shoud be,

    if(n == 2){
if(a[0] > a[1]) sum = a[0] - a[1];
else sum = a[1] - a[0];
}


Also, the way you solved it, you need not to handle n = 2 exceptionally. Your else part is capable of handling it.

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
vector<int> a(n);

for(int i = 0; i < n; i++)
{
int x;
cin >> x;
a[i] =  abs(x);
}

int max_odd = a[1];                                      //finding the maximum number at odd position
int idx1 = 0;
for(int i = 1; i < n; i = i + 2)
{
if(a[i] >= max_odd) {
max_odd = a[i];
idx1 = i;
}
}

int min_even = a[0];                                   //finding the minimum number at even position
int idx2 = 0;
for(int i = 0; i < n; i = i + 2)
{
if(a[i] <= min_even) {
min_even = a[i];
idx2 = i;
}
}

swap(a[idx1], a[idx2]);                             //swapping the two numbers found

int i = 0;
ll res = 0;
while(i < n)                                             //calculating according to the question given
{
if(i%2 == 0)
{
res = res + a[i];
}
else
{
res = res - a[i];
}
i++;
}
cout << res << endl;
}

return 0;


}

/* package codechef; // donāt place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be āMainā only if the class is public. /
class plusle
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t,n,i,min,max,sum;
t=sc.nextInt();
while(t>0)
{
n=sc.nextInt();
int a[]=new int[n];
sum=0;
min=Integer.MAX_VALUE;
max=Integer.MIN_VALUE;
for(i=0;i<n;i++)
{
a[i]=sc.nextInt();
if(i%2==0)
{
sum+=Math.abs(a[i]);
min=Math.min(min,Math.abs(a[i]));
}
else
{
sum-=Math.abs(a[i]);
max=Math.max(max,Math.abs(a[i]));
}
}
System.out.println(Math.max(sum,sum+2
(max-min)));
tā;
}
}
}

/* package codechef; // donāt place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be āMainā only if the class is public. /
class plusle
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t,n,i,min,max,sum;
t=sc.nextInt();
while(t>0)
{
n=sc.nextInt();
int a[]=new int[n];
sum=0;
min=Integer.MAX_VALUE;
max=Integer.MIN_VALUE;
for(i=0;i<n;i++)
{
a[i]=sc.nextInt();
if(i%2==0)
{
sum+=Math.abs(a[i]);
min=Math.min(min,Math.abs(a[i]));
}
else
{
sum-=Math.abs(a[i]);
max=Math.max(max,Math.abs(a[i]));
}
}
System.out.println(Math.max(sum,sum+2
(max-min)));
tā;
}
}
}

    ans+=(m2 - m1)


It is wrong.
It should be:

    ans+=2*(m2 - m1)


I donāt know much about python. This is the only mistake i can spot.

@dr1p @deathcrate
You have to use at most one operation.
It means you have two choices. Either perform no operation or one operation.
But, you are always performing one operation.
For some cases, doing swaps will decrease initial alternating sum.

1 Like

in my code i m trying to find the maximum negative number and smallest positive number and this code is passing all my test cases including sample test cases but gives wrong answer on submission ,plz tell the error

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t--)
{
long long n,maxs=INT_MIN,mins=INT_MAX,l=0,h=0,sum=0;
cin>>n;
long long arr[n];
for(long long i=0;i<n;i++)
{
cin>>arr[i];
}
for(long long i=1;i<n;i+=2)//for finding maximum number which is being subtracted
{
if(abs(arr[i])>maxs)
{
maxs=abs(arr[i]);
l=i;
}
}
for(long long i=0;i<n;i+=2)// for finding smallest number which is being added
{
if(abs(arr[i])<mins)
{
mins=abs(arr[i]);
h=i;
}
}
if(abs(arr[l])!=abs(arr[h]) && l<h)
swap(arr[h],arr[l]);
long long c=0;
for(long long i=0;i<n;i++)
{
sum+=pow(-1,c)*abs(arr[i]);
c++;
}
cout<<sum<<endl;
}
return 0;
}


Hey @deathcrate, No the test cases are hidden for a reason. It is done so that the candidate is forced to think of all the ways their code can fail and handle those cases. The sample cases are only to make the understanding of the problem clear for the candidate.

Hey, your code is completely alright except for the part that you have used int data type instead of long long due to which overflow is occurring. Using long long data type will solve this problem

Your code fails on the case when n = 2 and a[0] < a[1]
In this case you should have swapped a[0] with a[1] but your code hasnāt handled it.

putting

        if (n == 2) {
sum = abs(a[0] - a[1]);
}


will work.

thanks a lot, it worked now for all test cases

You can refer my code in cpp. I donāt Know much about java. Here is my code:
#include<bits/stdc++.h>
#define flash ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long int
using namespace std;

void solve(){

int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
if(a[i]<0)
a[i]*=-1;
}
int pi,ni,mnm=1000000001,mxm=0;
for(int i=0;i<n;i++){
if(i%2==0){
if(a[i]<=mnm){
mnm=a[i];
pi=i;
}
}
else{
if(a[i]>=mxm){
mxm=a[i];
ni=i;
}
}
}
int sum=0;
for(int i=0;i<n;i++){
if(i==pi and a[pi]<a[ni])
sum-=a[pi];
else if(i==ni and a[pi]<a[ni])
sum+=a[ni];
else if(i%2==0)
sum+=a[i];
else
sum-=a[i];
}
cout<<sum<<"\n";


}

int32_t main(){

flash;
int tc;
cin>>tc;
while(tc--)
{
solve();
}
`

}