My Solution fails for last Task. I am not able to identify the mistake in it.
cost can be greater than 10^9 , so your int gets overflowed
1 Like
Bhai reverse bhi kar 2nd vector ko
Bhai vector 2 reverse Karne Par shi chal raha hai tera code.Ye try kar
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int compare(const void *a, const void *b){
const ll* x=(ll*) a;
const ll * y=(ll*) b;
if(*x>*y) return 1; // qsort(a,n,sizeof(ll),compare);
else if(*x<*y) return -1;
return 0;
}
/*
1
8
1 2 2 2 4 5 5 5
1 2 3 3 4 5 6 6
*/
void solve(){
ll n;
cin>>n;
ll arr[n],arr2[n],arr3[2*n],mini;
for(ll i=0;i<n;i++){
cin>>arr[i]; arr3[i]=arr[i];
}
for(ll i=0;i<n;i++){
cin>>arr2[i]; arr3[i+n]=arr2[i];
}
qsort(arr,n,sizeof(ll),compare);
qsort(arr2,n,sizeof(ll),compare);
qsort(arr3,2*n,sizeof(ll),compare);
mini=min(arr[0],arr2[0]);
ll same=0;
for(ll i=0;i<n;i++) if(arr[i]==arr2[i]) same++;
if(same==n){
printf("0\n"); return ;
}
for(ll i=0;i<2*n;i++){
if((i&1) && arr3[i]!=arr3[i-1]){
printf("-1\n"); return ;
}
}
ll c=0;
vector<ll>v,v2;
for(ll i=0;i<n;i++){
if(arr[i]!=arr2[i]){
v.push_back(arr[i]);
v2.push_back(arr2[i]); i++;
c++;
}
}
sort(v.begin(),v.end());
sort(v2.begin(),v2.end());
reverse(v2.begin(),v2.end());
// for(ll i=0;i<v2.size()/2;i++) swap(v2[i],v2[v2.size()-i-1]);
ll sum=0;
for(ll i=0;i<v.size();i++){
if(mini*2<min(v[i],v2[i])) sum+=(2*mini);
else if(v[i]<v2[i]) sum+=v[i];
else sum+=v2[i];
}
printf("%lld\n",sum);
return ;
}
int main(){
ll t,z=1;
scanf("%lld",&t);
while(z<=t){
solve(); z++;
}
return 0;
}
/*
3
1
1
2
2
1 2
2 1
2
1 1
2 2
*/
/*
1 2 1 2 1 2 1 2
3 4 3 4 3 4 3 4
1 1 2 2 3 3 4 4
1 1 2 2 3 3 4 4
*/
Hey, but I thought that the minimum cost is considered only when the elements are swapped between two sequences. It was not written that the min cost can be considered even in the same sequence. How have you people come to this notion of swapping with the min element??
1 Like
Always happy to help 
Have you considered the case where you can get minimum cost by swapping both the elements with minimum element among both the arrays? Because I got the same result when I didnāt consider this case.
Bro, yea code WA de raha hai. Even if the second vector is reversed.
U need to optimise Ur code further. Every sort takes nearly O(Nlog(N)) time and you are also using loops. There are few shortcuts to solve it in python. Check out my code:-
content://com.mi.android.globalFileexplorer.myprovider/external_files/chefina%20and%20swaps.
i am getting partial marks bt i am unable to find any mistake.
help
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define endl "\n"
#define pb push_back
#define mp make_pair
#define ut unsigned int
#define ss second
#define ff first
#define vi vector<int>
#define vl vector<ll>
#define lb lower_bound
#define up upper_bound
#define re return
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t ;
cin >> t;
while(t--)
{
ll n,i,j,ans=0,flag=0,r=0,mini=0;
cin>>n;
vl a,b,v1,v2; // vector<ll,ll>
map<ll,ll>m;
for(i=0;i<n;i++){
cin>>j;
m[j]++;
a.pb(j);
}
for(i=0;i<n;i++){
cin>>j;
m[j]--;
b.pb(j);
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());
mini=min(a[0],b[0]);
//cout<<mini<<" ";
for(auto &x : m){
if(x.ss%2!=0){
flag=1;
break;
}
}
if(flag==1)
cout<<"-1"<<endl;
else{
for(i=0;i<n;i++){
if(a[i]!=b[i]){
if(m[a[i]]!=0)
v1.pb(a[i]);
if(m[b[i]]!=0)
v2.pb(b[i]);
}
}
reverse(v2.begin(),v2.end());
r=v1.size();
for(i=0;i<r;i=i+2){
ans=ans+min(2*mini,min(v1[i],v2[i]));
}
cout<<ans<<endl;
}
}
return 0;
}
i took all the values in map and check whether any values are odd the print the -1.
after that i created two array which will be balanced array. i took array A and store all element which is excess or should not be present in that array. and done same thing with array B. lets call them array notneedA and notneedB. i sort both the array and sum all values min(notneedA[i],notneedB[i]) and sum is answer.
https://www.codechef.com/viewsolution/35363936
where i am going wrong?
Got it bro!!. The mistake was whenever arr[i]!=arr2[i], I was pushing both elements to the vectors. Instead we should push only the element which we need to swap!. But anyway, thanks for replying and helping 
.
Hereās the code
1 Like
Always happy to help
I am so noob that I couldnāt think about the āusing the minimum numberā for swaps. 
No it is not necessary ,each swaps(Ai,Bj) will reduce the count of A[i] by 1
Hi, iām not getting AC for my java code. Can someone please help me out with this ?
My Solution:
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- != 0){
int n = sc.nextInt();
long[] a = new long[n];
long[] b = new long[n];
//Scanning both arrays
for(int i=0; i<n; i++)
a[i] = sc.nextLong();
for(int i=0; i<n; i++)
b[i] = sc.nextLong();
//Sorted both input arrays
Arrays.sort(a);
Arrays.sort(b);
int aidx = 0, bidx = 0, count = 0;
//mma(MismatchArray A), mmb (MismatchArray B) to store mismatch elements
ArrayList<Long> mma = new ArrayList<Long>();
ArrayList<Long> mmb = new ArrayList<Long>();
while(aidx<n && bidx<n){
if(a[aidx]==b[bidx]){aidx++;bidx++;count++;}
else if(a[aidx]<b[bidx])
mma.add(a[aidx++]);
else mmb.add(b[bidx++]);
}
while(aidx<n)
mma.add(a[aidx++]);
while(bidx<n)
mmb.add(b[bidx++]);
//Count represent matching elements, (n-count) represent count of mismatch elements
count = n - count;
long sum = 0;
//if count (of mismatch) is odd OR mismatch arrays differ in size, print -1
if(count % 2 == 1 || mma.size()!=mmb.size())System.out.println("-1");
else if(count == 0)System.out.println("0");
else {
boolean flag = false;
//using stacks to verify whether each element is present even number of times.
Stack<Long> s1 = new Stack<Long>();
Stack<Long> s2 = new Stack<Long>();
s1.push(mma.get(0));
s2.push(mmb.get(0));
for(int i = 1; i<mma.size(); i++)
if(!s1.isEmpty() && s1.peek() == mma.get(i))
s1.pop();
else s1.push(mma.get(i));
for(int i = 1; i<mmb.size(); i++)
if(!s2.isEmpty() && s2.peek() == mmb.get(i))
s2.pop();
else s2.push(mmb.get(i));
//both stacks are empty, which means both mma, mmb are valid
// ai : minimum of ith element of mma & ith element from last of mmb
//a0 : minimum of a[0], b[0] * 2
if(s1.isEmpty() && s2.isEmpty()){
for (int i = 0; i < count; i += 2){
long ai = Math.min(mma.get(i), mmb.get(count - i - 1));
long a0 = Math.min(a[0], b[0])*2;
sum += Math.min(ai, a0);
}
System.out.println(sum);
}
else
System.out.println("-1");
}
}Can someone please tell me whatās wrong in this code:
test=int(input())
for k in range(0,test):
N=int(input())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
dictA={}
dictB={}
for num in A:
if num not in dictA:
dictA[num]=1
else:
dictA[num]+=1
for num in B:
if num not in dictB:
dictB[num]=1
else:
dictB[num]+=1
cost=0
minimum=min(min(A,B))
A.sort(reverse=True)
B.sort(reverse=True)
count={}
for key in dictA.keys():
if key in dictB:
diff=dictA[key]-dictB[key]
count[key]=diff
else:
diff=dictA[key]
count[key]=diff
if diff%2!=0:
cost=-1
for key in dictB.keys():
if key not in count:
diff=-dictB[key]
count[key]=diff
if diff%2!=0:
cost=-1
elementsA=[]
elementsB=[]
for j in range(0,N):
if count[A[j]]!=0 and (A[j] not in elementsA):
elementsA.append(A[j])
for j in range(0,N):
if count[B[j]]!=0 and (B[j] not in elementsB):
elementsB.append(B[j])
flag=1
if cost!=-1:
while (len(elementsA)!=0 and len(elementsB)!=0) and flag==1 :
while count[minimum]!=0:
if count[minimum]>0:
cost+=minimum
count[minimum]-=2
count[elementsB[0]]+=2
if count[minimum]==0:
elementsA=elementsA[:-1]
if minimum in elementsB:
elementsB=elementsB[:-1]
if count[elementsB[0]]==0:
if elementsB[0] in elementsA:
del elementsA[elementsA.index(elementsB[0])]
elementsB=elementsB[1:]
else:
cost+=minimum
count[minimum]+=2
count[elementsA[0]]-=2
if count[minimum]==0:
elementsB=elementsB[:-1]
if minimum in elementsB:
elementsA=elementsA[:-1]
if count[elementsA[0]]==0:
if elementsA[0] in elementsB:
del elementsB[elementsB.index(elementsA[0])]
elementsA=elementsA[1:]
flag=0
for value in count.values():
if value!=0:
flag=1
if flag!=0:
while elementsA!=[] and elementsB!=[]:
if elementsA[-1]<elementsB[-1]:
if elementsA[-1]<=2*minimum:
cost+=elementsA[-1]
else:
cost+=2*minimum
count[elementsA[-1]]-=2
count[elementsB[0]]+=2
if count[elementsB[0]]==0:
#del elementsA[elementsA.index(elementsB[0])]
elementsB=elementsB[1:]
if count[elementsA[-1]]==0:
#del elementsB[elementsB.index(elementsA[-1])]
elementsA=elementsA[:-1]
elif elementsA[-1]==elementsB[-1]:
if count[elementsA[-1]]>0:
if elementsA[-1]<=2*minimum:
cost+=elementsA[-1]
else:
cost+=2*minimum
count[elementsA[-1]]-=2
count[elementsB[0]]+=2
if count[elementsB[0]]==0:
elementsB=elementsB[1:]
if count[elementsA[-1]]==0:
elementsA=elementsA[:-1]
elementsB=elementsB[:-1]
else:
if elementsB[-1]<=2*minimum:
cost+=elementsB[-1]
else:
cost+=2*minimum
count[elementsB[-1]]+=2
count[elementsA[0]]-=2
if count[elementsA[0]]==0:
elementsA=elementsA[1:]
if count[elementsB[-1]]==0:
elementsB=elementsB[:-1]
elementsA=elementsA[:-1]
else:
if elementsB[-1]<=2*minimum:
cost+=elementsB[-1]
else:
cost+=2*minimum
count[elementsB[-1]]+=2
count[elementsA[0]]-=2
if count[elementsA[0]]==0:
#del elementsB[elementsB.index(elementsA[0])]
elementsA=elementsA[1:]
if count[elementsB[-1]]==0:
#del elementsA[elementsA.index(elementsB[-1])]
elementsB=elementsB[:-1]
else:
break
print(cost)I got 2nd test case wrong and many others TLE.