You are not logged in. Please login at www.codechef.com to post your questions!

×

ABGAME - EDITORIAL

7
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Praveen Dhinwa
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Game Theory, Nim's Game and Observations.

PROBLEM:

Two players $A$ and $B$ plays a game on a string consisting of characters '.', 'A' and 'B'. Each occurrence of character 'A' and 'B' is assigned direction from left to right alternatively, starting from the right direction. '.' represent empty spot.

Player A can move any character marked 'A' in the predetermined direction any number of steps as long as not jumping over any of character 'A' and 'B', while player B can move any character marked 'B' in the predetermined direction in the same manner.

Players make move alternatively, with player A playing first. Determine who will win, if both of them play optimally and the player making the last move wins.

For this problem, I am counting only A and B as characters, for a simpler explanation.

QUICK EXPLANATION

  • Except for the last character if the number of characters present is odd, all characters are assigned directions such that in pairs of two, Characters are moving toward each other. ie. First and second are moving toward each other, Third and Fourth characters are moving toward each other and so on. If there are an odd number of characters, the last character is moving toward the right end.
  • Let reserve moves represent the number of moves a player can perform independently of other moves. More the reserve moves, better for that person. Since he wants to play the last move.
  • If any pair of adjacent characters moving toward each other belongs to the same player, that player can move either of his characters toward the other in maximum $d$ moves, if $d$ is the number of empty cells between both characters. So, That player's reserve moves increases by $d$. In case of the last character where the last character is moving toward the right border, that player has an additional $d$ reserve moves, if there are $d$ empty cells between last character and right border.
  • If the pair of adjacent characters are different and there are $d$ empty cells between both characters, It can be reduced to the game of Nim, with sizes of piles being the number of cells between every pair of adjacent numbers, where the losing player has to use its reserve moves first.
  • The final game is the game of Nim with a finite number of pass moves for both players.
  • If Number of pass moves differ, The player having the higher number of pass moves will always win. Otherwise, It is simply a Game of Nim, with the winner of Nim game being the winner of the Game.

EXPLANATION

This is not a single game, but a combination of Nim's game combined with a simple turn game.

Let us see how the directions first. Consider example A..A...A..B..B....B. The first character is assigned direction right, second is assigned left, third is assigned right and so on. This way. Directions are assigned as R..L...R..L..R....L.

It is easy to notice that the first and second characters are moving together, third and fourth character are moving toward each other and so on. So, Every pair of characters can be treated separately.

Let us define the concept of reserve moves for a player as the number of moves a player can perform independently of the moves performed by the opponent.

Playing a simple game for understanding

Player A can perform X moves, while player B can perform Y moves, independent of each others' moves. If player A is first to move, player A wins if $X > Y$. But if player B is second to move, player A wins if $X \geq Y$. It is not easy to prove how.

The first move matters.

Coming back to original problem

When both characters of the pair are same, both characters are controlled by the same player, and cannot be affected by opponent's moves. This player can make minimum 1 and maximum $d$ moves using these pair of characters only. Since a player wants to play as many moves as possible, it is optimal to spend $d$ moves on this pairs. This will add to reserve moves available to the player.

Similarly, If there are an odd number of characters available, the last character is assigned right direction and it will move toward the right border. This will add $d$ moves to reserve moves of player, to whom the last character belongs.

Now comes the tricky part.

When both characters of the pair are different. Either of the players can move any number of steps at a time, moving only one character in one move until there is no empty cell left in between. Notice that Either player will run out of moves if and only if there are no such pairs, with empty cells in between. Hence, in the final state, all such pairs will compress, removing all empty cells between the characters.

Let us consider an example A..B.A...B

Winning player is A with the strategy to move his character at position 6 to position 7, and then in subsequent moves, moving his character in the same way as B moves.

Let's try to reframe the problem as Number of empty cells between first such pair is 2, while the number of empty cells between the second pair is 3. Playing in turns with A moving first, Each player at a move is allowed to reduce exactly one of the numbers by any non-zero number. The player unable to make a move loses. Find the winner if both players play optimally.

Does the above rings a bell?

Give it a try!!

The above statement is exactly the Nim's game. :) (Explaining Nim's Game later).

Hence, the problem is just the Nim's game, with both players having a given number of pass moves (possibly different number of moves). In case initially the Nim's game is in a winning position, A will Make move so as to give B a losing position in Nim's game. In case the given game was already in a losing position, A will use a reserve move. In either way, Now player B and A, in turns, use their pass moves till pass moves are exhausted for a player, and is forced to make a move in losing position in Nim, thus losing the game.

Another way of writing the winning idea is, If both players have an unequal number of reserve moves, the player with more reserve moves wins, otherwise the winner of Nim's game wins. It is not hard to follow, once you get the idea of the above solution.

About Nim's Game

I had seen a post asking details on Game Theory but couldn't reply, so, here we go!

I will not be going in too much detail, will be using informal language, just explaining the ideas with brief proof. Details you can find on various blogs, for example, here and here.

The Nim's game at the core is the problem with $N$ piles of stones containing a non-zero number of stones. Both players, in their turns, are allowed to remove any positive number of stones from exactly one pile. The player unable to make a move loses.

The solution is based on the idea of xor-sum.

Let us see the final state. In this state, none of the pile has any stones left. In terms of xor-sum, the xor-sum of the number of stones in each pile is 0. The previous state must have included one pile containing say $x$ stones, having $x$ as xor-sum and is a winning state.

