SOPC006 Editorial

PROBLEM LINK:

Practice
Contest

Author: Shriram Chandran
Editorialist: Shriram Chandran

DIFFICULTY:

Easy

PREREQUISITES:

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 :slight_smile: