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).
