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 << "Alicen";
        else if(B > A)
            cout << "Bobn";
        else
            cout << "Tien";
        hm.clear();
    }
    return 0;
}

Second solution

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "n"       
#define eps 0.00000001
LL 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;
            }
        }   
    }

coding problems solutions