Help in BOX REDUCTION(BXRED)

Problem:-Contest Page | CodeChef

Code:-

``````#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)cin>>arr[i];

sort(arr,arr+n,greater<int>());
if(n==1)
cout<<"1"<<endl;
else{
//map<int,int> m;
bool vis[n];
for(int i=0;i<n;i++)
vis[n]=false;
int c=0;
int i,j;
for(i=0,j=1;i<n && j<n;){
//cout<<i<<" "<<j<<endl;
//cout<<"Before: ";
//cout<<i<<" "<<j<<"    ";
if(arr[i]>=(2*arr[j])){
//m[i]=j;
vis[j]=vis[i]=true;
c++;
while(vis[i]==true)
i++;
while(vis[j]==true || i==j)
j++;
}
else
j++;

//cout<<"After: ";
//cout<<i<<" "<<j<<endl;
}
//cout<<i<<endl;

cout<<n-c<<endl;
}
}
``````

1 Like

Done,can u tell the problem in the code also?

Yeah, greedy is not the optimal solution for this problem. Consider this test-case:

TEST-CASE
``````4
15 6 5 3
``````

correct answer is 2 ( [3,6] and [15,5]) but your code outputs 3

1 Like

Greedy can be used but before that do sorting and divide the array into two equal halves(or 1 element more in case of odd) and try to make pairs from one half to the other half iteratively. By this, we will end up getting all the possible pairing and note to keep taking into account the unpaired number from both the halves in between and at the end.

The intuition is that suppose after sorting in non-decreasing order if we are at an index i (in the first half) and for some index j (in the second half) > i, we can not put the box at index i on the top of the box at index j, for no box at index >i we will be able to put it at the top of the box at index j.

Check my code once: Solution: 41609351 | CodeChef

1 Like

yeah i got that solution accepted,but can u again explain why greedy with 2 halves works ?