Subarray Game CodeChef Solution

Problem

We define the goodness of any array $B$ of length $M$ as: \sum_{i = 1}^{M – 1} |B_{i + 1} – B_{i}|∑i=1M−1​∣Bi+1​−Bi​∣ (Here $|X|$ denotes the absolute value of $X$). In particular, goodness of any array of length $1$ is $0$.

Alice and Bob have an array $A$ containing $N$ distinct elements and they play a game with it.
Alice starts the game after which both the players make moves alternatively. In one move:

• A player can delete any subarray from $A$ such that the goodness of $A$ does not change.

Formally, the player chooses indices $L$ and $R$ such that $1\le L\le R\le \mathrm{length}(A)$ and removes the subarray [A_L, A_{L + 1}, \ldots, A_R][AL​,AL+1​,…,AR​] from $A$ such that the goodness of $A$ does not change.

For e.g. $A=[3,1,2,4]$, a player can select $L=3,R=3$, then the resulting array will be $[3,1,4]$. Initially, the goodness was $|1-3|+|2-1|+|4-2|=5$. After the move, the goodness is $|1-3|+|4-1|=5$. Here we can observe that the goodness does not change.

The player who is not able to make a move loses. If both the players play optimally, determine who out of Alice and Bob will win the game.

Input Format

• The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer $N$ — the size of the array $A$.
• The second line of each test case contains $N$ space-separated integers A_1, A_2, \dots, A_NA1​,A2​,…,AN​ denoting the array $A$.

Output Format

For each test case, output the winner of the game if both players play optimally.

You may print each character of Alice and Bob in uppercase or lowercase (for example, aLiCe, ALIce, alice will be considered identical).

Constraints

Sample 1:

2
3
1 3 2
4
1 2 3 4

Bob
Alice

Explanation:

Test case 1: Alice can not make any moves such that the goodness of the array does not change. Therefore Bob wins.

Test case 2: Alice can choose $L=2,R=3$ and remove the subarray [A_2, A_3][A2​,A3​]. The resulting array is $[1,4]$.

• Goodness of the array before the operation $=|2-1|+|3-2|+|4-3|=3$.
• Goodness of the array after the operation $=|4-1|=3$.

Thus, the array has the same goodness as before. Now Bob can not make any move. Therefore Alice Wins