PMA - Editorial

PROBLEM LINK:

Practice
Div-4 Contest
Div-3 Contest
Div-2 Contest
Div-1 Contest

Author: Agamya Yadav
Tester: Anshu Garg

DIFFICULTY:

SIMPLE

PREREQUISITES:

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 readString(int l,int r,char end){
    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){
    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,' ');
}


int _runtimeTerror_()
{
    int T = readIntLn(1, 1e5);
    int mx_N = 0, mn_N = 1e6, sum_N = 0;
    for(int i=1;i<=T;++i) {
    	vector<vector<int>> g(2);
    	int N = readIntLn(2, 1e5);
    	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) {
    			x = readIntSp(-1e9, 1e9);
    		}
    		else {
    			x = readIntLn(-1e9, 1e9);
    		}
    		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];
                }
            }
            //printing out the answer
            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.

Can you please help me find why this code didnā€™t pass all the testcases? Thankyou!

#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;

}

Please help! My code is getting rejected again and again.
/* 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ā€“;
}
}
}

Please help! My code is getting rejected every time.
/* 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();
}

}