ZCO16001 - Editorial

editorial
, ,
1

PROBLEM LINK

ZCO16001

DIFFICULTY

Easy

PREREQUISITES

Logic

PROBLEM IN SHORT

Given two arrays, by doing a maximum of k swaps between them, reduce the sum of the maximum element of the two arrays.

SOLUTION

The key observation in this problem is that the maximum number between the two arrays will
always be included in the sum. This is because, however many swaps you do, it will still be a part
of either of the arrays.

Building up on this, we first choose an array that should contain the biggest element. Now the array
containing this biggest element should have all the other large elements. This is because the other
elements of the array won’t be part of the sum.

Hence, we simply swap the largest element from the other array with the smallest element of this
array, if it is bigger. We do this upto k times.

This can be done by sorting the two arrays (say big and small), and maintaining two pointers,
bigPt, and smallPt. Initially, bigPt = 0, & smallPt = n - 1. Now, after ever swap of big[bigPt] and
small[smallPt], bigPt is incremented by 1, and smallPt is decreased by 1.

Finally, once this is done - we sort the arrays once again, and big[n - 1] + small[n - 1] is the
solution.

TIME COMPLEXITY

O(n log n) for sorting, and O(n) for swaps, which means the overall time complexity is O(n log n).

EDITORIALIST’s SOLUTION

#include <bits/stdc++.h>
using namespace std;

int n, k;

int solve(vector<int> big, vector<int> small) {
	int ck = k;
	int smallPt = n - 1;
	int bigPt = 0;
	while (ck > 0) {
		if (big[bigPt] >= small[smallPt])
			break;
		else if(bigPt >= n || smallPt < 0)
			break;
		else {
			ck--;
			swap(big[bigPt], small[smallPt]);
			bigPt++;
			smallPt--;
		}
	}
	sort(big.begin(), big.end());
	sort(small.begin(), small.end());	
	return big[n - 1] + small[n - 1];
}

int main() {
	vector<int> a, b;
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		a.push_back(x);
	}
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		b.push_back(x);
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	printf("%d", min( solve(a, b), solve(b, a) ) );
	return 0;
}