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