APLUSB - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh_07
Tester: mridulahi
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Sorting

PROBLEM:

You’re given arrays A and B, both of length N.
Find any rearrangement of both arrays such that A_i + B_i = A_j + B_j for any 1 \leq i\lt j\leq N, or say that no such rearrangement exists.

EXPLANATION:

Our task is essentially to pair up each element of A with some element of B, such that the sums of the elements in each pair are the same.

If this were possible at all, the only choice is to pair up the smallest element of A with the largest element of B, the second smallest of A with the second largest of B, and so on.

Proof

Let A and B both be sorted, i.e, A_1 \leq A_2 \leq\ldots\leq A_N and B_1 \leq B_2 \leq\ldots\leq B_N.

Our claim is that if a solution exists, then A_i should be paired with B_{N+1-i} for every i.
First, suppose A_1 is paired with B_x, where x \lt N.
Then, observe that B_N must be paired with some A_i such that i \gt 1.
However in that case,
A_1 \leq A_i and B_x \leq B_N, so A_1 + B_x \leq A_i + B_N

Further, the only way the last inequality actually becomes an equality, is if A_1 = A_i and B_x = B_N; meaning A_1 could’ve been paired up with B_N anyway (B_x = B_N, after all).

Now that A_1 is paired up to B_N, remove them from consideration and you’re left with two arrays of length N-1, simply keep repeating this argument on it to prove the claim (a more formalized version of this is to use induction).

This leads to a simple implementation.
Sort the array A in ascending order, and B in descending order.
Then, check if all the A_i + B_i values are the same. If yes, you already have valid rearrangements; and if not, no solution exists.

TIME COMPLEXITY:

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

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n; cin >> n;
    vector <int> a(n);
    for (auto &x : a) cin >> x;
    vector <int> b(n);
    for (auto &x : b) cin >> x;

    sort(a.begin(), a.end(), greater<int>());
    sort(b.begin(), b.end());

    vector <int> c(n);
    for (int i = 0; i < n; i++) c[i] = a[i] + b[i];
    sort(c.begin(), c.end());

    if (c[0] != c.back()){
        cout << -1 << "\n";
        return;
    }
    for (auto x : a) cout << x << " ";
    cout << "\n";
    for (auto x : b) cout << x << " ";
    cout << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = sorted(list(map(int, input().split())))
    b = sorted(list(map(int, input().split())))[::-1]
    c = [a[i] + b[i] for i in range(n)]
    if min(c) == max(c):
        print(*a)
        print(*b)
    else:
        print(-1)