BWCELL - Editorial

PROBLEM LINK

Practice
Contest

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

SOLUTIONS

2 Likes

i solved it in a simple way:
https://www.codechef.com/viewsolution/8840559

5 Likes

It suffices to check if W occurs in the middle of the array, if not, in one move Aleksa can bring it to such a position. This position guarantees defeat for the person who will play next, who will be chef. In such a position, Aleksa wins. Else chef wins

However the solution provided in the editorial has a broader application in the field of game theory

2 Likes

If there are equal ‘B’ on each side of single ‘W’ then it is for sure that Chef will win because for every move that Aleska does, Chef can do the same on the other side And finally Chef would be last one to finish all B’s. Otherwise Aleska will always be the winner.

1 Like

My simple AC solution:slight_smile:

Concept same as explained by vsp4

bbbwbbb can this happen that aleksa chooses 2 b’s on left hand side and then chef chooses the 3rd one on the left side and aleksa chooses all the 3 b’s on the right side? in that case chef will loose !

*finish all B’s,not W’s. :stuck_out_tongue:

But the question says that they will play optimal moves. If Aleksa chooses 2b’s on left hand then the next optimal move for chef would be to choose 2b’s on right hand side so next is bwb with Aleksa turn in which again Aleksa will loose.

is it possible that if chef chooses left on first turn then he can choose right on his next turn?

Yes they can. In a single move, they can choose any side and then remove any amount of B’s on that side.

@vsp4 thanx a lot

Does it really matters how many b’s are in each pile as they can pick from both ?