[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.
• A 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}]$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

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: BOB, bob, boB, and Bob are all identical.

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.