# SOPC006 Editorial

Author: Shriram Chandran
Editorialist: Shriram Chandran

Easy

Greedy

# PROBLEM:

Given a set of elements, find a maximum matching if any two elements can be paired if they are within twice of each other.

# EXPLANATION:

Note that if we have i and j paired up and there is another person k with a_i \leq a_k \leq a_j, then both j and k can be paired and i and k can be paired.
Thus this gives us a greedy solution of maximizing number of teams at every index:
Sort the array in descending order.
Now at index i, if a_i \leq 2a_{i+1}, then pair i and i+1 and go to i+2. Otherwise, leave a_i and go to i+1.

All correct answers are given AC verdict.

# SOLUTION:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> ans;
void calc(pair<int,int> a[],int n)
{
if(n<=0)
return;
else if(a[n].first>2*a[n-1].first)
calc(a,n-1);
else
{
ans.push_back(make_pair(a[n].second,a[n-1].second));
calc(a,n-2);
}
}

void solve()
{
int n;
cin>>n;
pair<int,int> a[n];
for(int i=0;i<n;i++)
{
cin>>a[i].first;
a[i].second=i+1;
}
ans.clear();
sort(a,a+n);
calc(a,n-1);
cout<<2*ans.size()<<endl;
for(auto i:ans)
cout<<i.first<<" "<<i.second<<endl;
}

int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}


Many solutions used “int” instead of “long long int” , still got AC. Why ?
It was clearly mentioned that number can be as large as “1000000000”.
Example Solution which got AC(should have got WA):–>https://www.codechef.com/viewsolution/28817881

Edit:-The above solution is correct. I had wrong idea about range/limit of “int”

1 Like

This is because the limit of int is larger than 10^9. int allows upto 32 bits, which is approximately around 2*10^9.

Omg. I thought to till this day its 10^6 for int. What a noob I am.
Thanks