# HackerEarth Hectic Game problem solution

In this HackerEarth Hectic Game problem solution, Alice and Bob are playing a hectic game in which there are a total of N tasks each consisting of a start time Si and end time Ei.

Both players take alternate turns, Alice plays first. In each turn, a player chooses the maximum number of tasks that are non-overlapping as both Alice and Bob can perform only one task at a time. In the next turn, the other player will choose the maximum number of tasks that are non-overlapping from the remaining tasks and so on.

Now, both the players will take XOR (Exclusive - OR) of the total tasks count value obtained in each of their turns. Let the value be A for Alice and B for Bob. Now, If A > B, Alice wins. If B > A, Bob wins. If A = B, it's a tie. Find out the winner?

Note: The ending time Ei for each selected task in each turn should be as less as possible, e.i. if the given tasks are [1,5], [3,8], [6,10], [9,15], Alice can choose maximum 2 tasks in 3 ways as [1,5], [6,10] or [1 5], [9 15] or [3,8], [9,15]. Alice will choose [1 5], [6 10] as the ending time for each selected task is as less as possible in this case.

## HackerEarth Hectic Game problem solution.

`#include <bits/stdc++.h> using namespace std;vector<pair<int, int> > er; map<pair<int, int>, int> hm; int main() {    ios_base::sync_with_stdio(false);    cin.tie(NULL);    int t;    cin >> t;    while(t --) {        int n;        cin >> n;        int S, E;        for(int i = 0; i < n; i ++) {            cin >> S >> E;            hm[{E, S}] ++;        }        int A, B;        A = B = 0;        int turn = 1;        while(hm.size() > 0) {            int cnt = 0;            int prev = -1;            for(auto i : hm) {                if(prev == -1) {                    prev = i.first.first;                    hm[i.first] --;                    if(hm[i.first] == 0)                        er.push_back(i.first);                    cnt ++;                } else {                    if(i.first.second > prev) {                        prev = i.first.first;                        hm[i.first] --;                        if(hm[i.first] == 0)                            er.push_back(i.first);                        cnt ++;                    }                }            }            for(int i = 0; i < (int) er.size(); i ++)                hm.erase(er[i]);            er.clear();            if(turn)                 A ^= cnt;            else                 B ^= cnt;            turn ^= 1;        }        if(A > B)            cout << "Alice\n";        else if(B > A)            cout << "Bob\n";        else            cout << "Tie\n";        hm.clear();    }    return 0;}`

### Second solution

`#include<bits/stdc++.h>#define LL long long int#define M 1000000007#define endl "\n"       #define eps 0.00000001LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}using namespace std;int main()    {        ios_base::sync_with_stdio(0);        int t;        cin >> t;        while(t--){            int n;            cin >> n;            vector<pair<int,int> > v;            for(int i = 1; i <= n; i++){                int a , b;                cin >> a >> b;                v.push_back(make_pair(b , a));            }            sort(v.begin() , v.end());            int score1 = 0 , score2 = 0;            int turn = 0;            while(v.size()){                vector<int> to_erase;                to_erase.push_back(0);                for(int i = 1; i < v.size(); i++){                    if(v[i].second > v[to_erase.back()].first){                        to_erase.push_back(i);                    }                }                if(turn == 0){                    score1 = score1 ^ to_erase.size();                }                else{                    score2 = score2 ^ to_erase.size();                }                while(to_erase.size()){                    v.erase(v.begin() + to_erase.back());                    to_erase.pop_back();                }                turn = 1 - turn;            }            if(score1 > score2){                cout << "Alice" << endl;            }            else if(score1 == score2){                cout << "Tie" << endl;            }            else{                cout << "Bob" << endl;            }        }       }`