BENCHP - Editorial

editorial
, ,
22

I was on an Instant high when I solved the first 2 in less than 7 mins. Then I overlooked this problem and what I misunderstood was our Aim is to put equal sums on both sides, such that total weight must be greater than or equal to the W. I immediately searched for the subset sum problem (my bad), wasted much time modifying the DP approaches found online. Later realised this would fail as the constraints are much higher where DP wouldn’t pass. But noticed that I can easily solve for 1st Subtask - Coded for those 30 points and boom rank was 20. After having dinner (when lunchtime was going on) I came back and saw the rank go above 1000. I slapped myself for not looking at this problem carefully and immediately solved it for 100. Still rank was increasing exponentially. Took a deep breath and solved the remaining problems partially. This way I was able to prevent the fall of ratings :neutral_face:.

Btw, NICE problems :clap: but it would have been better if the first three problems didn’t have the same difficulty, it is like the first three problems are just a cakewalk and the immediate next problem is super difficult for me.

Still regret overlooking the statement. :sob:

23

If the weights are odd say 7, you can still use 6 of these weights (3 on each side).

24

Exactly, if weigths are odd, then you can take condition
if(x.second%2==0)
{
sum+=(x.second*x.first);
}
else{ sum+=(x.second-1)*x.first; }

25

I did the same, I instantly looked for subset sum for half the weight remaining after subtracting W-wr. It didn’t worked.

26

exactly same , and then i think why submissions increased , then read again and realise oh shit I read question wrong :frowning_face:

1 Like
27

We can definitely take this, just use mp.clear(). I made the same mistake, Checkout my code

#include<bits/stdc++.h>
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long t, n, w, wr, a;
cin>>t;
while(t–)
{
cin>>n>>w>>wr;
w=w-wr;
map<long long, long long>mp;
for(int i=0 ; i<n ; i++)
{
cin>>a;
mp[a]++;
}

    for(auto i:mp)
    {
        if(i.second%2==0)
        w=w-(i.first*i.second);
        else
        w=w-(i.first*(i.second-1));
    }
    if(w>0)
    cout<<"NO\n";
    else
    cout<<"YES\n";
    mp.clear();
}
return 0;

}

1 Like
28

we can use hashmap to find the occurence of weight

30

This is my solution… Since most of the people have used maps to solve this problem…I am sharing my solution which does not use maps … thanks

void solve(){
int n,w,wr;
cin >> n >> w >> wr;
int arr[n];
for (int i=0;i<n;i++){
cin >> arr[i];
}
sort(arr,arr+n);
// for (int c: arr)
// cout << c << " ";
if (wr >= w)
cout << “YES” << endl;

else{
int diff = 0;
diff = w - wr;
int i = 0;
while(i<n-1){
if (arr[i] == arr[i+1]){

        diff  = diff - 2*arr[i];
        i = i+2;
        if (diff <= 0){
            cout << "YES" << endl;
            return;
        }
    }
    else
        i++;
   }

cout << "NO" << endl;

}
}

31

Umm So the algo is correct,
the thing is the questions should have been more clear in that what they meant from symmetric, I thought that just the torque should be zero or weights should be equal

32

Your solution is mostly similar to that of mine…i think what mistake you have done is that the iteration which you have used like think about cases if weights are 10,10,10 your code will consider the middle 10 two times… because bcz here if it is a array,then a[0] = a[1] and a[1] = a[2]… but we do not have to do that here. Clearly from this array only two weights of 10 can be used… not all three… So if we select a pair we need to jump not one but two place as when a pair is selected another element comes with it already… If you will think about these type of cases then you can figure out the mistake…Thanks

33

No dude, in iteration I have written i++
If case 10 10 10 the it will add first and second 10 and then it will jump to direct 3rd 10 :slightly_smiling_face:

34

By unordered_map it will become O(n) time complexity. fun problem.

35

#include <bits/stdc++.h>
using namespace std;

int main() {
int T;
cin>>T;
while(T–)
{
int N,W,Wr,i,temp,sum=0;
cin>>N>>W>>Wr;
int wr[N];
sum+=Wr;
for(i=0;i<N;i++)
cin>>wr[i];
if(Wr>=W)
cout<<“YES”<<endl;
else
{
i=0;
sort(wr,wr+N);
while(i<N)
{
int count=0;
temp=wr[i];
while(wr[i]==temp)
{
count++;
i++;
if(i>=N)
break;
}
if((count%2)==0)
sum+=(count*temp);
else
sum+=(count-1)*temp;
}
if(sum>=W)
cout<<“YES”<<endl;
else
cout<<“NO”<<endl;
}
}
return 0;
}
Could someone please tell what’s wrong in this code. It’s running on some other compilers but not on CodeChef. I am getting runtime error.

36

Use long long int.

37

can anyone tell me why my code does not give me any output

#include<bits/stdc++.h>

using namespace std;

int main()

{

int n;

cin>>n;

int arr[n];

int count[10]={0};

for(int i=0;i<n;i++)

{

    cin>>arr[i];

    

}      

for(int i=0;i<n;i++)

{

    count[arr[i]]++;

}

for(int i=0;i<10;i++){

    cout<<count[i];

}

}

38

could you plz, tell me why this code is giving WA :confused:


#include<bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    // your code goes here
    int t;
    cin>>t;
    while(t--)
    {
        int n,w,rod;
        cin>>n>>w>>rod;
        
        int wgt[n];
        for(int i=0; i<n; i++)
         cin>>wgt[i];
        
        sort(wgt,wgt+n);
        long long add=0;
        
        int count=1;
        for(int i=1; i<n; i++)
        {
            if(wgt[i]==wgt[i-1])
            count++;
            else
            {
                if(count%2==0)
                {
                    add= add+ (wgt[i-1]*count);
                    count=1;
                }
                else{
                    add= add+ (wgt[i-1]*(count-1));
                    count=1;
                }
            }
        }
        if(count>1)
        {
            if(count%2==0)
                {
                    add= add+ (wgt[n-1]*count);
                }
                else{
                    add= add+ (wgt[n-1]*(count-1));
                }
        }
        
        if((rod+add) >=w)
        cout<<"YES\n";
        else
        cout<<"NO\n";
    }
	return 0;
}
39

i used the map but got WA . PLease help where i am going wrong .

40

Use long long
Your AC Code

1 Like
41

It worked. Thank you.

42

I HAVE DONE THIS YESTERDAY AFTER READING THE QUESTION INCORRECTLY AND MISSED THE WORD " AT LEAST ". GO THROUGHT THE CODE AND IF POSSIBLE TRY TO HACK MY CODE. I HAVE NOT TESTED IT TO VARITY OF TEST CASES. HERE IS THE CODE.