CHFNSWPS - Editorial

shadow08 · July 15, 2020, 11:29am

Can any one help me with my code.Please

void swap(int a[],int b[]){
int temp=*a;
*a=*b;
*b=temp;
}

int main(){

int t;
cin>>t;
while(t--){
	
	int n,c=-1,sum=0;
	cin>>n;
	int a[n],b[n];
	
	
	for(int i=0;i<n;i++)
	cin>>a[i];
	for(int i=0;i<n;i++)
	cin>>b[i];
	sort(a,a+n);
	sort(b,b+n);
	int w=min(a[0],b[0]);
	
	
	for(int i=0,j=0;i<n,j<n;){
		int k1=-1,c1,c2,k2=-1;
		if(a[i]==b[j]){
			i++;
			j++;
		}
		else
		{
			 c1=i+1;
			 c2=j+1;
			while(c1<n&&c2<n){
				if(a[i]==a[c1]){
					swap(b+j,a+c1);
				    k1=min(a[c1],b[j]);
				    break;
				}
				if(b[j]==b[c2]){
					swap(b+c2,a+i);
					k2=min(a[i],b[c2]);
					break;
				}
				
				c1++;
				c2++;	
			}
		
            if(k1==-1&&k2==-1){
		    	sum=k1;
		    	break;
			}
			else
	        sum+=min(w,max(k1,k2));
	    	i++;
	    	j++;
			}
	}
	cout<<sum<<endl;
}

}

gauravsahu34 · July 15, 2020, 1:22pm

Video Editorial for the solution is:

satwik_2000 · July 15, 2020, 2:32pm

can anyone help me in finding out the flaw in my code
I dont even have full set of test cases,i used the same logic as in the editorial.

my code goes here.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll abs(map<ll,ll>::iterator itr)
{
if(itr->second>=0)
return(itr->second);
else
return(-itr->second);
}
int main()
{
//#ifndef ONLINE_JUDGE
//freopen(“in.txt”,“r”,stdin);
//freopen(“pooc.txt”,“w”,stdout);
//#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
for(ll i=0;i<t;i++)
{
map<ll,ll> m,ma,mb;
ll n;
cin>>n;
for(ll i=0;i<n;i++)
{
ll data;
cin>>data;
map<ll,ll>::iterator itr=ma.find(data);
if(itr==ma.end()){
ma.insert(pair<ll,ll>(data,1));
mb.insert(pair<ll,ll>(data,0));
}
else if(itr!=ma.end())
{
itr->second++;
}
}
for(ll i=0;i<n;i++)
{
ll data;
cin>>data;
map<ll,ll>::iterator itr=mb.find(data);
if(itr==mb.end()){
mb.insert(pair<ll,ll>(data,1));
ma.insert(pair<ll,ll>(data,0));
}
else if(itr!=mb.end())
{
itr->second++;
}
}

ll sum=0;
map<ll,ll>::iterator itr1=ma.begin();
map<ll,ll>::iterator itr2=mb.begin();
for(;itr1!=ma.end();itr1++)
{
    m.insert(pair<ll,ll>((itr1->first),((itr1)->second-itr2->second)));
    itr2++;

}
map<ll,ll>::iterator itr=m.begin();
while(itr!=m.end() && itr->second%2==0)
{

    sum=sum+itr->second;
    itr++;
}
if(sum!=0 || itr->second%2!=0){
    cout<<"-1"<<endl;
    sum=100000;
}
if(sum==0)
{
    for(itr=m.begin();itr->second==0 && itr!=m.end();itr++)
    {}
    ll ans=0;
    if(itr==m.end())
        cout<<"0"<<endl;

    if(itr!=m.end())
    {
       map<ll,ll>::iterator itr1,itr2;
       itr1=m.begin();
       for(itr1;itr1->second==0;itr1++)
       {}
     ll value=itr1->first;
       itr2=m.end();


       while(itr2!=m.begin() && itr1!=m.end())
       {
        
         if((itr1->second)*(itr2->second)<0)
         {

            if(abs(itr1)>abs(itr2)  )
            {
                if(min(itr1->first,itr2->first)<(2*value)){

                ans=ans+(min(itr1->first,itr2->first)*(min(abs(itr1->second),abs(itr2->second))/2));
                }
                else{

                ans=ans+((value*2)*(min(abs(itr1->second),abs(itr2->second))/2));
                }
                itr1->second=itr1->second+itr2->second;
                itr2->second=0;
                itr2--;

              }
            else if(abs(itr2)>abs(itr1) )
            {
                  if(min(itr1->first,itr2->first)<(2*value)){
                ans=ans+(min(itr1->first,itr2->first)*(min(abs(itr1->second),abs(itr2->second))/2));
                  }
                else{
                ans=ans+((value*2)*(min(abs(itr1->second),abs(itr2->second))/2));
                }
                itr2->second=itr2->second+itr1->second;
                itr1->second=0;
                itr1++;

            }
            else if(abs(itr1)==abs(itr2))
            {

                  if(min(itr1->first,itr2->first)<(2*value)){

                ans=ans+(min(itr1->first,itr2->first)*(min(abs(itr1->second),abs(itr2->second))/2));
                  }
                else{

                ans=ans+((value*2)*(min(abs(itr1->second),abs(itr2->second))/2));
                }
                itr2->second=0;
                itr1->second=0;
                itr1++;
                itr2--;

            }
        }

            else if(itr1==itr2)
            {
                if(itr1->second>0)
                    itr2--;
                else if(itr1->second<0)
                    itr1++;
            }
           else if(itr1->second<0){
              itr1++;

           }
            else if(itr2->second>0){
                itr2--;
            }
            else if(((itr1->second)*(itr2->second))==0){
             if(itr1->second==0){
                itr1++;
             }
            if(itr2->second==0){
               itr2--;
            }
            }

         }
        
         cout<<ans<<endl;
     }



    }

}

return(0);
}

