 # CHFNSWPS - Editorial

Author and Editorialist: Ritesh Gupta
Tester: Encho Mishinev

EASY

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: 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;
int b;

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;

for (auto it=A.begin();it!=A.end();it++)
{
if (it->second % 2 == 1)

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)

for (j=1;j<=(it->second)/2;j++)
{
pushB.push_back(it->first);
}
}

{
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;
}
``````
22 Likes

for video reference : Chefina and Swaps

12 Likes

Is there anyway to solve the question using frequency of array elements.??

2 Likes

It is only partially running.
After this code I also took the fast input output and cleared the vectors after the use was over but it was not working.

6 Likes

Can anybody please tell me why my Python code is giving TLE for the last two test cases ?
I have tried almost everything from fast I/O but still getting the same time limit exceed error…
https://www.codechef.com/viewsolution/35454334

was there a different solution for the smaller subtask ?

``````#include <bits/stdc++.h>
using namespace std;
int possible,n;
multiset<int> s;
int num;
for(int i=0;i<n;i++){
cin >> num;
s.insert(num);
possible^=num;
}
return s;
}
int main() {
int t;
cin >> t;
while(t--){
cin >> n;
possible = 0;

int min_element = min(*a.begin(),*b.begin());

if(possible==0){
vector<int> r;
for(auto i : b){
auto it = a.find(i);
if(it==a.end()){
r.push_back(i);
}
else{
a.erase(it);
}
}
for(auto i : a){
r.push_back(i);
}
sort(r.begin(),r.end());
int len = r.size();

long long ans = 0;
for(int i=0;i<len/2;i+=2){
ans+=min(2*min_element,r[i]);
}
cout << ans;
}
else{
cout << -1;
}
cout << '\n';
}
}``````
1 Like

Aslaam Alaikum Waqar bro
for every swap is it neccesarry that elements becomes equal on both sides

1 Like

my solution

1 Like

can anyone help me why i’m getting wrong ans for this code and could also tell some optimizations for it.

Aren’t we suppose to make A[i]=b[i] as question says ?
" two sequences with length N as identical if, after they are sorted in non-decreasing order, the ii-th element of one sequence is equal to the ii-th element of the other sequence for each ii (1≤i≤N1≤i≤N)"

Here’s my solution if you want to check -

Hope this helps 1 Like

try this test case:
8
2 2 3 3 3 3 4 4
2 2 2 2 6 6 6 6
min ans=8 ,while your code giving 9

1 Like

fir=min(a,b) , and reverse the vector d because you are swaping minimum elements of both array.

can anybody provide a solution in c? My code got tle for the last test case and I couldn’t solve the problem. Thanks in advance.

sorry , I didn’t understand your question , can you elaborate a bit more.

Here’s my soln-

``````#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
bool isZero (int i)
{
return i == 0;
}
int main() {
int t;
cin>>t;

while(t--){
long long int n,f=1,c1=0,z=0;
cin>>n;
std::vector<long long int> a;
std::vector<long long int> b;
for (int i = 0; i < n; i++) {
long long int x;
cin>>x;
a.push_back(x);
z=z^x;
}
for (int i = 0; i < n; i++) {
long long int y;
cin>>y;
b.push_back(y);
z=z^y;
}
if(z !=0){
cout<<-1<<endl;
f=-1;
}
if(f!=-1){
sort(a.begin(),a.end());
sort(b.begin(),b.end());
long long int i=0,lo=0;long long int c=lo;
if(a[i]==b[i])
{
lo=a[i];
}
else{
lo =min(a[i],b[i]);
}
lo=2*lo;
i=0;
vector<long long int> v(a.size() +b.size());
vector<long long int>::iterator it, st;

it = set_symmetric_difference(a.begin(),
a.end(),
b.begin(),
b.end(),
v.begin());

std::vector<long long int>::iterator newIter = std::remove_if( v.begin() ,v.end() , isZero);
v.resize( newIter -  v.begin() );

sort(v.begin(),v.end());

c1=0;
for (int i = 0; i < v.size()/2 ; i+=2)
{
c1+=min(lo,v[i]);

}
cout<<c1<<endl ;
}
}	return 0;
}
``````

I implemented the solution in C++ and don’t know what’s wrong in it. I took input in 2 arrays, combined both in 3rd array, sorted all 3 arrays, then checked for every odd index in arr3, the element of that index should match with previous index element, if it dosen’t match then answer is -1. Further I looped over to check if arr1[i]!=arr2[i], if yes then pushed arr[i] in v vector and arr2[i] in v2 vector. Then I sorted v2 vector in non-ascending order, then looped over the 2 vectors (as size of both are equal) by checking if (min form arr1 &arr2)2 is less than min(v[i],v2[i]) if yes, then sum+=min2 else sum+=min(v[i],v2[i]);
It works well in many of my trial tests but gives WA while submission.
Here the code