P4149 - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given an array A. In one move, you can multiply two of its elements by -1.
Maximize the sum of A.

EXPLANATION:

Since in each move we multiply exactly two elements by -1, after several moves we can certainly multiply any even number of elements by -1.
Further, it can be seen that there’s no way to multiply an odd number of elements by -1.

Why?

Suppose an operation is performed on indices (i, j).
Then,

  • If i and j are both not negated, they both become negated.
    The number of negated elements increases by 2.
  • If i and j are both already negated, they both become not negated.
    The number of negated elements decreases by 2.
  • If i is negated and j is not (or vice versa), they swap states.
    The number of negated elements doesn’t change.

So, after an operation, the number of negated elements changes by +2/0/-2.
Given that we start at 0, it’s impossible to reach an odd number.

Now, ideally we’d like to turn negative elements positive, and not turn positive elements negative.
So,

  • If there are an even number of negative elements, they can all be made positive, and this is optimal.
  • If there are an odd number of negative elements, we have two choices:
    1. Leave one negative element aside, and turn all the others positive.
      Here, of course we leave the largest one aside: for example if A = [-1, -2, -3] then we turn it to [-1, 2, 3] and leave -1 aside.
    2. Turn all the negative elements positive, while also operating on one non-negative element (if it exists).
      For example, when A = [-100, 1], it’s optimal to turn it into [100, -1].
      Here, it’s easy to see that the chosen non-negative element should be as small as possible.

When there are an odd number of negative elements, try both cases and take the maximum of them.
Each case is easily simulated in \mathcal{O}(N) time - you only need to find all negative elements, and then know either the largest among them or the smallest among the remaining elements.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
	ll tt=1;
    cin>>tt;
    while(tt--){
        ll n;
        cin>>n;
        ll a[n];
        ll flag=0;
        ll o=0;
        ll sum=0;
        ll mini=1e9;
        for(int i=0;i<n;i++){
            cin>>a[i];
            sum+=abs(a[i]);
            mini=min(mini,abs(a[i]));
            if(a[i]==0){
                flag=1;
            }
            if(a[i]<0){
                o++;
            }
        }
        if(flag || o%2==0){
            cout<<sum<<"\n";
        }else{
            sum-=2*mini;
            cout<<sum<<"\n";
        }
    }
}
Tester's code (C++) 
//Har Har Mahadev
#include<bits/stdc++.h>
#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 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 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;
}
 
void solve()
{
    int n;
    cin >> n;
    vi a(n);
    take(a,n);
    int cnt = 0;
    repin{
    	if(a[i] < 0)cnt++;
    }
    for(auto &x : a)x = abs(x);
    sort(be(a));
	if(cnt&1)a[0]*=-1;
	int sm = 0;
	for(auto x : a)sm += x;
	cout << sm << '\n';

}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifdef NCR
        init();
    #endif
    #ifdef SIEVE
        sieve();
    #endif
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = sorted(list(map(int, input().split())))
    ans = sum(a)
    for i in range(0, n-1, 2):
        ans -= a[i] + a[i+1]
        ans += max(a[i] + a[i+1], -a[i] - a[i+1])
    print(ans)
1 Like