# VCOUPLE - Editorial

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

Cake-Walk

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 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){
}
long long readIntLn(long long l,long long r){
}
}
}

const int maxn = 2e4, maxt = 5, maxv = 1e9;

int main()
{
while(t--){
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

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
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)
so , the approach will be
(4+3),(5+2),(6+1)

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;
}