Header Ad

HackerEarth New game of Oz problem solution

In this HackerEarth New game of Oz problem solution, Today Oz is playing a new game. He has an array arr[] of N distinct integers. In each turn he is will follow two actions -
  1. He selects a random number from arr[]. Say the value of this element is X.
  2. He will remove X from arr[]. if X-1 is present in arr[] then he will remove it. if X+1 is present in arr[] then he will remove it.
Oz will take turns until arr[] becomes empty. Oz loves this game so he wants to make a maximum number of possible turns. Help Oz to make a maximum number of possible turns.

HackerEarth New game of Oz problem solution

HackerEarth New game of Oz problem solution.

#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define mod 1000000007 // 10**9 + 7
#define INF 1e9
#define FOR(i,a,b) for(int (i) = (a); (i) < (b); ++(i))
#define RFOR(i,a,b) for(int (i) = (a)-1; (i) >= (b); --(i))
#define CLEAR(a) memset((a),0,sizeof(a))
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, b, a) for (int i = b; i > a; i--)
#define all(v) v.begin(), v.end()
#define GETCHAR getchar_unlocked
#define pi(n) printf("%d\n",n)
#define pll(n) printf("%lld\n",n)
#define rk() int t; scanf("%d",&t); while(t--)
using namespace std;
const double pi = acos(-1.0);

const int er[8] = {-1,-1,0,1,1,1,0,-1};
const int ec[8] = {0,1,1,1,0,-1,-1,-1};
const int fr[4] = {-1,1,0,0};
const int fc[4] = {0,0,1,-1};
typedef unsigned long long ull;
typedef long long ll;
typedef long l;
typedef pair<int,int> pii;
typedef vector<int> vec;
typedef vector<pii> vpii;
ll po(ll a,ll p)
{ll ret = 1;while(p){if(p&1)ret = (ret*a)%mod;a=(a*a)%mod;p=p>>1;}return ret%mod;}

int getans(vector<int> &res){
int ans = 0;
sort(res.begin(), res.end());
int size = 0;
for(int i = 0; i < res.size(); i++){
int ff = 0;
if(i == 0 || res[i] == res[i-1] + 1)size++;
else {
ff = size;
size = 1;
ans += (ff+1)/2;
if(i == res.size()-1)ans += (size+1)/2;
return ans;

int main(){
int n;
for(int i=0;i<n;i++){
int a;
int ans=getans(v);

Second solution

#define assn(n,a,b) assert(n<=b && n>=a)
using namespace std;
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,b) for(i=0;i<b;i++)
#define rep1(i,b) for(i=1;i<=b;i++)
#define pdn(n) printf("%d\n",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%d",&n)
#define pn printf("\n")
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define MOD 1000000007
LL mpow(LL a, LL n)
{LL ret=1;LL b=a;while(n) {if(n&1)
return (LL)ret;}
int main()
int t;
int n,ar[109],ans=0;
for(int i=0; i<n; i++)
for(int i=0; i<n; i++){
if(i!=n-1 and ar[i+1]==ar[i]+1)i++;
cout << ans << endl;
return 0;

Post a Comment