HackerEarth An interesting game problem solution

In this HackerEarth An interesting game problem solution You are given two arrays a1,a2, …, an and b1,b2, …, bn where n is an even number.

Alice and Bob are playing a game on these arrays. In each turn, Alice selects two unused numbers before numbers i and j such that 1 <= i, j<= n and i != j. Bob selects one of them and this number is denoted as x and adds bx to his score. Alice takes the remaining one, that is denoted as y, and adds ay to his scores.

Alice and Bob want to maximize their scores simultaneously. Your task is to determine the difference between their scores after the game. Totally, they have n/2 turns.

In other words, your task is to find the difference between Alice’s and Bob’s scores after all turns if both sides move optimally.

HackerEarth An interesting game problem solution.

#include <bits/stdc++.h>
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define VAR(v, i) __typeof( i) v=(i)
#define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
 
using namespace std;
 
const int maxn = (int)1e6 + 100;
const int mod = (int)1e9 + 7;
const int P = (int) 1e6 + 7; 
const double pi = acos(-1.0);

#define inf mod
 
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;   
typedef vector<ll> Vll;               
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;                        

int n;
pii a[maxn];
bool type[maxn];
ll sum;

void solve(){
  scanf("%d", &n);
  forn(i, 1, n) scanf("%d", &a[i].s);
  forn(i, 1, n) scanf("%d", &a[i].f), sum += a[i].f;
  sort(a + 1, a + n + 1);
  forn(i, 1, n) a[i].s += a[i].f;
  priority_queue<int> q;
  ll ans = 0;
  q.push(a[1].s);
  forn(i, 1, n){
    ans += q.top();
    q.pop();
    if(i + 1 <= n) q.push(a[i + 1].s);
    if(i + 2 <= n) q.push(a[i + 2].s);
    i++;
  }
  printf("%lldn", ans - sum);
}

main () {
  int t = 1;
  scanf("%d", &t);
  while(t--)
    solve(); 
}

Second solution

#include <bits/stdc++.h>
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define VAR(v, i) __typeof( i) v=(i)
#define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
 
using namespace std;
 
const int maxn = (int)1e6 + 100;
const int mod = (int)1e9 + 7;
const int P = (int) 1e6 + 7; 
const double pi = acos(-1.0);

#define inf mod
 
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;   
typedef vector<ll> Vll;               
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;                        

int n;
pii a[maxn];
bool type[maxn];
ll sum;

void solve(){
  scanf("%d", &n);
  forn(i, 1, n) scanf("%d", &a[i].s);
  forn(i, 1, n) scanf("%d", &a[i].f), sum += a[i].f;
  sort(a + 1, a + n + 1);
  forn(i, 1, n) a[i].s += a[i].f;
  priority_queue<int> q;
  ll ans = 0;
  q.push(a[1].s);
  forn(i, 1, n){
    ans += q.top();
    q.pop();
    if(i + 1 <= n) q.push(a[i + 1].s);
    if(i + 2 <= n) q.push(a[i + 2].s);
    i++;
  }
  printf("%lldn", ans - sum);
}

main () {
  int t = 1;
  scanf("%d", &t);
  while(t--)
    solve(); 
}

coding problems solutions