# Black&White Ring Game CodeChef Solution

### We Are Discuss About CODECHEF SOLUTION

Black&White Ring Game CodeChef Solution

## Black&White Ring Game CodeChef Solution ## Problem

Alice and Bob are playing a game. Alice goes first.

They have a binary circular array A with N elements. In one move, a player can:

• Choose a circular continuous segment of the array and perform a left cyclic shift on the chosen segment.

We define the term diff(A) as the number of pairs of adjacent elements with different values. Note that we also consider A_N and A_1 as adjacent.

A player can make a move only if, for the updated array A’diff(A’)\gt diff(A).

The player who is unable to make a move, loses. Find the winner of the game if both players play optimally.

Note:

• For an array A with N elements, some circular continuous segments are [A_1], [A_1, A_2, A_3], [A_{N-1}, A_N, A_1, A_2], etc.
• left cyclic shift of a segment [A_1, A_2, A_3] is [A_2, A_3, A_1]. Similarly, left cyclic shift of segment [A_{N-1}, A_N, A_1, A_2] is [A_N, A_1, A_2, A_{N-1}].

### Input Format

• The first line of input contains a single integer T, the number of test cases. The description of the test cases follows.
• Each test cases consists of two lines of input.
• The first line of each test case contains a single integer N, the number of elements.
• The second line of each test case contains N space-separated integers A_1,A_2, \ldots, A_N.

### Output Format

For each test case, if Alice will win print Alice, otherwise print Bob.

You may print each character in Uppercase or Lowercase. For example: BOBbobboB, and Bob are all identical.

### Constraints

• 1 \leq T \leq 100
• 1 \leq N \leq 10^6
• 0 \leq A_i \leq 1
• The sum of N over all test cases won’t exceed 10^6.

### Sample 1:

Input

Output

3
3
1 0 1
4
1 1 0 0
8
1 0 1 0 0 0 1 1

Bob
Alice
Bob

### Explanation:

Test case 1: Alice can not perform any move. Thus, Bob wins.

Test case 2: Alice can perform the following move:

• Choose the segment [A_1,A_2,A_3] and perform left cyclic shift. Thus, A becomes [1,0,1,0].
Also, diff([1, 1, 0, 0]) = 2 as pairs of adjacent elements with different values are (A_2, A_3) and (A_4, A_1). After this move, diff([1, 0, 1, 0]) = 4 as all pairs of adjacent elements have different values. Since diff([1, 0, 1, 0]) \gt diff([1, 1, 0, 0]), this move is valid.

After performing the move, Bob has no valid move left. Thus, Alice wins. ## Black&White Ring Game CodeChef Solution

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here JOIN NOW 