pigeon9 · July 16, 2020, 8:43pm

you can check my code.
Its same as explained in the editorial
https://www.codechef.com/viewsolution/35716114

xxiamharixx · July 18, 2020, 2:38pm

https://www.codechef.com/viewsolution/35747391

May I know why its showing runtime and WA error?

kwatra · July 20, 2020, 10:03am

please tell me the test case on which my code is giving wrong

https://www.codechef.com/viewsolution/35602068

g_himanshu0100 · July 24, 2020, 6:33pm

showing wrong answer
please help

#include
#include
#include
#include
using namespace std;
int main(){
long long t{};
cin>>t;
vector result{};
for(long long i{};i<t;i++){

    long long n{},counts1{},counts2{};
    cin>>n;
    vector<long long> a{};
    vector <long long> b{};
    vector <long long> final{};
    for(long long j{};j<n;j++){
        long long c{};
        cin>>c;
        a.push_back(c);
        final.push_back(c);}
    for(long long j{};j<n;j++){
        long long c{};
        cin>>c;
        b.push_back(c);
        final.push_back(c);}
    
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    sort(final.begin(),final.end());
    long long x{};
    for(long long unsigned int j{};j<final.size();j=j+2){
        if(final[j]!=final[j+1]){
            x=1;
            result.push_back(-1);}}
            
            if(x==0){
            vector<long long> inter;
            set_intersection(a.begin(), a.end(),
             b.begin(), b.end(),
             back_inserter(inter));


            a.erase(set_difference(a.begin(), a.end(),
                    inter.begin(), inter.end(),
                    a.begin()),
            a.end());


            b.erase(set_difference(b.begin(), b.end(),
                    inter.begin(), inter.end(),
                    b.begin()),
            b.end());

            sort(a.begin(),a.end());
            sort(b.begin(),b.end());
            if(a.size()==0 and b.size()==0)
                result.push_back(0);
            else{    
            vector <long long> posa{};
            vector <long long> posb{};
            for(long long unsigned int j{};j<a.size();j=j+2){
                posa.push_back(a[j]); 
                posb.push_back(b[j]);}         
            
            for(long long unsigned int j{};j<posa.size();j++){
                counts1 = counts1 + min(posa[j],posb[j]);}
            reverse(posb.begin(),posb.end());
            for(long long unsigned int j{};j<posa.size();j++){
                counts2 = counts2 + min(posa[j],posb[j]);}
            
            if(counts1>counts2)
                result.push_back(counts2);
            else
                result.push_back(counts1);}  
    }

}
for(long long c:result)
cout<<c<<endl;
}

ameybhavsar · July 24, 2020, 8:11pm

Share a link to submission or format your code. This is difficult to read.

g_himanshu0100 · July 24, 2020, 8:17pm

please help saying wrong answer for 2 test cases

