Hello coders, today we are going to solve the Black & White Ring Game Codechef Solution whose Problem Code is RING_GAME.
As you already know that this site does not contain only the Codefchef solutions here, you can also find the solution for other programming problems. I.e. Leetcode, C programs, C++ Programs Solutions, Python Programs, Web Technology, Data Structures, RDBMS Programs, and Java Programs Solutions.
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
LinkedIn Skill Assessment Answers
Coursera Quiz Answers
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.
Finally, we are now, in the end, I just want to conclude some important message for you
Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.
Please share our posts on social media platforms and also suggest to your friends to Join Our Groups. Don’t forget to subscribe.
