CKMNMX - EDITORIAL

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Pranjul Pal
Tester: Sonali Singh
Editorialist: Pranjul Pal

DIFFICULTY:

Medium

PREREQUISITES:

Binary Search

PROBLEM:

Given two arrays A and B of length N. You need to find the minimum number of operations required to satisfy the condition that minimum value of array A should be at least as much as the maximum value of array B.
And in one operation, we can increase or decrease value of any element of any array by 1.

QUICK EXPLANATION:

You can solve the problem :

  • By using the fact that optimal values are attainable at the array values

EXPLANATION:

Claim: f is convex :

Instead of proving it formally, try checking the property on many random test cases. You will realize that f is convex.

Proof:

It is fairly easy to prove. See the derivative of f.

= — (# of elements of b > k) + (# of elements of a < k)

The first term (without sign) can only decrease as k increases whereas second term can only increase as k increases.

So,

  • By using the fact that optimal values are attainable at the array values :

All the extremum points will lie in the elements from the any of the arrays because f is convex and at the event points (or the points of array A and B).

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ln "\n"
#define pb push_back
#define pll pair<ll,ll>
#define ppll pair<ll,pll>
#define vll vector<ll>
#define vpll vector<pll>
#define vvll vector<vector<ll>>
#define sll stack<ll>
#define qll queue<ll>
#define mp make_pair
#define f first
#define s second
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define Test ll t;cin>>t; while(t--)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define init(x,n,v) for(ll i=0;i<=n;i++) x[i]=v;
#define all(x) x.begin(),x.end()
ll MOD = 1e9+7 , MAX = 1e18;
int main() 
{
	fast_io;
	ll n,m,i,ans=MAX;
	map<ll,ll> mp;
	cin>>n>>m;
	vll a(n),b(m),ap(n+1,0),bp(m+1,0);
	for(auto &i: a) cin>>i , mp[i]=1;
	for(auto &i: b) cin>>i , mp[i]=1;
	sort(all(a)) , sort(all(b),greater<ll>());
	for(i=1;i<=n;i++) ap[i]=ap[i-1]+a[i-1];
	for(i=1;i<=m;i++) bp[i]=bp[i-1]+b[i-1];
	for(auto k: mp)
	{
	    ll p1=ub(all(a),k.f)-a.begin();
	    ll p2=ub(all(b),k.f,greater<ll>())-b.begin();
	    ans=min(ans,max(p1*k.f-ap[p1],0ll) + max(bp[p2]-p2*k.f,0ll));
	}
	cout<<ans;
	return 0;
}