It works for all test cases. But submission verdict is WA.
Can anyone help finding the mistake?
`from collections import Counter
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ac=Counter(a)
bc=Counter(b)
weird=(ac-bc)+(bc-ac)
temp=list(weird.values())
sumi=0
i=0
try:
while(i<len(temp)):
if(temp[i]%2==0):
sumi+=temp[i]
else:
raise Exception
i+=1
except Exception as e:
sumi=-1
if(sumi/4==sumi//4):
print(sumi//4)
else:
print(-1)`
Link to original solution: CodeChef: Practical coding for everyone
You are just swapping the minimum unbalanced element with the maximum unbalanced element in both the arrays so that you can take min value as the cost for balancing 2 operations.
There is an operation which can cost lesser.
Through another path. That is the minimum element. For example A is 0 1 1 B is 0 2 2
Min operation will be with swapping with 0. Ans is 0.
Swap 0 and 2 , then swap 0 and 1. Cost = 0
Check this snippet for optimal path for swaps
m is the minimum element, for going through this path, m needs to be swapped twice, so that it returns to its original array.
while(count>0)
{
ll swap= itr->second;
ll val= itr->first;
if(swap>count)
swap=count;
itr++;
if(swap*val <= m* swap*2)
sum+= swap*val;
else
sum+= m*swap*2;
count-= swap;
}