HackerEarth One-Sized Game problem solution

In this HackerEarth One-Sized Game problem solution Ladia and Kushagra are playing the One-Sized Game. The rules of this game are pretty simple.

They have an array consisting of N elements (1-indexed). In each step, one needs to find out the smallest element present in the array. Get the index of that element and subtract that value (index value) from every element of the array. If there is a clash/collision between the smallest element, pick the one that occurs first -- that is the one having smaller index. This process is repeated several times. Whenever an element's value goes below 0 this element gets removed from the array and the array gets re-sized.

During the game's play, if at any point of time, the array is left with only one element, Ladia wins the game otherwise Kushagra wins.

Given an array consisting of N elements, print whether Ladia will win or Kushagra.

HackerEarth One-Sized Game problem 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 tot 300005
#define BLOCK 1000
#define MAXN 1000005
typedef unsigned long long int uint64;
typedef long long int int64;

vector<pair<int,int> >v;
int arr[100005];
int BIT[200005];

void upd(int x,int val){
  for(int i=x;i<200000;i+=i&(-i))
    BIT[i]+=val;
}

int query(int x){
  int ret=0;
  while(x){
    ret+=BIT[x];
    x-=x&(-x);
  }
  return ret;
}

int main(){
  int n,i,t;
  cin>>t;
  freopen("output.txt","w",stdout);
  while(t--){
    cin>>n;
    v.clear();
    for(i=1;i<=n;i++){
      cin>>arr[i];
      v.pb(mp(arr[i],i));
    }

    sort(all(v));
    int64 sub=0;
    bool won=false;

    for(int i=0;i<v.size();i++){
      if(v[i].first<sub){
        upd(v[i].second,1);
      }     
      else{
        if(i==(n-1))
          won=true;
        int64 rem=v[i].first-sub;
        int idx=v[i].second-query(v[i].second);
        int64 mul=rem/idx;
        mul++;
        sub+=mul*(int64)idx;
        upd(v[i].second,1);
      }
    }

    if(won)
      cout<<"Ladia"<<endl;
    else
      cout<<"Kushagra"<<endl;
    
    for(i=1;i<=n;i++)
      upd(i,-1);
  }
  fclose(stdout);
  return 0;
}

Second solution

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

ll pwr(ll base, ll p, ll mod = MOD){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}


ll gcd(ll a, ll b){
    if(b == 0)  return a;
    return gcd(b, a%b);
}


int n, BIT[100005];
ii arr[100005];


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

int query(int idx){
  int ans = 0;
  while(idx){
    ans += BIT[idx];
    idx -= idx & (-idx);
  }
  return ans;
}



int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin>>t;
    assert(t >= 1 && t <= 5);
    while(t--){

      cin>>n;
      assert(n >= 1 && n <= 100000);
      for(int i=1;i<=n;i++){
        cin>>arr[i].ff;
        assert(arr[i].ff >= 1 && arr[i].ff <= 1000*1000*1000);
        arr[i].ss = i;
      }
      sort(arr+1, arr+n+1);

      memset(BIT, 0, sizeof(BIT));
      ll sum = 0;
      for(int i=1;i<=n-1;i++){

        ll actual_val = arr[i].ff - sum;
        int actual_idx = arr[i].ss - query(arr[i].ss);
        if(actual_val < 0){
          update(arr[i].ss, 1);
          continue;
        }

        ll needed = actual_val/actual_idx+1;

        sum += actual_idx * needed;
        update(arr[i].ss, 1);
      }

      if(arr[n].ff-sum < 0) cout<<"Kushagra"<<endl;
      else  cout<<"Ladia"<<endl;
    }

    return 0;
}