Hello coders, today we are going to solve the Black & White Ring Game Codechef Solution whose Problem Code is RING_GAME.
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_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.
- A 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.
Constraints
Sample 1
Input
3 3 1 0 1 4 1 1 0 0 8 1 0 1 0 0 0 1 1
Output
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[0]==arr[n-1]){
if (arr[0]){
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[0])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
# cook your dish here
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.
