# Black & White Ring Game Codechef Solution

Hello coders, today we are going to solve the Black & White Ring Game Codechef Solution whose Problem Code is RING_GAME.

### 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_NAN​ and A_1A1​ as adjacent.

A player can make a move only if, for the updated array A’A′, diff(A’)\gt diff(A)diff(A′)>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 AA with NN elements, some circular continuous segments are [A_1], [A_1, A_2, A_3], [A_{N-1}, A_N, A_1, A_2][A1​],[A1​,A2​,A3​],[AN−1​,AN​,A1​,A2​], etc.
• left cyclic shift of a segment [A_1, A_2, A_3][A1​,A2​,A3​] is [A_2, A_3, A_1][A2​,A3​,A1​]. Similarly, left cyclic shift of segment [A_{N-1}, A_N, A_1, A_2][AN−1​,AN​,A1​,A2​] is [A_N, A_1, A_2, A_{N-1}][AN​,A1​,A2​,AN−1​].

### Input Format

• The first line of input contains a single integer TT, 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 NN, the number of elements.
• The second line of each test case contains NN space-separated integers A_1,A_2, \ldots, A_NA1​,A2​,…,AN.

### 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.

### Sample 1

Input

```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 [A1​,A2​,A3​] 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 (A4​,A1​). After this move, diff([1,0,1,0])=4 as all pairs of adjacent elements have different values. Since diff([1, 1, 0, 0]) 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 in CPP

```#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define f first
#define mt make_tuple
#define s second
#define ll long long
#define NO cout << "NO" << '\n'
#define YES cout << "YES" << '\n'
#define rep(i, a, b) for(int i = a; i < (b); ++i)
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef map<int,int> mii;
class comp{
public:
bool operator()(pair<int,int>&t,pair<int,int>&c){
return t.f > c.f;
}
};
class comp_2{
public:
bool operator()(pair<int,int>&t,pair<int,int>&c){
return t.s > c.s;
}
};
int main() {
int test;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> test;
rep(i, 0, test) {
int n;
cin >> n;
if (n==1){
cout << "Bob" << '\n';
continue;
}
vi arr(n);
rep(j,0,n) {
cin >> arr[j];
}
int dif = 0;
int one = 0;
int z = 0;
if (arr==arr[n-1]){
if (arr){
one++;
} else {
z++;
}
}
int p = 1;
while (p < n){
if (arr[p]==arr[p-1]){
if(arr[p]){
one++;
} else {
z++;
}
}
p++;
}
dif = min(z,one);
if (dif%2==0){
cout << "Bob" << '\n';
} else {
cout << "Alice" << '\n';
}
}
}
```

### Black & White Ring Game Codechef Solution in JAVA

```import java.util.*;
import java.lang.*;
class credsits {
public static void main (String[] args) {
Scanner scan = new Scanner(System.in);
int cases = scan.nextInt();
for(int c = 0; c< cases ;c++){
int[] array = new int[scan.nextInt()];
for(int i = 0; i<array.length;i++){
array[i] = scan.nextInt();
}
if(array.length==1 ||array.length == 2){
System.out.println("Bob");
return;
}
int one = 0;
int zero = 0;
int counter = 0;
for(int i = 0; i<array.length;i++){
if(array[i]==0)zero++;
else one++;
if(i!=array.length-1) {
if (array[i] != array[i + 1]) counter++;
}else if(array[i]!=array)counter++;
}
int max = 2*Math.min(one,zero);
if(((max-counter)/2)%2==0 )System.out.println("Bob");
else System.out.println("Alice");
}
}
}
```

### Black & White Ring Game Codechef Solution in Python

```# Chase2learn
for _ in range(int(input())):
n = int(input())
l = list(map(int, input().split()))
a = 0
b = 2 * min(l.count(0), l.count(1))
for i in range(n):
if l[i] != l[i - 1]:
a += 1
if ((b - a) // 2) % 2 == 0:
print('Bob')
else:
print('Alice')
```

Disclaimer: The above Problem (Black & White Ring Game) is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.

Sharing Is Caring