Help in BOX REDUCTION(BXRED)

[kariyeno]

Problem:-BXRED Problem - 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

[cubefreak777]

Please format your code before posting .

[Tutorial] CoLoR format the Code!

Really quick tutorial for all forum members who dont know how to color format code like this which i learned from another site. just use 3 backticks ``` before and after the code and your code looks like this CPP : #include <iostream> using namespace std; int main() { for(int i=0 ; i < 10 ;++i) { cout << i <<" - hello world\n"; } return 0; } Python : # Python 3 program to find # factorial of given number def factor…

[Tutorial] Formatting in CodeChef Discuss

CodeChef has many beautiful Discuss Forum features. This tutorial is for introducing newcomers to the various formatting that are available in CC Discuss. I’ve seen individual tutorials on formatting code or equations, but no topic on the entire available options. So I’m writing this topic for it to be that one place with all available formatting. Basic: The very basic formatting such as Boldface or Italics are available in GUI, and just a click away. You can also use ** text ** for boldface an…

[kariyeno]

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

[cubefreak777]

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

[skn1998]

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: CodeChef: Practical coding for everyone

[kariyeno]

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

PS:-Thx for reply

[kariyeno]

Thx for the test case

[skn1998]

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.

[kariyeno]

Got the intution ,thx