MAJIK - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: still_me
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

2105

PREREQUISITES:

Sorting

PROBLEM:

You have an array A of length N.
At most P times, you can replace two elements of A by their sum.
At most Q times, you can replace two elements of A by their signed difference.

Let B be the final array you obtain. What’s the maximum possible value of \max(B) - \min(B)?

EXPLANATION:

If N = 1, the answer is of course 0, so we focus on N\gt 1.

Let \text{mn} denote the initial minimum element of A, and \text{mx} denote the initlal maximum.
A move is good if it either increases \text{mx}, or decreases \text{mn}, because that’s how we increase the distance between them.

Consider some element x of A.

  • If x \gt 0, we can increase \text{mx} by x using an addition operation, or decrease \text{mn} by x using a subtraction operation.
  • If x \lt 0, the exact opposite applies: we can increase \text{mx} by x using a subtraction operation, or decrease \text{mn} by x using an addition operation.
  • If x = 0 what we do doesn’t matter anyway.

Notice that no matter whether x is positive or negative, we can always have it contribute to the answer using an addition or a subtraction operation.

In particular, an element x allows us to increase the ‘separation’ between minimum and maximum, by |x|.
We can do this with at most P+Q elements, so clearly it’s best to choose the ones whose absolute value is large as possible.

This leads to a greedy solution: take the absolute values of all elements other than \text{mn} and \text{mx} into an array, sort them, and take the sum of the largest P+Q of them.
Of course, the array has only N-2 elements so the number of chosen elements is \min(P+Q, N-2) instead.

If the sum found above is S, the answer is simply S + \text{mx} - \text{mn}.

TIME COMPLEXITY

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

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    p, q = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    ans = a[-1] - a[0]
    b = []
    for i in range(1, n-1): b.append(abs(a[i]))
    b.sort()
    for i in range(min(p+q, n-2)): ans += b[-1-i]
    print(ans)
3 Likes
3

Thanks for Editorial. Why can’t the case be where we incerase the seperation using newly created element or using mn or mx? I’m neither getting intution nor able to prove that using the newly created elements won’t help. Please help me.

2 Likes
4

One way to see it, is that each ‘newly created element’ is itself a combination of additions/subtractions of some of the initial elements.
As in, you might have some element that looks like A_2 - A_5 - A_7 + A_8 - A_1 + A_{23} - \ldots

If you want to use this in a future move, you could just as well have not created it, and used each of its individual parts one by one (adding/subtracting as appropriate) right?
You can see that the number of moves used stays the same either way.

1 Like
5

Thank You, This helps!