#include
#include<bits/stdc++.h>
#include
#include
using namespace std;
int main(){
long long t{};
cin>>t;
vector result{};
for(long long i{};i<t;i++){

    long long n{},counts{};
    cin>>n;
    vector<long long> a{};
    vector <long long> b{};
    vector <long long> final{};
    for(long long j{};j<n;j++){
        long long c{};
        cin>>c;
        a.push_back(c);
        final.push_back(c);}
    for(long long j{};j<n;j++){
        long long c{};
        cin>>c;
        b.push_back(c);
        final.push_back(c);}
    
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    sort(final.begin(),final.end());
    long long x{};
    for(long long unsigned int j{};j<final.size();j=j+2){
        if(final[j]!=final[j+1]){
            x=1;
            result.push_back(-1);}}
            
            if(x==0){
                vector<long long> c{a};
                vector<long long> d{b};
            vector<long long> inter;
            set_intersection(a.begin(), a.end(),
             b.begin(), b.end(),
             back_inserter(inter));


            a.erase(set_difference(a.begin(), a.end(),
                    inter.begin(), inter.end(),
                    a.begin()),
            a.end());


            b.erase(set_difference(b.begin(), b.end(),
                    inter.begin(), inter.end(),
                    b.begin()),
            b.end());
            

            sort(a.begin(),a.end());
            sort(b.begin(),b.end());
            reverse(b.begin(),b.end());
            
            if(a.size()==0 and b.size()==0)
                result.push_back(0);
            else{ 
                   
                    long long k{min(c[0],d[0])},mins1{-1},mins2{-1};
                    c.clear();
                    d.clear();
                    for(long long j{};j<a.size();j++)
                    {if(a[j]==a[j+1])
                            {c.push_back(a[j]);
                            j=j+1;}
                        else
                            c.push_back(a[j]);}
                    for(long long j{};j<b.size();j++)
                    {if(b[j]==b[j+1])
                            {d.push_back(b[j]);
                            j=j+1;}
                        else
                            d.push_back(b[j]);} 
                    
                   long long unsigned int sizes{c.size()};
                    while(sizes!=0){
                        
                        mins1=min(2*k,min(c[0],d[0]));
                        mins2=min(2*k,min(c[c.size()-1],d[d.size()-1]));
                        if(mins1>mins2){
                        counts=counts+mins1;
                        c.erase(c.begin()); 
                        d.erase(d.begin());}
                        else{
                            counts=counts+mins2;
                            c.erase(c.begin()+c.size()-1); 
                            d.erase(d.begin()+d.size()-1);
                        }
                        sizes=sizes-1;}
                        result.push_back(counts);}  
           
    }

}
for(long long c:result)
cout<<c<<endl;
}

ameybhavsar · July 24, 2020, 8:21pm

Consider the test case

3
1 59 59
1 123 123

Correct Answer:

2

Your answer:

59

Steps:

Swap 1 with 123.
Swap 1 with 59.

Remember: cost is min(a,b) where a and b are being swapped.

chenreddy · July 24, 2020, 8:45pm

I understood that the greedy move(picking maximum unused element from first array and minimum unused element from the second array) is a safe step(i.e., will lead to a optimal solution) when we allow only the direct swaps. Can someone please explain to me why the greedy move remains the same for direct swaps even when indirect swaps are introduced?

shivamgarg210 · August 2, 2020, 7:17am

Can someone tell the problem in below code ?

#include
#include <stdio.h>
#include
#include
#include
#define MAX 200005
using namespace std;

long long a[MAX], b[MAX];

int main()
{
int t;
cin>>t;

while(t--)
{
	int n;
	cin>>n;

	long long mn = 10^9 + 7;
	map<long long, long long> m1, m2;

	for(int i=0; i<n; i++)cin>>a[i],mn=min(mn,a[i]),m1[a[i]]++;
	for(int i=0; i<n; i++)cin>>b[i],mn=min(mn,a[i]),m2[b[i]]++;

    vector<long long> v1,v2;
    int flag=1;

    map<long long, long long>::iterator itr;
    for(itr=m1.begin();itr!=m1.end();++itr)
    {
        long long x = itr->first;
        int y = itr->second;

        if((y+m2[x])%2 != 0){flag=0;break;}

        if(y>m2[x])
        {
           for(int j=0; j<(y-m2[x])/2; j++)v1.push_back(x);
        }
    }
    for(itr=m2.begin();itr!=m2.end();++itr)
    {
        long long  x = itr->first;
        int y = itr->second;

        if((y+m1[x])%2 != 0){flag=0;break;}

        if(y>m1[x])
        {
           for(int j=0; j<(y-m1[x])/2; j++)v2.push_back(x);
        }
    }
    if(flag==0)
    {
        printf("-1\n");
        continue;
    }

    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());

    long long a1=0,a2=0,ans;
    int i=0,j=v2.size()-1;
    while(i<v1.size() && j >=0)
    {
        a1 = a1 + min(min(v1[i],v2[j]), 2*mn);
        i++;
        j--;
    }
    i=v1.size()-1;j=0;
    while(i>=0 && j<v2.size())
    {
        a2 = a2 + min(min(v1[i],v2[j]), 2*mn);
        i--;
        j++;
    }
    ans = min(a1, a2);

	printf("%lld\n", ans);
}
return 0;

}

