All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Hectic Game
Tag(s):

Algorithms, Bit manipulation, Easy, Greedy algorithm, Hash function

Problem
Editorial
Analytics

Alice and Bob are playing a hectic game in which there are a total of $$N$$ tasks each consisting of a start time $$S_i$$ and end time $$E_i$$.

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 \gt B$$, Alice wins. If $$B \gt A$$, Bob wins. If $$A = B$$, it's a tie. Find out the winner?

Note: The ending time $$E_i$$ 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.

Input Format

The first line of the input will be $$T$$, the total number of test cases.

The first line of each test case will be $$N$$, the total number of tasks.

Then $$N$$ lines follow each consisting of two space-separated integers $$S_i$$ and $$E_i$$ the start time and the end time.

Output Format

For each test case print the respective result Alice, Bob or Tie.

Constraints

\(1 \le T \le 10\)

\(1 \le N \le 10^3\)

\(1 \le S_i \le E_i \le 10^9\)

SAMPLE INPUT
1
5
1 2
1 3
4 5
3 4
1 5
SAMPLE OUTPUT
Alice
Explanation

Initially, there are maximum 2 tasks Alice can choose i.e. $$[1\;2]$$ and $$[3\;4]$$. From the remaining tasks, Bob can choose maximum 2 tasks i.e. $$[1\;3]$$ and $$[4\;5]$$. Now, Alice chooses the 1 last task i.e. $$[1\;5]$$.

$$A$$ = 2 ^ 1 = 3

$$B$$ = 2

$$A > B$$ thus, Alice wins.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

QuEST Global

Challenge Name

QuEST Global Coding Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?