HackerEarth Balanced Partition problem solution

In this HackerEarth Balanced Partition problem solution, There are n houses in the village Dholakpur. The location of each house in the village can be given as (xi,yi) in the Cartesian coordinate plane. There are hi persons living in the ith house. Central electricity authority of the village is set to built a wire line across the village. The wire line is supposed to constructed in a way such that it is the north-east direction. In other words the wire line is parallel to the line y = x. Given that the construction of such line is considered to be effective only if the number of persons living in its left and right side are equal, can you tell if the construction of such wire line is possible?

HackerEarth Balanced Partition problem solution.

#include "bits/stdc++.h"
using namespace std;
struct ${$(){ios_base::sync_with_stdio(0);cin.tie(0);}}$;

const int X = 1000;
const int off = 2 * X + 50;

string solve(vector<pair <int, int> > a) {
   
   vector <int> sum(4 * off);
   
   for(auto e: a) 
      sum[e.first + off] += e.second;
   
   int all = accumulate(sum.begin(), sum.end(), 0LL);
   bool ok = false;
   
   for(int i = 1; i < sum.size(); i++) {
      sum[i] += sum[i - 1];
      ok |= (2 * sum[i] == all);
      ok |= (sum[i - 1] == all - sum[i]);
   }
   return ok? "YES": "NO";
}


int main() {
   int t, n, x, y, h;
   cin >> t;
   while(t--) {
      cin >> n;
      vector <pair <int, int> > v(n);
      
      for(int i = 0; i < n; i++) {
         cin >> x >> y >> h;
         v[i] = {x - y, h};
      }

      sort(v.begin(), v.end());
      cout << solve(v) << endl;
   }   

   return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    assert(cin>>t);
    while(t--)
    {
        int n;
        assert(cin>>n);
        vector<pair<int,int> >v;
        int minn=10000,maxx=-10000;
        for(int i=0;i<n;i++)
        {
            int x,y,h;
            assert(cin>>x>>y>>h);
            v.push_back({y-x,h});
            minn=min(minn,y-x);
            maxx=max(maxx,y-x);
        }
        int l=minn,r=maxx;
        int ans=r+1;bool f=0;
    while(l<=r)
    {
        int mid=(l+r)/2;
        int val=mid;
        int suma=0,sumb=0,sume=0;
        for(int i=0;i<v.size();i++)
        {
            if(v[i].first<val)suma+=v[i].second;
            else if(v[i].first==val)sume+=v[i].second;
            else sumb+=v[i].second;
        }
        if(suma==sumb){f=1;break;}
        suma+=sume;
        if(suma>sumb)
        {
            r=val-1;
        }
        else if(suma<sumb)
        {
            l=val+1;
        }
        else {f=1;break;}
 
    }
        if(f)cout<<"YESn";
        else cout<<"NOn";
    }
    return 0;
}

HackerEarth Balanced Partition problem solution.

Second solution

Leave a Reply