ZCO16001 - Editorial

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;
}

why wouldnt this function work??
ll func(ll B[],ll S[],ll n,ll k)
{
ll pt1=0,pt2=n-1;
while(k-- && pt2>=0 && pt1<n && S[pt2]>B[pt1])
{
ll temp=S[pt2];S[pt2]=B[pt1];B[pt1]=temp;
pt2–; pt1++;
}
sort(S,S+n); sort(B,B+n);
return S[n-1]+B[n-1];
}

after doing atmost k swaps b/w ele of array a & b
let final desired answer be skew = u + v, where u & v are largest ele of their respective array

:exclamation: keep i mind, here i am explaining with help of array ds (assuming 1-based indexing)

driving force 1
Initially 
let x be the largest ele of array a 
let y be the largest ele of array b 
driving force 2
let x > y ,, then we claim that x will be either u or v
driving force 3
now lets make 2 cases, but before that sort the arrays a & b  
for case 1 answer be ans1 ,, for case 2 answer be ans2 
our final answer will be min(ans1,ans2)
driving force 4
case 1: never swap a[n] with any ele in b,  also we know a[n] = x 
    let l =1,
    ShiftSwap(a,b)
        throw the largest ele of the array b, (i.e. b[n]) out of array,, after this size of b reduces to n -1 
        insert the a[l] in the desired place in the sorted array b    ,, after this size of b agains increments to  n   
        increment l(i.e. l++)
        ans1 = min(ans1, a[n]+b[n])
        swap successful

perform this subroutine k times (as long as u are successfully able to knock largest ele(b[n]) of b outside & introducing a smallest ele(a[l]) in the array b )
:exclamation: keep in mind a[l] should be less than b[n] why :question:(to get optimized swap)

driving force 5
case 2: swap a[n] with smallest ele(i.e. b[1]) of b,  also we know x = a[n]
        again sort array a & b (as while swapping a[n] & b[1] we may get unsorted array)
    follow same subroutine with argument exchanged  ShiftSwap(b,a)  this time atmost k-1 swaps as one swap we did in line above 
    we get ans2 
driving force 6
we got our answer = min(ans1,ans2)
if you find some typo pls acknowlege, i'll be happy to improve it 
driving force 7
 u may work with this test case to get confidence in the technique described above 
3 1
0 2 7 
1 3 5
ans = 9 , ans ≠ 10