Header Ad

HackerEarth The score game problem solution

In this HackerEarth The score game problem solution You are given an array A of N elements where each element is a pair represented by (X[i], Y[i]). 

Bob and Alice play a game where both of them have to pick some elements from the array A. Suppose, Bob picked the elements at index i1,i2,...,ik where K <= N.

Score(Bob) = Sigma(X[j] + Y[j]), where j belongs to (i1,i2,....,ik).
Score(Alice) = Sigma(X[j]), where j belongs to (1,2,....,N) excluding (i1,i2,....,ik).
Find the minimum number of elements Bob must pick such that the score of Bob is greater than Alice.


HackerEarth The score game problem solution


HackerEarth The score game problem solution.

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

bool cmp(pair<int,int> a, pair<int,int> b)
{
int gaina = 2*a.first + a.second;
int gainb = 2*b.first + b.second;

if(gaina != gainb) return gaina < gainb;
return a.first < b.first;
}

void solve(){
int n;
cin >> n;

int x[n+1], y[n+1];

for(int i = 1 ; i <= n ; i++) cin >> x[i];

for(int i = 1 ; i <= n ; i++) cin >> y[i];

int bob = 0;
int alice = 0;

vector<pair<int,int> >m;

for(int i = 1 ; i <= n ; i++){
m.push_back(make_pair(x[i], y[i]));
alice += x[i];
}

sort(m.begin(), m.end(), cmp);
int answer = 0;
for(int i = n - 1 ; i >= 0 ; i--)
{
if(bob > alice) break;
answer++;
bob += (m[i].first + m[i].second);
alice -= (m[i].first);
}

cout << answer << endl;
}

signed main(){
int t;
cin >> t;
while(t--){
solve();
}
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 1e5;
int x[MAX_N], y[MAX_N];

int main() {
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
ll alice = 0;
for (int i = 0; i < n; ++i) {
cin >> x[i];
alice += x[i];
}
for (int i = 0; i < n; ++i)
cin >> y[i];
int per[n];
iota(per, per + n, 0);
sort(per, per + n, [](int i, int j) { return 2 * x[i] + y[i] > 2 * x[j] + y[j]; });
ll me = 0;
int ans = 0;
while (me <= alice) {
me += x[per[ans]] + y[per[ans]];
alice -= x[per[ans++]];
}
cout << ans << '\n';
}
}


Post a Comment

0 Comments