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


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.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;
}
}
}