PROBLEM LINK:
Drona and his Greatest Warrior
Author: artha6391
Tester: artha6391
Editorialist: devansheegupta
DIFFICULTY:
Easy
PREREQUISITES:
Greedy
PROBLEM:
The problem wants us to find the smallest number of swaps needed to make Arjun win in every input case and accordingly print that smallest number as output.
QUICK EXPLANATION:
The approach is first we sort both array and we will iterate second array from last and first array form first till we get sum1 > sum2. After swapping if sum1 < sum2 print -1, and if sum1 > sum2 print count of swapping, else print 0.
EXPLANATION:
First of all, let’s see what happens when we swap two integers from different multisets. Let’s call sum of elements of the first multiset before swap SA_1 . Similarly we can define SB_1. Let’s call integer that will be deleted from the first multiset x. Let’s call integer that will be deleted from the second multiset y. So new sum of elements of the first multiset will be SA_1 - x + y and new sum of elements of the second multiset will be SB_1 - y + x.
Since we want sum of elements of the first multiset to be greater than sum of elements of the second multiset it’s always profitable to swap the smallest integer from the first multiset with the biggest integer from the second multiset. Let’s prove this fact.
Indeed let’s call the smallest integer from the first multiset small and another one that we want to swap big. Delta = big - small. We can notice that if we will swap small instead of big new sum of elements of the first multiset will increase by Delta and new sum of elements of the second multiset will decrease by Delta and since Delta always > 0 (small < big) the result won’t be worse.
In similar manner we can prove this fact for the biggest integer from the second multiset.
So now we can just simulate this process:
If sum of elements of the first multiset is bigger than sum of elements of the second multiset we should stop the process and print value of counter;
In other case let’s find x and y.
If x > y print -1
if x < y swap them and add 1 to counter.
SOLUTIONS:
Setter’s Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n, m;
cin>>n>>m;
int a[n], b[m], Ascore = 0, Bscore = 0;
for (int i = 0; i < n; i++)
{
cin>>a[i];
Ascore += a[i];
}
sort(a, a+n);
for (int i = 0; i < m; i++)
{
cin>>b[i];
Bscore += b[i];
}
sort(b, b+m, greater<int>());
int cnt = 0;
for (int i = 0; i < n && i < m; i++)
{
if(Ascore <= Bscore)
{
if(b[i] > a[i])
{
int diff = b[i] - a[i];
a[i] = diff + a[i];
b[i] = b[i] - diff;
Ascore += diff;
Bscore -= diff;
cnt++;
}
else
break;
}
}
if(Ascore > Bscore)
cout<<cnt<<endl;
else
cout<<-1<<endl;
}
return 0;
}
Tester’s Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n, m;
cin>>n>>m;
int a[n], b[m], Ascore = 0, Bscore = 0;
for (int i = 0; i < n; i++)
{
cin>>a[i];
Ascore += a[i];
}
sort(a, a+n);
for (int i = 0; i < m; i++)
{
cin>>b[i];
Bscore += b[i];
}
sort(b, b+m, greater<int>());
int cnt = 0;
for (int i = 0; i < n && i < m; i++)
{
if(Ascore <= Bscore)
{
if(b[i] > a[i])
{
int diff = b[i] - a[i];
a[i] = diff + a[i];
b[i] = b[i] - diff;
Ascore += diff;
Bscore -= diff;
cnt++;
}
else
break;
}
}
if(Ascore > Bscore)
cout<<cnt<<endl;
else
cout<<-1<<endl;
}
return 0;
}
Editorialist’s Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n, m;
cin>>n>>m;
int a[n], b[m], Ascore = 0, Bscore = 0;
for (int i = 0; i < n; i++)
{
cin>>a[i];
Ascore += a[i];
}
sort(a, a+n);
for (int i = 0; i < m; i++)
{
cin>>b[i];
Bscore += b[i];
}
sort(b, b+m, greater<int>());
int cnt = 0;
for (int i = 0; i < n && i < m; i++)
{
if(Ascore <= Bscore)
{
if(b[i] > a[i])
{
int diff = b[i] - a[i];
a[i] = diff + a[i];
b[i] = b[i] - diff;
Ascore += diff;
Bscore -= diff;
cnt++;
}
else
break;
}
}
if(Ascore > Bscore)
cout<<cnt<<endl;
else
cout<<-1<<endl;
}
return 0;
}