ALT - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: ro27
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Sorting

PROBLEM:

For an array A of even length N, its alter ego array B is obtained by doing the following:

  • For each 1 \leq i \leq \frac{N}{2}, insert A_i + A_{i+\frac{N}{2}} and |A_i - A_{i+\frac{N}{2}}| into B, at some position.

You’re given B. Find an array A with maximum sum such that B is the alter ego array of A, or claim that none exist.

EXPLANATION:

Let’s work on a really simply case first: N = 2.
So, we’re given (x+y) and |x-y| (as B_1 and B_2), and we want to find if there exist integers x and y that satisfy them.
This is not too hard, with some simple algebra.
If x\geq y (so that |x-y| = (x-y)), note that (x+y) + (x-y) = 2x and (x+y) - (x-y) = 2y.

However, we want x and y to be integers - which is only possible if (x+y)+(x-y) is even; that is (x+y) and (x-y) have the same parity.
That is, a solution exists if and only if B_1 and B_2 have the same parity.

For N \gt 2, notice that we can do something pretty similar.
A_1 and A_{1+\frac{N}{2}} can be found by picking two elements of the same parity from B and applying the above construction to them.
Similarly we can find A_2 and A_{2+\frac{N}{2}}, A_3 and A_{3+\frac{N}{2}}, and so on.

The only way we’ll be able to get all N elements however, is if we’re able to keep pairing up elements of the same parity like this.
In other words, a solution exists if and only if:

  • There are an even number of even elements in B; and
  • There are an even number of odd elements in B.

Since N is even, one of the above conditions being true is enough to guarantee the other one as well.
So, count the number of even and odd elements in B; and if they’re odd, no solution exists and the answer is -1.
Otherwise, a valid array A does exist - now, we need to figure out how to maximize its sum.

Let’s deal with only the even elements for now; the odd elements can be dealt with similarly.
Suppose there are 2k even elements, say E_1, E_2, \ldots, E_{2k}
Let’s also assume they’re sorted, so that E_i \leq E_{i+1}.

Recall that if we pair up E_i and E_j, the resulting elements of A we get are \frac{E_i + E_j}{2} and \frac{E_i - E_j}{2}.
Their sum is just E_i; meaning E_j gets functionally ignored.

So, we can essentially choose k out of these 2k elements of E, and have their sum contribute to the sum of A.
Since we aim to maximize the sum of A, clearly the optimal strategy is to just pick the k largest elements of E, that is E_{k+1}, E_{k+2}, \ldots, E_{2k}.
Each of these can be paired up with one of the first k elements, any such pairing will be optimal.

Do the same thing for the odd elements, and we’re done.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Author's code (C++) 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<class T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// order_of_key(a)  -> gives index of the element(number of elements smaller than a)
// find_by_order(a) -> gives the element at index a
#define accelerate ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int        long long int
#define ld         long double
#define mod1       998244353
#define endl       "\n"
#define ff         first
#define ss         second
#define all(x)     (x).begin(),(x).end()
#define ra(arr,n)  vector<int> arr(n);for(int in = 0; in < n; in++) {cin >> arr[in];}


const int mod = 1e9 + 7;
const int inf = 1e18;
int MOD(int x) {int a1 = (x % mod); if (a1 < 0) {a1 += mod;} return a1;}
// int N = 1e8;
// vector<int>yep(N + 1, true);
// void sieve() {
//     yep[0] = yep[1] = false;
//     for (int i = 2; i <= N; i++) { if (yep[i] && i * i <= N) {for (int j = i * i; j <= N; j += i) {yep[j] = false;}}}
// }
vector<int>v;
int power( int a,  int b) {
    int p = 1; while (b > 0) {if (b & 1)p = (p * a); a = (a * a)  ; b >>= 1;}
    return p;
}


void lessgoo()
{
    int n;
    cin >> n;
    ra(arr, n);
    if (n % 2 != 0) {
        cout << -1 << endl;
        return;
    }
    sort(all(arr), greater<int>());
    vector<int>even, odd;
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 == 0)even.push_back(arr[i]);
        else odd.push_back(arr[i]);
    }
    vector<int>ans(n, 0);
    int e = even.size();
    int o = odd.size();
    if (e % 2 != 0 && o % 2 != 0) {
        cout << -1 << endl;
        return;
    }
    int k = 0;
    for (int i = 0; i < e / 2; i++) {
        int a = (even[i] + even[i + e / 2]) / 2;
        int b = even[i] - a;
        ans[k] = a;
        ans[k + n / 2] = b;
        k++;
    }
    for (int i = 0; i < o / 2; i++) {
        int a = (odd[i] + odd[i + o / 2]) / 2;
        int b = odd[i] - a;
        ans[k] = a;
        ans[k + n / 2] = b;
        k++;

    }
    // cout << e << " " << o << endl;
    for (auto x : ans) {
        cout << x << " ";
    }
    cout << endl;





}


signed main()
{
    accelerate;

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif


    int test = 1;
    cin >> test;
    for (int tcase = 1; tcase <= test; tcase++)
    {
        // cout << "Case #" << tcase << ": ";

        lessgoo();

    }
    return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    evens, odds = [], []
    for x in map(int, input().split()):
        if x%2: odds.append(x)
        else: evens.append(x)
    if len(evens)%2:
        print(-1)
        continue
    a1, a2 = [], []
    for a in [sorted(odds), sorted(evens)]:
        for i in range(len(a)//2):
            x, y = a[i], a[-1-i]
            a1.append((x+y)//2)
            a2.append(abs(x-y)//2)
    print(*a1, *a2)
1 Like