ARRSWAP - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: rkyouwill
Testers: iceknight1093, tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Sorting

PROBLEM:

You have two arrays A and B. In one move, you can swap any element of A with any element of B.
Find the minimum possible value of \max(A) - \min(A) that you can attain.

EXPLANATION:

The fact that any element of A can be swapped with any element of B is quite powerful; in fact, we can pick any N integers out of the 2N we have and put them in A.

Proof

If A already contains the N integers we want, nothing more needs to be done.

Otherwise, B contains one such integer, and A contains one integer we don’t want.
Swap these two, and continue.

Now, let C be an array of size 2N containing all the elements of A and B.
Let’s sort C, so C_1 \leq C_2 \leq \ldots \leq C_{2N}.

To minimize the difference, it’s clearly optimal to choose N consecutive elements from this sorted C.
That is, if the smallest element we pick is C_i, then it’s optimal to pick the elements \{C_i, C_{i+1}, \ldots, C_{i+N-1}\}; giving us a difference of C_{i+N-1} - C_i

There are N+1 choices for the smallest element: C_1, C_2, \ldots, C_{N+1}.
Try each one, compute the appropriate maximum element (C_{i+N-1}), and take their difference.
The final answer is the minimum difference among all these.

TIME COMPLEXITY:

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

CODE:

Code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = sorted(a + b)
    print(min(c[i] - c[i-n+1] for i in range(n-1, 2*n)))
2

I am questioning your solution. In the case where A = 20 85 4 95 7 and B = 77 3 65 8 20, I believe the min difference between Amax and Amin is 16, instead of the result your code produces, 17.
The resultant A would be 4 7 8 20 20. Which has a lower delta than 3 4 7 8 20.

Am I misreading the problem statement? In your solution, you state, ‘Try each one’, but in your code, you do not ‘try each one’. You only are comparing the first array and the last array, not any of those in between.
Thanks.
ps. here is the code I used and get 16 as a result:
for _ in range(int(input())):
n = int(input())
a = list(map(int,input().split()))
# your code:
#b = list(map(int, input().split()))
#c = sorted(a + b)
#print(min(c[n-1] - c[0], c[-1] - c[n]))
#print(c)
a += list(map(int,input().split()))
a.sort()
testm = list(zip(a,a[n-1:]))
mindelta = [(y-x) for x,y in testm]
print(min(mindelta))

2 Likes
3

Oh, you’re right, I accidentally pasted testing code in instead of correct code.
It’s fixed now.

4

Thanks for letting me know.