BENCHP - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan
Tester & Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

None

PROBLEM

Given a rod weighing W_r and N weights, ith weight weighing w_i. In order to maintain balance, Chef can lift rod if and only if on both sides of rod, the sequence of weights is symmetric. Determine if Chef can lift the rod weighing atleast W.

QUICK EXPLANATION

  • If grouping by weight, some weight appear odd number of times, the last one cannot be paired. Calling this last weight as useless weight.
  • After discarding useless weights, if the sum of weight of rod and the remaining weights exceed the target weight, Chef can lift rod with weight atleast W, otherwise Chef can’t.

EXPLANATION

Since we want to check if Chef can lift weight at least W, it is sufficient to determine the maximum weight Chef can lift while maintaining balance, and compare it with W.

Only constraint that stops Chef from adding all weight is the balance. Let’s group the weights by their weight in grams. We can see that weights of different weight do not affect each other.

Say there are C weights of weight G.

  • If C is even, we can put C/2 weights on left side and C/2 weights on the right side, thus maintaining balance while adding weight C*G to the total weight.
  • If C is odd, we cannot pair the last weight. we can put \lfloor C/2 \rfloor weights on left side and \lfloor C/2 \rfloor weights on the right side, thus maintaining balance while adding weight (C-1)*G to the total weight.

Hence, it is sufficient to count the occurrence of each weight, compute the maximum weight achievable while maintaining balance and compare it with target.

Summary

Can you write expression to avoid writing if condition or ternary operator for handling even and odd case?

Summary

(C-C%2)*G

Bonus

  • Can Chef lift exactly W weight?
  • What is the minimum weight greater than W the chef can lift?

TIME COMPLEXITY

The time complexity is O(N*log(N)) using normal sorting, or O(N+W) using counting sort.

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>

using namespace std;
 
const int maxw = 2e5, maxwr = 2e4, maxwi = 1e5, maxt = 10, maxn = 1e5;
int f[maxwi + 1]; 