cchinmaya0 · August 23, 2020, 11:46am

#include <bits/stdc++.h>

using namespace std;
long int t,x;
int main() {
long int i;
cin>>t;
for(x=1;x<=t;x++ )
{long int n;
cin>>n;
long long int a[n],b[n],small=1000000000;

for(i=0;i<n;i++)
{
 cin>>a[i];  if(small>a[i]){small=a[i];} 
}
for(i=0;i<n;i++)
{
 cin>>b[i];   
}

  sort(a,a+n);sort(b,b+n);
  
  
    long long temp,min,cost1=0,cost2=0,cost=0;
  for(i=0;i<n-1;i++)
  {
      if(a[i]!=b[i])
      {
          if(a[i+1]==a[i]&&b[i+1]==b[i])
          {
              if(a[i]<b[i])
              {
                  temp=a[i+1];min=a[i];
                  a[i+1]=b[i];
                  b[i]=temp;
              }
              else if(a[i]>b[i])
              {
                  temp=a[i];min=b[i];
                  a[i]=b[i+1];
                  b[i+1]=temp;
              }i=i+1;cost1=cost1+min;
              cost2=cost2+(2*small);
             
              if(cost1>=cost2)
              {cost=cost2;}
              else
              {
                  cost=cost1;
              }
              
          }
          else {cost=-1;break;}
      }
  }
  
  if(n==1)
  {if(a[i]==b[i])
      cout<<"0\n";
      else 
      cout<<"-1\n";
  }
  
  else cout<<cost<<"\n";
    
}






return 0;

}

this my code i am not able to understand whats wrong with it…my submission gives all wrong answers but my logic and implementation is correct

atish1999 · September 19, 2020, 6:46am

Can anyone tell me why am I getting TLE in this approach?

import java.util.*;
import java.io.*;
public class Chefina_and_swaps {

	static int mod = (int) (1e9 + 7);
	public static void main(String[] args) throws java.lang.Exception
    {		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t=Integer.parseInt(br.readLine());
		while(t-->0) {
			int n=Integer.parseInt(br.readLine()),checkOdd=0;
			long min=mod;
			StringTokenizer st=new StringTokenizer(br.readLine());
			Map<Long, Integer> a=new TreeMap<>(),b=new TreeMap<>();
			for(int i=0; i<n; i++) {
				long x=Integer.parseInt(st.nextToken());
				checkOdd^=x;
				a.put(x, a.getOrDefault(x, 0)+1);
				min=Math.min(min, x);
			}
			st=new StringTokenizer(br.readLine());
			for(int i=0; i<n; i++) {
				long x=Integer.parseInt(st.nextToken());
				checkOdd^=x;
				b.put(x, b.getOrDefault(x, 0)+1);
				min=Math.min(min, x);
			}
			if(checkOdd!=0) {System.out.println(-1); continue;}
			if(a.equals(b)) {System.out.println(0);continue;}
			List<Long> A=new ArrayList<>(),B=new ArrayList<>();
//			Removing pair of common elements from a and b 
			for(Long x: a.keySet()) {
				if(b.containsKey(x)) {
					int d=Math.min(a.get(x), b.get(x));
					a.put(x, a.get(x)-d);
					b.put(x, b.get(x)-d);
				}
			}
			for(Long x: a.keySet()) for(int i=0; i<a.get(x)/2; i++) A.add(x);
			for(Long x: b.keySet()) for(int i=0; i<b.get(x)/2; i++) B.add(x);
//			As we are using treeMap then keys will be sorted
			Collections.reverse(B);
			long cost=0;
			for (int i = 0; i < A.size(); i++) cost+=Math.min(2*min, Math.min(A.get(i), B.get(i)));
			System.out.println(cost);
		}
		System.out.flush();

	}
	
}

rahulmysuru7 · September 19, 2020, 6:49am

you need to answer each test-case in O(1) time complexity, but your solution is taking O(n) or even higher complexity.

atish1999 · September 19, 2020, 6:52am

how can I optimize that? please help.

rahulmysuru7 · September 19, 2020, 6:54am

Once read the editorial completely and go through the setter’s and tester’s solution.

atish1999 · September 19, 2020, 7:27am

thanks ,this time my solution got accepted.