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

PLease describe the issue

1 Like

Please format your code before posting :slight_smile: .

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 ?

PS:-Thx for reply

Thx for the test case

Because that’s the best way to make pair I thought. Notice that if you can put the box at index i at the top of index j after sorting you can always put index i at the top of any other box greater than index j. But to avoid wastage of bigger boxes I put at the top of first possible in second half.

So instead of finding the next possible for any index i i.e. the smallest index j > i such that we can put box[i] at the top of box[j] I looked some distance away. Splitting in almost half to ensure that in the best possible case all gets paired. That’s what triggerd me to implement this.

1 Like

Got the intution ,thx

1 Like