int main()
{   
    int t; cin >> t; 
    int n, w, wr;
    while(t--){ 
        cin >> n >> w >> wr;
        memset(f, 0, sizeof(f));
        int x;
        for(int i = 0; i < n; i++){
            cin >> x;
            f[x]++;
        }
        long long int tot = wr;
        for(int i = 1; i <= maxwi; i++)tot += (long long int)i * 2 * (f[i] / 2);
        string ans = (tot >= w ? "YeS" : "No");
        cout << ans << endl;
    }
} 
Tester's Solution
import java.util.*;
import java.io.*;
class BENCHP{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni(), targetW = ni(), rodW = ni();
        int[] W = new int[N];
        for(int i = 0; i< N; i++)W[i] = ni();
        Arrays.sort(W);
        long maxWeight = rodW;
        for(int i = 0, ii = 0; i< N; i = ii){
            while(ii < N && W[i] == W[ii])ii++;
            int cnt = (ii-i);
            maxWeight += (cnt-cnt%2)*(long)W[i];
        }
        pn(maxWeight >= targetW?"yEs":"nO");
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new BENCHP().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

8 Likes

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

int main() {
int t;
cin>>t;
while(t–)
{
int n,w,wt;
cin>>n>>w>>wt;
int arr[n];
for(int i=0;i<n;i++) cin>>arr[i];
if(wt>=w) cout<<“YES\n”;
else
{
bool f=false;
int res=w-wt;
map<int,int> mp;
for(int i=0;i<n;i++) mp[arr[i]]++;
map<int, int>::reverse_iterator it;
for (it = mp.rbegin(); it != mp.rend(); it++)
{
int u=it->first,v=it->second;
if(v%2) v–;
res-=u*v;
if(res<=0)
{
f=true;
break;
}
}
if(f) cout<<“YES\n”;
else cout<<“NO\n”;
}
}
return 0;
}

My code is giving wrong answer verdict
Can anyone given me a test case where my code fails?

format please

``` 

before and after code

3 Likes

I implemented something a little different. If we divide the count (regardless of even or odd) and multiply it by 2 we will get the correct value. However, I am not sure why is it giving a WA verdict.

void solve()
{
	int n,w,wr;
	cin>>n>>w>>wr;
	long long wt = wr;
	unordered_map<int,int> mp;
	for(int i = 0; i < n; i++)
	{
		cin>>a[i];
		mp[a[i]]++;
	}
	for(int i = 0; i < n; i++)
	{		
		wt+=(a[i]*((mp[a[i]]/2)*2));
		mp[a[i]]=0;
	}
	if(wt >= w)
		cout<<"YES";
	else
		cout<<"NO";
	cout<<endl;

}
1 Like

What would be the best way to solve a modified problem : all arrangements in which sum of left weights and right weights are equal are allowed.

I would solve it by 0/1 knapsack dp.
where dp(x) = is it possible to make sum x.
then,
iterate from x = 2 to sum :
if (i % 2 == 0 && dp[x] && dp[x / 2])
Largest_possible_wt = W_rod + x;

Is there a better way to solve this modified problem?

1 Like

this one should help

my approach

we can only maintain the balance .if there are same numbers both the side then only it would balance .
therefore storing them and checking if their occurrence is multiple of 2 then only we can balance them (by placing left and right).
else they are odd anyhow 1 will not make them balancable.

#include<bits/stdc++.h>
typedef long long ll;
#define endl "\n"
using namespace std;

void sol() {
  ll n,w,wr;
  cin>>n>>w>>wr;
  ll arr[n];
  unordered_map <ll,ll> mp;
  for(ll i=0;i<n;i++)
  {  
    cin>>arr[i];
   mp[arr[i]]++;
  }

  ll sum=0;

  for(auto x : mp)
     if(x.second%2==0)
       {
        sum += ( x.second * x.first);
       }
  
  if(sum + wr>=w )
    cout<<"YES\n";
  else
     cout<<"NO\n";
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);cout.tie(NULL); 
 int t;
 cin>>t;
 while(t--)
 {
   sol();  
 }  
return 0;
}
3 Likes

I think that in your variation, the subset with x as sum should also be furhter divisible into 2 equal sum subset, since we have to distribute it equally in both sides, would love to know the possible approach for this.

1 Like

One possible approach would be the one that I mentioned. It has time complexity of O(n^2). I wonder if there is a better way.

1 Like

…My solution…

#include <iostream>
#include <map>

#define ll long long int
using namespace std;

   int main()
   {
    ll t;
    cin>>t;
    while(t--){
        
    ll N,W,Wr;
    cin>>N;
    cin>>W;
    cin>>Wr;
    map<ll,ll> weights;
    ll arr[N];
    for(ll i=0;i<N;++i)
    {
        cin>>arr[i];
    }
  
   
    
    for(ll i=0;i<N;++i)
    {
       ll key= arr[i];
       weights[key]=0;
       
    }
    for(ll i=0;i<N;++i)
    {
       ll key= arr[i];
       weights[key]++;
       
    }
    
    for(auto i=weights.begin();i!=weights.end();++i)
    {
       
       weights[i->first]=weights[i->first]/2;
       
    }
    ll extra_weight=0;
    
    for(auto it= weights.begin();it!= weights.end();++it)
    {
        if((it->second)>0)
        extra_weight+= ((it->first) *(it->second)*2); 
       
       
        
       
    }

    if(Wr>=W)
    cout<<"Yes"<<endl;
    else
    {
        if(Wr+extra_weight>=W)
        cout<<"Yes"<<endl;
        else
        cout<<"No"<<endl;
    }
    }
   

    return 0;
}

If w=100 and wr=0
And weights are 10,20,30,40
Then this algo will term all weights as useless and discard all of them
While we can do 10 + 40 || ROD || 20 +30
So how is the editorial correct ?

1 Like

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

int main()
{
// your code goes here
long long int t,n,w,wr,i,j;

cin>>t;

while(t--)
{
    cin>>n>>w>>wr;
    long long int a[n],dp[100005]={0},sum=0,temp[100005]={0};
    
    for(i=0;i<n;i++)
    cin>>a[i];
   
    if(w<=wr)
    cout<<"YES\n";
    else
    {
        sort(a,a+n);
        
        j = 0;
        for (int i=0; i<n-1; i++)
        if (a[i] != a[i+1])
        temp[j++] = a[i];
        
        temp[j++] = a[n-1];
        
        for(i=0;i<n;i++)
        {
            dp[a[i]]++;
        }
        
        for(i=0;i<100005;i++)
        {
            if(dp[temp[i]]%2==0)
            sum+=(dp[temp[i]]*temp[i]);
            else
            {
                dp[temp[i]]--;
                sum+=(dp[temp[i]]*temp[i]);
            }
        }
        
        if(w<=(wr+sum))
        cout<<"YES\n";
        else
        cout<<"NO\n";
        
    }
    
}

return 0;

}

An Example in the problem shows your case to be invalid

1 2 2 1 ||Rod Center|| 1 1 1 3 is a wrong configuration

it’s important that the weights added to the left side are symmetric to the weights added to the right side.

1 Like

I have no clue why my solution doesn’t pass this…

unordered_map<int, int> weightFreqMap;

bool solve(int wMin, int wRod) {
  size_t w = wRod;
  if (w >= wMin) return true;
  for (auto const& [weight, freq] : weightFreqMap) {
    if (freq >= 2) {
      w = w + weight * (freq - freq % 2);
    }
    if (w >= wMin) return true; 
  }
  return w >= wMin;
}

int main() {
  int t; cin >> t;
  int nWeights, wMin, wRod;
  for (int i = 0; i < t; ++i) {
    cin >> nWeights >> wMin >> wRod;
    for (int j = 0; j < nWeights; ++j) {
      int k; cin >> k;
      weightFreqMap[k] = weightFreqMap[k] + 1;
    }
    cout << (solve(wMin, wRod) ? "YES\n" : "NO\n");
  }
    return 0;
}

I solved in O(n) time with O(n) space. There is no need of sorting or dynamic programming. The only logic being a weight can be included if and only if it occurs even number of times.
Here is the code :

using ll = long long int;
void solve()
{
    ll n, w, wr;
    cin >> n >> w >> wr;
    unordered_map<ll, ll> foo;
    for (int i = 0; i < n; i++)
    {
        ll x;
        cin >> x;
        foo[x]++;
    }
    ll weight = 0;
    for (auto x : foo)
    {
        if (x.second % 2 == 0)
        {
            weight += x.first * x.second;
        }
    }
    if (weight + wr >= w)
        cout << "YES\n";
    else
        cout << "NO\n";
}

It is maybe because you are using the same map for every test case, you forgot to clear it.

i solved the problem as given in the tutorial but i felt that testcases maybe weak and some other logic should have been used because torque was not considered in this case…
example 1,5,6,4 = torque will be 11 + 25 + 63 +44 … like this and there might be some cases where the situation will balance in terms of torque and weights too.

You’re right, thanks!!

can someone please explain the problem with this code ?

#include
#include
#include
#include
#include
#include
#include
#include
typedef long long int ll;
using namespace std ;

int main ()
{
int t ;
cin >> t ;
while (t–)
{
long long int n ,w,w_rod ;
cin >> n >> w >> w_rod;
int a[n];
map<int,int> m;
for ( int i = 0 ; i < n ; i ++)
{
cin>> a[i];
m[a[i]]++;

    }

    if ( w_rod >= w)
    {
        cout << "YES"<<endl;
    }
    else
    {
   long long  int required = w-w_rod;
    long long int sum = 0 ;
    for ( auto it = m.begin() ; it!= m.end();it++)
    {
        if ( it->second % 2 == 0)
        {
            sum += it->first* it->second ;
        }
        else
        {
            sum += it->first * (it->second-1);
        }
    }
    if(sum >= required)
    {
        cout << "YES"<<endl;
    }
    else {
        cout << "NO"<<endl;
    }
    }
    m.clear();

}
}

Could anyone solve the alternative question of this where just the sum should be equal on either end.

using namespace std;
#include<bits/stdc++.h>
int main()
{
int t;
cin>>t;
while(t–)
{
int n,w,wr;
cin>>n>>w>>wr;
int a[n];
for(int i=0; i<n; i++) cin>>a[i];
sort(a,a+n);
w=w-wr;
for(int i=0; i<n-1; i++)
{
if(a[i]==a[i+1])
{

            w=w-2*a[i];
            i++;
        }

    }
    if(w<=0)cout<<"YES";
    else
    cout<<"NO";
    cout<<endl;

}
return 0;

}
What is wrong with my code???