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.

Black & White Ring Game 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_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: BOBbobboB, and Bob are all identical.

Constraints

Black & White Ring Game Codechef Solution

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.

Sharing Is Caring