FAIRELCT - Editorial

vegann · January 1, 2021, 11:51am

Author & Editorialist: Andrew Kostianoy
Tester: Radoslav Dimitrov

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Greedy

PROBLEM:

You’re given two multisets of integers. You can swap any two integers from diffrent multisets. You want to perform as few swaps as possbile in such a way that sum of elements of the first multiset is greater than sum of elements of the second multiset.

QUICK EXPLANATION:

It’s always profitable to swap the smallest integer from the first multiset (let’s call it x) with the biggest integer from the second multiset (let’s call it y). If x \geq y and the winning condition isn’t met you should print -1.

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 sml and another one that we want to swap bad. \Delta = bad - sml. We can notice that if we will swap sml instead of bad 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 \geq0 (sml \leq bad) 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 \geq y print -1;
if x < y swap them and add 1 to counter.

Complexity of the solution: O(n^2)

SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int M = 1010;
int n, m, a[N], b[M];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

//    freopen("input2.txt","r",stdin);
//    freopen("output2.txt","w",stdout);

    int qq; cin >> qq;

    for (; qq; qq--){
        cin >> n >> m;

        int sum_a = 0;
        int sum_b = 0;
        int ans = 0;

        for (int i = 0; i < n; i++){
            cin >> a[i];
            sum_a += a[i];
        }

        for (int i = 0; i < m; i++) {
            cin >> b[i];
            sum_b += b[i];
        }

        while (sum_a <= sum_b){
            int mn_a = int(1e9), loc_a = -1;
            int mx_b = -1, loc_b = -1;

            for (int i = 0; i < n; i++)
                if (a[i] < mn_a){
                    mn_a = a[i];
                    loc_a = i;
                }

            for (int i = 0; i < m; i++)
                if (b[i] > mx_b){
                    mx_b = b[i];
                    loc_b = i;
                }

            if (mn_a >= mx_b){
                ans = -1;
                break;
            }

            ans++;

            swap(a[loc_a], b[loc_b]);

            sum_a -= mn_a;
            sum_a += mx_b;

            sum_b += mn_a;
            sum_b -= mx_b;
        }

        cout << ans << '\n';
    }

    return 0;
}

Tester's Solution

#include <bits/stdc++.h>
#define endl '\n'
 
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
 
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
 
int n, m;
int a[MAXN], b[MAXN];
 
void read() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
}
 
void solve() {
    sort(a, a + n);
    sort(b, b + m);
 
    int sum_a = 0, sum_b = 0;
    for(int i = 0; i < n; i++) sum_a += a[i];
    for(int i = 0; i < m; i++) sum_b += b[i];
 
    if(sum_a > sum_b) {
        cout << 0 << endl;
        return;
    }
 
    for(int i = 1; i <= min(n, m); i++) {
        sum_a -= a[i - 1];
        sum_b -= b[m - i];
        sum_b += a[i - 1];
        sum_a += b[m - i];
 
        if(sum_a > sum_b) {
            cout << i << endl;
            return;
        }
    }
 
    cout << -1 << endl;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while(T--) {
        read();
        solve();
    }
 
    return 0;
}

VIDEO EDITORIAL:

anuanu_0 · January 11, 2021, 2:11pm

Can anyone help me in finding the error in my solution. It is partially correct i.e for subtasks. I tried but it seems correct to me.

Code

Thank you in advance.

green_619 · January 11, 2021, 2:21pm

can I get editorial for java language?

avi_9314 · January 16, 2021, 7:41am

remember if the score are equal then also it is not possible … also your loops are bit confusing
instead you can do something like this

Solution: 41665149 | CodeChef

harsh_raj02 · January 16, 2021, 7:52am

t = int(input())
for i in range(t):

    n, m = map(int, input().split())
    pn = list(map(int, input().split()))
    pm = list(map(int, input().split()))
    s_pn, s_pm = sum(pn), sum(pm)
    if s_pn > s_pm:
        print(0)

    elif min(pn) >= max(pm):
        print(-1)

    else:
        swap = 1
        flag = 0
        while swap <= n:
            s_pn = s_pn + max(pm) - min(pn)
            s_pm = s_pm + min(pn) - max(pm)
            pn.remove(min(pn))
            pm.remove(max(pm))
            if s_pn > s_pm:
                flag = 1
                break
            swap = swap + 1

        if flag == 1:
            print(swap)
        else:
            print(-1)

divyansh0908 · February 2, 2021, 11:33am

Can anyone help me to figureout, where I am going wrong?
#include<bits/stdc++.h>
#include
#include
using namespace std;

int main() {
// your code goes here
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;

while(t--){
    int sum_n=0,sum_m=0,counter=0;
    int n,m;
    cin>>n>>m;
    int tk=n;
    int pk=m;
    vector<int>arrn(n),arrm(m);
    for(int i=0;i<n;i++){
        cin>>arrn[i];
        sum_n+=arrn[i];
    }
    for(int i=0;i<m;i++){
        cin>>arrm[i];
        sum_m+=arrm[i];
        
    }
    sort(arrn.begin(),arrn.end());
	sort(arrm.begin(),arrm.end());
    for(int i=0;i<n;i++){
       // cout<<arrn[i]<<" ";
        
    }
   // cout<<" "<<endl;
    for(int k=0;k<m;k++){
       // cout<<arrm[k]<<" ";
       // cout<<""<<endl;
    }
   // cout<<" "<<endl;
    int count=0;
  
 
    while(sum_m>=sum_n && count<min(m,n) ){
            
            if(arrn[count]>=arrm[m-1-count]){
                counter=-1;
                break;
            }else{
                int suma=arrn[count]-arrm[m-1-count];
                sum_n=sum_n-suma;
                sum_m=sum_m+suma;
                count+=1;
                counter+=1;
               // cout<<"this loop was there"<<endl;
            
        }
    }
    
    
    cout<<counter<<endl;
}
return 0;

}

divyansh0908 · February 2, 2021, 11:39am

Can anyone help me figuring out my mistake.

shreyaxh · February 2, 2021, 4:08pm

The condition is that the person with strictly more votes wins, while in your code you break even for equal votes. Your solution was very similar to the one I used if you want to check that out heres the link : My Solution

divyansh0908 · February 2, 2021, 5:17pm

Thanks for your help. Got your point.

abhinav174 · June 30, 2021, 5:35pm

please tell what’s wrong
#include <bits/stdc++.h>
using namespace std;

int sum_arr(long long int arr[], int n)
{ int sum=0;
for(int i=0;i<n;i++)
{
sum+=arr[i];
}
return sum;
}

int main() {
// your code goes here
long long int t;
long long int n,m,b[m],a[n];
long long int ans=0,sum_n,sum_m;
while(t–)
{ cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int j=0;j<m;j++)
{
cin>>b[j];
}
sum_n=sum_arr(a,n);
sum_m=sum_arr(b,m);
if(sum_n<=sum_m)
{
int x=*min_element(a,a+n);
int y=*max_element(b,b+n);
if(x>=y)
{
ans=-1;

        }
        else
        
        {
            sum_m+=x-y;
            sum_n+=y-x;
            ans++;
        }
        
        cout<<ans<<endl;
    }
    
}
return 0;

}

anuj_pandey000 · September 29, 2021, 12:03pm

https://www.codechef.com/viewsolution/51773597
My solution is shown partially correct, can anyone tell me why?