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:
- One triplet can be chosen once.
- 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.
#include<bits/stdc++.h>
using namespace std;
#define scan(x) scanf("%d",&x)
#define printll(x) printf("%lld\n",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("Ananya\n"): printf("Sarika\n");
}
else{
sum1<sum2 ? printf("Ananya\n"): printf("Sarika\n");
}
if(sum2<=sum1){
printf("%lld\n",min(sum1,sum2)*2);
}else{
printf("%lld\n",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("Sarika\n");
else
printf("Ananya\n");
}
else{
if(ans1>ans2)
printf("Ananya\n");
else
printf("Sarika\n");
}
if(ans1<=ans2)
printf("%lld\n",2*ans1);
else
printf("%lld\n",2*ans2+1);
}
return 0;
}
0 Comments