CHFNSWPS - Editorial

PROBLEM LINK:

Division 1
Division 2

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

for video reference : Chefina and Swaps

12 Likes

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

2 Likes

Can anyone please help me to find out the mistake in my code.
It is only partially running.
code link is :- https://www.codechef.com/viewsolution/35545452
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> readValues(){
    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;
	    multiset<int> a  = readValues(),b = readValues();
	    
	    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.
code link: https://www.codechef.com/viewsolution/35605994

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 :slight_smile:
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[0],b[0]) , 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
Can anyone please help me with what I’m missing?

Maybe this will help in visualizing what question asks

6 Likes