HackerEarth Array Game problem solution

In this HackerEarth Array Game problem solution, Ashish and Jeel are playing a game. They are given a multiset of arrays (initially only one array is present).

A player has to make the following move in their turn:

Select one of the arrays of size greater than 1.
Divide the array into two non-empty parts such that every element of the left array is smaller than every element of the right array.

Formally, if we split an array A of size N into arrays L and R, then the following conditions must hold:

L must be a non-empty prefix and R must be the remaining non-empty suffix of the array A respectively.
For every element Pi of L and every element Qj of R, the inequality Pi < Qi must hold.

A player loses if he cannot make a move. Both the players play the game optimally. If Jeel plays first, then determine who wins the game.

Topics we are covering

HackerEarth Array Game problem solution.

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "n"
#define int long long

const int N=1e5+5;

int n, cnt=0;
int a[N], pref[N], suf[N];

int32_t main()
{
  IOS;
  int t;
  cin>>t;
  while(t--)
  {
    cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
      cin>>a[i];
      pref[i]=max(pref[i-1], a[i]);
    }
    suf[n+1]=1e9;
    for(int i=n;i>=1;i--)
      suf[i]=min(suf[i+1], a[i]);
    for(int i=1;i<=n-1;i++)
    {
      if(pref[i] < suf[i+1])
        cnt++;
    }
    if(cnt%2)
      cout<<"Jeel"<<endl;
    else
      cout<<"Ashish"<<endl;
  }
  return 0;
}

Second solution

#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        'n'
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(char ch) {
  return string("'")+ch+string("'");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <class InputIterator>
string to_string (InputIterator first, InputIterator last) {
  bool start = true;
  string res = "{";
  while (first!=last) {
    if (!start) {
      res += ", ";
    }
    start = false;
    res += to_string(*first);
    ++first;
  }
  res += "}";
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x){
  input>>x.F>>x.S;
  return input;
}

template <typename A>
istream& operator>>(istream& input,vector<A>& x){
  for(auto& i:x)
    input>>i;
  return input;
}


#ifdef PRINTERS
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

long long readInt(long long l,long long r,char endd){
  long long x=0;
  int cnt=0;
  int fi=-1;
  bool is_neg=false;
  while(true){
    char g=getchar();
    if(g=='-'){
      assert(fi==-1);
      is_neg=true;
      continue;
    }
    if('0'<=g && g<='9'){
      x*=10;
      x+=g-'0';
      if(cnt==0){
        fi=g-'0';
      }
      cnt++;
      assert(fi!=0 || cnt==1);
      assert(fi!=0 || is_neg==false);

      assert(!(cnt>19 || ( cnt==19 && fi>1) ));
    } else if(g==endd){
      assert(cnt>0);
      if(is_neg){
        x= -x;
      }
      assert(l<=x && x<=r);
      return x;
    } else {
      debug(int(g));
      assert(false);
    }
  }
}
string readString(int l,int r,char endd){
  string ret="";
  int cnt=0;
  while(true){
    char g=getchar();
    if(g==endd){
      break;
    }
    else if(islower(g)){
      cnt++;
      ret+=g;
    }
    else{
      assert(false);
    }
  }
  assert(l<=cnt && cnt<=r);
  return ret;
}
long long readIntSp(long long l,long long r){
  return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
  return readInt(l,r,'n');
}
string readStringLn(int l,int r){
  return readString(l,r,'n');
}
string readStringSp(int l,int r){
  return readString(l,r,' ');
}


void solve(){
  int T = readIntLn(1,10);
  for(int i = 0; i < T; i++){
    int N = readIntLn(1,100000);
    vector<int> elem(N);
    for(int j = 0; j < N; j++){
      if(j+1 == N){
        if(i+1 == T) elem[j] = readInt(1,1000000000,EOF);
        else elem[j] = readIntLn(1,1000000000);
      }
      else{
        elem[j] = readIntSp(1,1000000000);
      }
    }
    vector<int> prefmax(N);
    vector<int> suffmin(N);
    for(int j = 0; j < N; j++){
      if(j == 0) prefmax[j] = elem[j];
      else prefmax[j] = max(prefmax[j-1], elem[j]);
    }
    for(int j = N-1; j >= 0; j--){
      if(j+1 == N) suffmin[j] = elem[j];
      else suffmin[j] = min(suffmin[j+1], elem[j]);
    }
    int cnt = 0;
    for(int j = 1; j < N; j++){
      cnt += (suffmin[j] > prefmax[j-1]);
    }
    puts(cnt%2 ? "Jeel" : "Ashish");
  }
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t=1;
  while(t--){
    solve();
  }
  return 0;
}

coding problems solutions