Black & White Ring Game Codechef Solution

Hello Programmers In this post, you will know how to solve the Black & White Ring Game Codechef Solution. The Problem Code is RING_GAME.

Black & White Ring Game Codechef Solution
Black & White Ring Game Codechef Solution

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.

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';
      }
    }
}
       

Ezoicreport this adBlack & 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");
        }
    }
}
Ezoicreport this ad

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 BrokenProgrammers. This tutorial is only for Educational and Learning purpose.

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.

Next: AND Plus OR Codechef Solution

Sharing Is Caring

Leave a Comment

Ezoicreport this ad