### PROBLEM LINK

### Panel Members

**Problem Setter:** Sunny Aggarwal

**Problem Tester:** Pushkar Mishra

**Editorialist:** Prateek Gupta

**Contest Admin:** Praveen Dhinwa and Pushkar Mishra

**Russian Translator:** Sergey Kulik

**Mandarin Translator:** Hu Zecong

**Vietnamese Translator:** VNOI Team

**Language Verifier:** Rahul Arora

### DIFFICULTY:

Easy

### PREREQUISITES:

Game Theory

### PROBLEM:

Given a string of length N which contains exactly one ‘W’ character and rest of the characters as ‘B’. The only operation allowed per turn is to remove non-empty set of ‘B’ characters from either side of ‘W’ character. Both the players play optimally. The one who is not able to move in his turn ends up loosing. Predict the winner of the game.

### EXPLANATION

The two groups of black characters can be understood as two piles of coins such that each player in his turn can take any number of non-empty coins from either of the pile. So, the one who is not able to move in his respective turn looses the game.

**Solution for Subtask 1 & 2:**

Constraints for these subtasks allow us to use a simple **DP**.

**Approach**

Let us say that the count of coins in both the piles be x and y respectively. We can now apply DP to decide the winner by taking into account every possibility at each stage. At any particular instant, current player can take any number of coins from either of the piles. Hence, he will choose the move in which the next player will be at a loosing position from whatever he tries. This move will be winning move for the current player. If he does not find any move for which the next player can be at a loosing position, that means it is a loosing position for the current player. The pseudo code below will help you to explain the recurrence better.

**Pseudo Code**

```
bool F(x,y) {
bool ans = false;
for ( int i = 1; i ≤ x; i++ ) ans |= (!F(x-i,y));
for ( int i = 1; i ≤ y; i++ ) ans |= (!F(x,y-i));
return ans;
}
```

These states can then be memoized to give an overall complexity of \mathcal{O}(N^{3}).

**Solution for Subtask 3:**

**Simple Observation**

One simple observation is that if two piles have the same number of coins, it will always be a loosing position for the current player. That being said, any of the player would like to balance the two piles after his turn so that the next player who takes the turn ends up in the loosing position. There exists no other loosing position except both the piles having same number of coins.

Hence, it suffices to check the following condition for predicting the winner of the game.

```
return (s.length()%2 != 0 && s.find("W") == s.length()/2 ) ? "Chef" : "Aleksa"
```

**Nim Game Approach**

The problem can also be modelled into standardised Nim game problem.

There is a well know formula to detect the winning player if both the players play optimally in the mentioned pile game.

If Xor of number of coins in all the piles is zero, that means it is a loosing position for the first player. Otherwise, it will always be a winning position. In our case, XOR will be the bitwise XOR of number of characters before and after the single ‘W’ character in the string. Read this content to know more about the proof of this formula.

For details on the implementation, please look at the below mentioned solutions

### COMPLEXITY

Overall complexity for the solution to pass all the subtasks is \mathcal{O}(N).