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.

#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';
    }
}

coding problems solutions