We know, that in game theory, The states visited from last to first is something like losing state, winning state, losing state alternatively and so on. So, the second last state visited must be losing state for the player to move.

If it was like, that before second last move, there was only one pile having more than $x$ stones and losing player removed stones to leave $x$ stones, Then this is not an optimal strategy as the losing player could have removed the whole pile, winning the game.

So, in second last move, there should be exactly two piles. Suppose there were $y$ stones in that pile. Suppose $x \neq y$. Even now, the player making the current move can win, by removing stones in such a way to get the same number of stones in both piles, thus again winning the game.

Thus, for second last state to be losing, the required condition becomes $x == y$.

Similar reasoning escalates to more piles. (Equality changes into zero xor-sum).

The reasoning is simplified in terms of xor-sum of piles. See, All losing states have xor-sum of stones count in piles 0. The reasoning is, that If some piles have xor-sum 0, then in next turn, it will definitely change into some non-zero value.

And, If the piles have xor-sum non-zero, it is always possible to remove stones so as to make xor-sum 0.

This way, a parallel is drawn between Nim's game and xor-sum, and we get the result as we know today. :)

That's all for today. Feel free to share anything useful related to Game theory.

Time Complexity

Time complexity is $O(|S|)$ where $|S|$ is the length of string and we need to iterate over it only once.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution
Tester's solution
Editorialist's solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

asked 19 Nov '18, 12:53

taran_1407's gravatar image

5★taran_1407
3.8k2386
accept rate: 22%

edited 19 Nov '18, 13:01

admin's gravatar image

0★admin ♦♦
19.7k350498541


<copy>

Woah!! This long editorial, scary even after solving this problem.

</copy>

For those who are clueless. https://discuss.codechef.com/questions/135756/fctr-editorial/135773

Looks like someone went through a change of mind @taran_1407 ? :p

link

answered 19 Nov '18, 13:51

vijju123's gravatar image

4★vijju123 ♦♦
15.2k11859
accept rate: 18%

edited 19 Nov '18, 13:53

1

.......XDD

(19 Nov '18, 14:48) l_returns5★

I certainly remember what i said at that time. And, it was true :P

This one went long because of additional explanation of nim's game i provided.

(19 Nov '18, 18:30) taran_14075★

Congrats, its true in this case as well now :)

This one went long because of additional explanation of nim's game i provided.

Mine went long because I wanted a nice formatting to explain maths :)

(19 Nov '18, 18:50) vijju123 ♦♦4★

Video solution with explanation: https://youtu.be/Gp90sUHZ6Y0

link

answered 20 Nov '18, 11:51

code_report's gravatar image

3★code_report
3305
accept rate: 0%

Hello @saurav0001, I am unable to see your code.

link

answered 19 Nov '18, 19:30

vipin1407's gravatar image

5★vipin1407
2045
accept rate: 13%

Nice solution.

CodeChef seems to be obsessed with using Nim everywhere this year xD.

link

answered 19 Nov '18, 13:54

codesniper99's gravatar image

3★codesniper99
1186
accept rate: 7%

I think it was the first question on NIM's game- rest game theory questions were brute forcing optimal solutions?

(19 Nov '18, 14:13) vijju123 ♦♦4★

This one actually used Nim's game. Rest were just game theory ones, not exactly Nim's games.

(19 Nov '18, 18:31) taran_14075★
2

You can say that for game theory...
Codechef showed me how bad I am at game theory..XD
Or at only logical questions which has nothing about data structure...

(19 Nov '18, 20:13) l_returns5★

i did the same but it gave WA:- https://ideone.com/k6pI0F

link

answered 19 Nov '18, 17:43

saurav0001's gravatar image

4★saurav0001
1
accept rate: 0%

Another way to look at it is to compare the total number of each player's moves if they play optimally. Player A wins iff he has more moves available. First, count the number of "pass moves" for each player. If the Nim game is initially in a winning position it gives one extra move to player A - add 1 to his move count, otherwise both players have equal numbers of moves in the Nim game.

link

answered 21 Nov '18, 02:21

eugalt's gravatar image

3★eugalt
2827
accept rate: 4%

Short and sweet explaination...
Can be called "quick explaination"... Nice one...

(22 Nov '18, 02:41) l_returns5★
link

answered 21 Nov '18, 09:41

saurav0001's gravatar image

4★saurav0001
1
accept rate: 0%

@saurav0001 what you are doing in your submission is wrong. You need to study more about nim games and how to determine the winner in case of nim games (xor of the piles' sizes etc.).

link

answered 22 Nov '18, 19:33

roll_no_1's gravatar image

6★roll_no_1
413
accept rate: 20%

Can someone plz explain why we are making pairs and make them move towards each other only? I think i'm missing something. Plz help!

link

answered 24 Nov '18, 10:18

pk301's gravatar image

3★pk301
62710
accept rate: 16%

Because every character at odd position (out of non-empty characters) is moving toward right, while other characters are moving toward left.

See, .A...B..B..B First A moves toward right, First B toward left, Second B toward right and third A toward left. So, they end up moving toward each other.

(24 Nov '18, 11:25) taran_14075★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3,705
×636
×308
×212
×50
×40
×16

question asked: 19 Nov '18, 12:53

question was seen: 2,322 times

last updated: 24 Nov '18, 11:25