PROBLEM LINK:
Author and Editorialist: Ritesh Gupta
Tester: Encho Mishinev
DIFFICULTY:
EASY
PREREQUISITES:
Sorting, STL
PROBLEM:
You are given two arrays A and B of length N. You can apply swap operations on them. In one operation, you can select two integers i and j(1 \le i,j \le N), and swap A_i and B_j, and the cost of this operation is minimum of A_i and B_j.
You have to find the minimum cost to make the two arrays identical where two arrays are said to be identical if for each element x, the frequency of x in both the array is the same.
QUICK EXPLANATION:
- Let’s create a frequency array f which contains the frequency of elements of both the array A and B. Now if for any valid i, f_i is odd then we can say that there is no way to distribute i between two arrays, so the answer is -1.
- We can say that if x is a minimum element and we want to swap A_i and B_j for some valid i and j then there are two ways to do that:
- direct swap – swap (A_i,B_j) and cost is $min(A_i, B_j)
- using minimum element – first swap (A_i,x) and then swap (B_j, x) or vice-versa and cost is 2*x.
EXPLANATION:
We can be sure that if any number occurs odd times in array A and even times in array B or vice versa then the answer is -1 as their cumulative frequency is odd, otherwise, the answer always exists.
Now, we have to minimize the total cost to make the sequences identical. Let’s say there exist indices i, j such that they need to be swapped, and there exists a minimum element k among all elements of A and B, then we can swap A_i and B_j in two ways: Either swap A_i and B_j directly, or swap A_i and B_j using two swaps with the help of k (i.e., swap A_i with k, and then swap k with B_j or vice-versa).
If we swap A_i and B_j directly, the cost will be min(A_i, B_j) else the cost will be 2*k. So, in a case 2*k<min(A_i, B_j), we’ll swap A_i and B_j using two swaps with the help of k else we’ll swap A_i and B_j directly in order to minimize the cost of operations performed. So, we can say that after we finish swapping A_i and B_j, k will again be in its original place. Would this give the minimum cost? Can we make it better?
In case of indirect swaps(two swaps through k), we can either choose A_i to be the minimum element of A and B_j to be the maximum element of B or A_i to be the maximum element of A and B_j to be the minimum element of B, such that A_i and B_j both need to be swapped. This is the optimal way to minimize the total cost incurred in case of direct swaps.
TIME COMPLEXITY:
TIME: O(NlogN)
SPACE: O(NlogN)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int32_t main()
{
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
vector <int> v1,v2;
int x;
map <int,int> m;
for(int i=0;i<n;i++)
{
cin >> x;
m[x]++;
v1.push_back(x);
}
for(int i=0;i<n;i++)
{
cin >> x;
m[x]--;
v2.push_back(x);
}
bool flag = false;
v1.clear();
v2.clear();
int mi = x;
for(auto i:m)
{
mi = min(mi, i.first);
x = abs(i.second);
if(x%2)
flag = true;
x = i.second;
if(x > 0)
{
x /= 2;
while(x--)
v1.push_back(i.first);
}
else if(x < 0)
{
x = abs(x)/2;
while(x--)
v2.push_back(i.first);
}
}
if(flag)
{
cout << -1 << endl;
continue;
}
reverse(v2.begin(),v2.end());
int ans = 0;
for(int i=0;i<v1.size();i++)
ans += min(2*mi,min(v1[i],v2[i]));
cout << ans << endl;
}
}
Tester's Solution
#include <iostream>
#include <stdio.h>
#include <map>
#include <set>
#include <vector>
using namespace std;
typedef long long llong;
int t;
int n;
int a[200111];
int b[200111];
map<int, int> A;
map<int, int> B;
void update(map<int, int> &M, map<int, int> &AUX, int num)
{
auto it = M.find(num);
if (it == M.end())
{
it = AUX.find(num);
if (it == AUX.end())
AUX.insert(make_pair(num, 1));
else
(it->second)++;
}
else
{
(it->second)--;
if (it->second == 0)
M.erase(it);
}
}
int main()
{
int i,j;
int test;
scanf("%d", &t);
for (test=1;test<=t;test++)
{
int minv = -1;
A.clear();
B.clear();
scanf("%d", &n);
for (i=1;i<=n;i++)
{
scanf("%d", &a[i]);
if (minv == -1 || a[i] < minv)
minv = a[i];
}
for (i=1;i<=n;i++)
{
scanf("%d", &b[i]);
if (b[i] < minv)
minv = b[i];
}
for (i=1;i<=n;i++)
{
update(A, B, b[i]);
update(B, A, a[i]);
}
vector<int> pushA, pushB;
bool bad = false;
for (auto it=A.begin();it!=A.end();it++)
{
if (it->second % 2 == 1)
bad = true;
for (j=1;j<=(it->second)/2;j++)
{
pushA.push_back(it->first);
}
}
for (auto it=B.begin();it!=B.end();it++)
{
if (it->second % 2 == 1)
bad = true;
for (j=1;j<=(it->second)/2;j++)
{
pushB.push_back(it->first);
}
}
if (bad)
{
printf("-1\n");
continue;
}
llong ans = 0;
for (int i = 0; i < pushA.size(); i++)
{
ans += (llong)min(2*minv, min(pushA[i], pushB[ (int)pushB.size() - 1 - i ]));
}
printf("%lld\n", ans);
}
return 0;
}
