VCOUPLE - Editorial

PROBLEM LINK:

Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest

Setter: Ashish Vishal, Aditya Kumar Singh
Tester: Daanish Mahajan

DIFFICULTY:

Cake-Walk

PREREQUISITES:

Sorting, Greedy

PROBLEM:

Given the height of N boys and N girls in two arrays A and B. You have to form an N couple such that the maximum of the sum of the height of all couples must be minimum.

EXPLANATION:

Sort array A in increasing order and array B in decreasing order, then iterate ‘i’ from 1 to N and updating the required ans by max(ans,A[i]+B[i]).

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define is insert
#define rep1(i,a,b) for(long long i=a;i<=b;i++)
#define F first
#define S second
#define file ifstream fin("input.txt");ofstream fout("output.txt");
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fr(n) for(long long i=0;i<n;i++)
#define rep(i,a,b) for(long long i=a;i<b;i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;

void solve()
{
    ll n;
    cin>>n;
    vi a(n),b(n);
    fr(n)cin>>a[i];
    fr(n)cin>>b[i];

    sort(ALL(a));
    sort(ALL(b));
    reverse(ALL(b));

    fr(n)a[i]+=b[i];
    ll ans=*max_element(ALL(a));
    cout<<ans<<endl;
}
int32_t main()
{
    #ifndef ONLINE_JUDGE
    freopen("inputf.in", "r", stdin);
    freopen("outputf.in", "w", stdout);
    #endif
    fast;
    ll t=1;
    cin>>t; 
    while(t--)
    solve();
    return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
# define ll long long int  
# define pb push_back
# define pll pair<ll, ll>
# define pli pair<ll, int>
# define mp make_pair
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        // char g = getc(fp);
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
            // cout << x << " " << l << " " << r << endl;
            assert(l<=x && x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        // char g=getc(fp);
        assert(g != -1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
const int maxn = 2e4, maxt = 5, maxv = 1e9;
 
int main()
{   
    int t = readIntLn(1, maxt);
    while(t--){
        int n = readIntLn(1, maxn);
        vector<int> a, b;
        for(int i = 0; i < n; i++)a.pb(i == n - 1 ? readIntLn(1, maxv) : readIntSp(1, maxv));
        for(int i = 0; i < n; i++)b.pb(i == n - 1 ? readIntLn(1, maxv) : readIntSp(1, maxv));
        sort(a.begin(), a.end());
        sort(b.begin(), b.end(), greater<int>());
        int ans = 0;
        for(int i = 0; i < n; i++)ans = max(ans, a[i] + b[i]);
        cout << ans << endl;
    }
    assert(getchar()==-1);
} 

can anyone explain this sentence ,“maximum of the sum of the height of all couples must be minimum” i am not able to understand .

5 Likes

It means that if in some case the MAX Couple is turning out to be 9 and in some other case 7 then you have to take the case with Couple = 7.
eg.
4 5 3 boys
2 1 4 girls

Max couple here should be 5+2=7 and other couples as 4+1,3+4.
NOT 5+4=9
as 7<9;

Hope you understood.

1 Like

I did the exact same way and the test case was fine but when submitting my code it was wrong answer.

What does it mean?

It means it’s a school level problem

i am getting the point ,but how they come to now to sort one array in increasing order and other as decreasing order,thank you .

can’t we do it as it is ,i mean that without sorting
eg
4 5 3
2 1 4

if we add=>
4+2=6
5+1=6
3+4=7
we are getting the same answer ,i used like this what is wrong in this way of thinking ?

1 Like

i got it .

Okey

i am also having the same issue what is wrong in this approach.

okay so this is the comment that clears all your doubt .
suppose two array are there :
the no. of boy and girl present is 3.
boys: 4,6,5.(heights of boys)
girls: 2,3,1.(heights of girls)
now , first sort both the array.
after sorting the arrays are as follows:
boys: 4,5,6
girls: 1,2,3

wrong approach:
(4+1),(5+2),(6+3)
=5,7,9
so answer = 9 max.
but this approach is wrong as the question clearly states that we need to find the minimum maximum possible .
so the minimum maximum in above example = max girl height + max boy height
which gives us wrong answer ,

correct approach :
boys: 4,5,6
girls: 1,2,3

(minimum height of boy + maximum height of girl)
(4+3)=7 Answer.
so , the approach will be
(4+3),(5+2),(6+1)
=7,7,7 answer .

4 Likes

same approach, but getting time error.

#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int test;
cin >> test;
while(test–)
{
int num{};
cin >> num;
int arr1[num]{}, arr2[num]{};

    for (int i=0;i<num;i++)
    {
        cin >> arr1[i];
    }
    for (int i=0;i<num;i++)
    {
        cin >> arr2[i];
    }
    
    //bub sort
    {
        int i{},j{};
        for (int i=0;i<num-1;i++)
        {
            for (int j=0;j<num-1-i;j++)
            {
                if (arr1[j]>arr1[j+1])
                {
                    long long temp{};
                    temp = arr1[j];
                    arr1[j]=arr1[j+1];
                    arr1[j+1]=temp;
                }
                if (arr2[j]>arr2[j+1])
                {
                    long long temp{};
                    temp = arr2[j];
                    arr2[j]=arr2[j+1];
                    arr2[j+1]=temp;
                }
            }
        }
    }
    
    long long biggest{};
    biggest = arr1[num-1]+arr2[0];
    for (long long i=0;i<num;i++)
    {
        if (biggest < (arr1[num-1-i]+arr2[i]))
        biggest = arr1[num-1-i]+arr2[i];
    }
    
    cout << biggest << endl;
    
}

return 0;

}

#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int test;
cin >> test;
while(test–)
{
int num{};
cin >> num;
int arr1[num]{}, arr2[num]{};

    for (int i=0;i<num;i++)
    {
        cin >> arr1[i];
    }
    for (int i=0;i<num;i++)
    {
        cin >> arr2[i];
    }
    
    //bub sort
    {
        int i{},j{};
        for (int i=0;i<num-1;i++)
        {
            for (int j=0;j<num-1-i;j++)
            {
                if (arr1[j]>arr1[j+1])
                {
                    long long temp{};
                    temp = arr1[j];
                    arr1[j]=arr1[j+1];
                    arr1[j+1]=temp;
                }
                if (arr2[j]>arr2[j+1])
                {
                    long long temp{};
                    temp = arr2[j];
                    arr2[j]=arr2[j+1];
                    arr2[j+1]=temp;
                }
            }
        }
    }
    
    long long biggest{};
    biggest = arr1[num-1]+arr2[0];
    for (long long i=0;i<num;i++)
    {
        if (biggest < (arr1[num-1-i]+arr2[i]))
        biggest = arr1[num-1-i]+arr2[i];
    }
    
    cout << biggest << endl;
    
}

return 0;

}
getting time error, but same idea

use merge sort instead of bubble

Can any one find my mistake in this code.

#include
#include
#include
using namespace std;
#define ll long long int

int main()
{
ll t;
while(t–) {
ll n,j,k,sum=0;
cin>>n;
ll a[n],b[n],c[n];
for(ll i=0;i<n;i++)
cin>>a[i];
for(ll i=0;i<n;i++)
cin>>b[i];

    sort(a,a+n);
    sort(b,b+n);
  
    k=n;
    for(j=0;j<n;j++) {
     
            ll temp=a[j]+b[k-1];
            if(temp >= sum)
            sum=temp;
            k--;
      
    }
 
   
    cout<<sum<<"\n"

}
return 0;
}