Game Theory in Competitive Programming Part 7

Find the player with least 0s after emptying a Binary String by removing non-empty substrings

Photo by Pakata Goh on Unsplash

Here is the link to the problem : Binary String

Welcome to part 7 of this series, in case you have missed part 6, here is the link: Part 6

Problem Statement:

Given a binary string S, the task is to determine the winner of the game when two players play a game optimally in alternate turns with the given string, as per the following conditions:

• Player 1 always starts first.
• In each turn, a player removes a non-empty substring from the given string.
• After the given string is emptied, the player having the minimum count of 0s will win the game. If both players have equal count of 0s, then print “Tie”.

Examples:

Input: S = “00011”
Output: Player 1
Explanation: Substrings can be chosen as follows:
Turn 1: Player 1 removes the substring S[4…5]. Therefore, Player 1 contains “11”.
Turn 2: Player 2 removes the substring S[0…0]. Therefore, Player 2 contains “0”.
Turn 3: Player 1 removes the substring S[0…0]. Therefore, Player 1 contains “110”.
Turn 4: Player 2 removes the substring S[0…0]. Therefore, Player 2 contains “00”.
Therefore, Player 1 wins the game.

Input: S = “000011”
Output: Tie
Explanation: Substrings can be chosen as follows:
Turn 1: Player 1 removes the substring S[4…5]. Therefore, Player 1 contains “11”.
Turn 2: Player 2 removes the substring S[0…0]. Therefore, Player 2 contains “0”.
Turn 3: Player 1 removes the substring S[0…0]. Therefore, Player 1 contains “110”.
Turn 4: Player 2 removes the substring S[0…0]. Therefore, Player 2 contains “00”.
Turn 5: Player 1 remover the substring S[0…0] . Therefore , Player 1 contains
“1100”.

Since both the players have same number of zeroes at the end of the game , thus Result is Tie

Hint: Basic idea is clear that if 0’s occur even time than it would be a ‘tie’ , think greedily what will happen if they occur odd times how does this effect the game.

Approach: The problem can be solved based on the following observations:

• If count of 0s in the string is an even number then the player 1 and player 2 choose the substring “0” in each turn and no player will win this game.
• Otherwise, store the count of consecutive 1s in an array and apply the game of nim rule on the array.
• Nim-Sum: The cumulative XOR value of the number of coins/stones in each piles/heaps(here consecutive 1s) at any point of the game is called Nim-Sum at that point.

Follow the steps below to solve the problem:

• Initialize a variable, say cntZero, to store count of 0s in the string.
• Initialize a variable, say cntConOne, to store the count of consecutive 1s in the string.
• Initialize a variable, say nimSum, to store the Nim-Sum of consecutive 1s of the given string. So we will be checking who will be taking first zero in case the count of zeroes is odd because lets say player1 takes the first zero and there are 3 zeroes in total then he will also be taking the last zero and eventually will have more zero thus loses the game . NimSum would help us to know who would take the last consecutive set of ones , since whoever takes the last consecutive set of one will eventually win the game as the next player will be taking the zeroes first and as explained abould would eventually lose.
• Traverse the array and calculate count of 0s and nimSum.
• Finally, check if the value of cntZero is an even number or not. If found to be true, then print Tie.
• Otherwise, check if value of nimSum is greater than 0 or not. If found to be true, then print Player 1.
• Otherwise, print player 2.(why so ? we will understand this by doing dry run ) .

Source Code:

void FindwinnerOfGame(string& S){
  int cntZero = 0;// Stores total count of 0s in the string
  
  int cntConOne = 0;// Stores count of consecutive 1s
  
  int nimSum = 0;// Stores Nim-Sum on count of consecutive 1s
  
  int N = S.length();// Stores length of the string
  
  for (int i = 0; i < N; i++) {
 if (S[i] == '1') {// If the current character is 1
      
      cntConOne += 1;// Update cntConOne
      
    }else {
      
      nimSum ^= cntConOne;// Update nimSum
      
      cntConOne = 0; // Update cntConOne
      
      cntZero++;// Update cntZero
      
    }
  }
nimSum ^= cntConOne;// Update nimSum
// If countZero isan even number
  if (cntZero % 2 == 0) {
    cout << "Tie";
  }
// nimSum is not 0
  else if (nimSum) {
    cout << "player 1";
  }
// If nimSum is zero
  else {
    cout << "player 2";
  }
}