 # BXRED - Editorial

Practice

Author: Yash Dwivedi

Tester: Shubham Kushwaha

Editorialist: Nikhil Shukla

MEDIUM

Two-pointers

# PROBLEM:

You are given an array of size n and you can choose any two indexes i and j and merge them together if a[i]*2 <= a[j] by merging I mean putting the smaller box into the bigger one. Thus, every merge operation will reduce the size of the array by one. You have to find out the minimum size you can get by doing this operation. Please note that you cannot choose any index more than once.

# Observation:

Since you cannot choose one index more than one thus it means that the minimum number of elements you can have is ceil(n/2).

# QUICK EXPLANATION:

First sort the array and then use two pointers technique, declare two-pointers one at the starting positions i.e at index 0, and the second at index ceil(n/2). Now choose the two index to merge if they satisfy a[first]*2 <= a[second] then increment number of mergeCount and increment both first and second and if they don’t just satisfy just increment the second pointer and do this till the second one reaches the end. The answer will be n-mergeCount.

# EXPLANATION:

First of all, we can observe that we can have a minimum of ceil(n/2) elements or we can also say that we can perform a maximum of floor(n/2) merges. Now lets sort the array and declare two variables one pointing to the 0th index and the second pointing to ceil(n/2)th index. Now if the element at the first pointer satisfies the condition that a[first]*2 <= a[second] then it is optimal to choose elements at the first and second pointer and merge them but if the a[first]*2 > a[second] then as the array is sorted we can imply that a[first+i] > a[second] where 0 < first+i < second, so we just have to increment the second pointer we will do this until the second pointer reaches the end of the array. During every merge, we will keep track of mergeCount and the answer will be n-mergeCount.
Time complexity will be O(nlogn) as in every case we need to sort the given array.

# SOLUTIONS:

Setter's Solution
``````#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ll n;
cin>>n;
ll i,a[n];
for(auto &i:a)
cin>>i;
ll mid=n/2;
ll grp=0;
ll total=n;
sort(a,a+n);
for(i=0;i<n/2;i++)
{
while(mid<n&&2*a[i]>a[mid])
{
mid=mid+1;
}
if(mid<n)
grp++;
mid++;
}
cout<<n-grp<<"\n";
return 0;
}
``````
Tester's Solution
``````#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define endl "\n"
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector<ll>
#define fast                          \
ios_base::sync_with_stdio(false); \
cin.tie(NULL)
using namespace std;
void solve()
{
int n;
cin>>n;
vi a(n,0);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a.begin(),a.end());

int ans=n,i=n-1,j=(n-1)/2;
while(j>=0)
{
if(2*a[j]<=a[i])
{

a[i]=a[j]=-1;
j--;
while(a[i]==-1){
i--;
}
ans--;
}
else
{
j--;
}
}
cout<<ans<<endl;
}
int main()
{

fast;
int t = 1;
while (t--)
{
solve();
}
}
``````
Editorialist's Solution
``````#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int>g(n);
for(int i=0;i<n;i++)
{
cin>>g[i];
}
sort(g.begin(),g.end());
int f=0;
int s=ceil(n/2.0);
int cnt=0;
while(1)
{
if(s==n)
break;
if(g[f]*2<=g[s])
{
cnt++;
f++;
s++;
}
else
{
s++;
}
}
cout<<n-cnt<<"\n";
}
``````

For video editorial, you can watch this live stream by Nikita Skybytskyi @sky_nik video link.
Thanks @sky_nik for this live stream.

Sorry to say but test-cases for this problem were painfully bad like many of the accepted solutions are just single or double pass incorrect greedy solutions. In fact my own solution that didn’t even pass the samples got an AC, I think you should at least have the samples as one of the hidden test-cases.

1 Like

Yes @cubefreak777 the test cases of this problem were weak. We sincerely apologise to everyone for this it was the first time we were hosting any contest. Next time we will do better .

1 Like

u can try this question for better practice its exact the same