MXALT - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Sorting

PROBLEM:

You’re given an array A. Find any rearrangement of A such that the alternating sum

A_1 - A_2 + A_3 - A_4 + \ldots + (-1)^{N+1}A_N

is maximized.

EXPLANATION:

Observe that the elements placed at indices 1, 3, 5, 7, \ldots will be added to the alternating sum, while elements at indices 2, 4, 6, \ldots will be subtracted from it.

Our aim is to maximize the alternating sum, so ideally ‘large’ elements should be added and ‘small’
elements should be subtracted.
This gives rise to a straightforward approach: place the largest \left\lceil \frac{N}{2} \right\rceil elements at the odd indices, and the remaining elements at the even indices.

Even more simply, the answer is simply the sum of the larger half of the elements, minus the sum of the smaller half of the elements (if N is odd, the middle element is added).
This can easily be computed by just sorting the array A.

TIME COMPLEXITY:

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

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()

    half = n//2
    ans = 0
    for i in range(half): ans -= a[i]
    for i in range(half, n): ans += a[i]
    print(ans)