Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

HackerEarth Gaming Triples problem solution

YASH PAL, 31 July 2024
In this HackerEarth Gaming Triples problem solution, All the Games are not Mathematical at all but Mathematical games are generally favourite of all. Ananya offered such a Mathematical game to Sarika. Ananya starts dictating the rules of the game to Sarika. Sarika finds the game interesting and wishes to play it. Ananya said that they have an array of N elements. Each second either Ananya or Sarika can make a move. First one to make a move can select any 3 elements from the given array which satisfies the following condition.
Let us consider 3 selected elements are A[x1], A[x2], A[x3] so they must follow the given two condition.
x1 < x2 < x3
y1 < y2 > y3.
where y1=A[x1] , y2=A[x2] , y3=A[x3].
The 3 selected numbers are written down on a piece of paper. One triplet can only be chosen once.
The second player to make a move can also choose any 3 elements A[x1], A[x2], A[x3] such that chosen set of elements fulfill the following two conditions.
x1 < x2 < x3
y1 > y2 < y3.
where y1=A[x1] , y2=A[x2] , y3=A[x3].
Ananya and Sarika move alternatively and play optimally. Determine the winner of the game and also report the number of seconds for which the game lasts.
NOTE:
  1. One triplet can be chosen once.
  2. Two triplets are considered to be different if there exists at least one x which belongs to the first triplet but not to the second triplet.( where x is one of the indices of the chosen triplet )
HackerEarth Gaming Triples problem solution

HackerEarth Gaming Triples problem solution.

#include<bits/stdc++.h>
using namespace std;
#define scan(x) scanf("%d",&x)
#define printll(x) printf("%lldn",x)
#define all(x) x.begin(),x.end()
#define ft first
#define sd second

vector<int> BIT;
vector<long long> A,B;
vector< pair<int,int> > arr;

void update(int idx,int n){
while(idx<=n){
BIT[idx]+=1;
idx+=(idx&(-idx));
}
}

int summ(int idx){
int s=0;
while(idx>0){
s+=BIT[idx];
idx-=(idx&(-idx));
}
return s;
}

int query(int l,int r){
return summ(r)-summ(l-1);
}


int main(){

int t;
scan(t);
while(t--){
int n;
scan(n);
arr.resize(n);
A.resize(n+1);
B.resize(n+1);
BIT.resize(n+1);
fill(all(BIT),0);
fill(all(A),0);
fill(all(B),0);
for(int i=0;i<n;i++){
scan(arr[i].ft);
arr[i].sd=i+1;
}
int st;
scan(st);
sort(all(arr));
int i=n-1;
while(i>=0){
int x=arr[i].ft;
int c=0;
while(i>=0&&x==arr[i].ft){
A[arr[i].sd]=query(arr[i].sd,n);
A[arr[i].sd]=1LL*A[arr[i].sd]*query(1,arr[i].sd);
i--,c++;
}
int idx=i;
while(c--){
idx++;
update(arr[idx].sd,n);
}
}
fill(all(BIT),0);
i=0;
while(i<n){
int x=arr[i].ft;
int c=0;
while(i<n&&x==arr[i].ft){
B[arr[i].sd]=query(1,arr[i].sd);
B[arr[i].sd]=1LL*B[arr[i].sd]*query(arr[i].sd,n);
i++,c++;
}
int idx=i;
while(c--){
idx--;
update(arr[idx].sd,n);
}
}
long long sum1=0,sum2=0;
for(int i=1;i<=n;i++)
{ sum1+=A[i];
sum2+=B[i];
}
if(st){
sum1>=sum2 ? printf("Ananyan"): printf("Sarikan");
}
else{
sum1<sum2 ? printf("Ananyan"): printf("Sarikan");
}
if(sum2<=sum1){
printf("%lldn",min(sum1,sum2)*2);
}else{
printf("%lldn",min(sum1,sum2)*2+1);
}
}
return 0;
}

Second solution

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define all(a) a.begin(),a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define MOD 1000000007
#define total 5
#define M 100000*MOD
#define NIL 0
#define MAXN 200001
#define EPS 1e-5
#define INF (1<<28)
typedef unsigned long long int uint64;
typedef long long int int64;

pair<int,int>a[111111];
int64 BIT[111111];
void clea(int n){
for(int i=1;i<=n;i++)
BIT[i]=0;
}
void upd(int idx,int n){
while(idx<=n){
BIT[idx]+=1;
idx+=(idx)&(-idx);
}
}
int64 query(int l,int r){
int64 ret=0;
while(r){
ret+=BIT[r];
r-=(r)&(-r);
}
while(l){
ret-=BIT[l];
l-=(l)&(-l);
}
return ret;
}
int main(){
int mov,t,n,i;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a[i].first);
a[i].second=i;
}
sort(a+1,a+n+1);
int64 ans1=0,ans2=0;
for(i=1;i<=n;){
int val=a[i].first;
int cnt=0;
while(i<=n&&a[i].first==val){
ans1+=query(0,a[i].second)*query(a[i].second-1,n);
cnt++;
i++;
}
int idx=i;
while(cnt--){
idx--;
upd(a[idx].second,n);
}
}
clea(n);
for(i=n;i>=1;){
int val=a[i].first;
int cnt=0;
while(i>=0&&a[i].first==val){
ans2+=query(0,a[i].second)*query(a[i].second-1,n);
cnt++;
i--;
}
int idx=i;
while(cnt--){
idx++;
upd(a[idx].second,n);
}
}
clea(n);
scanf("%d",&mov);
if(mov){
if(ans1>ans2)
printf("Sarikan");
else
printf("Ananyan");
}
else{
if(ans1>ans2)
printf("Ananyan");
else
printf("Sarikan");
}
if(ans1<=ans2)
printf("%lldn",2*ans1);
else
printf("%lldn",2*ans2+1);
}
return 0;
}
coding problems

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes