Xtreme 10.0 - Game of Stones
Hi peeps :) I brought a new game for algorithmic geeks who enjoy solving games rather than playing.
Problem
Alice and Bob play a game. The game is turn based: Alice moves first, then Bob, and so on. There are N piles of stones; in every pile there is an odd number of stones. At every turn, the one to play must pick a pile and splits it into 3 piles with an odd number of stones each.
The player who cannot split any pile loses. As this game is too simple for both of them, they decided to play multiple games in parallel. The rules remain the same, but at every turn, the one to play must first pick a game and then split a pile only in that game. The one who loses is the one that can’t split any pile in any game, i.e. all the piles in all the games have only 1 stone. Bob still thinks that he is at a disadvantage since he is the second to move. Your task is to find the winner if both the players play optimally.
Original problem: https://www.hackerrank.com/contests/ieeextreme-challenges/challenges/game-of-stones-1-1
Input Format
The input begins with an integer T, giving the number of test cases in the input.
Each test case begins with an integer G, on a line by itself, giving the number of games to be played in parallel.
The G games are then described in two lines as follows: The first line gives the number of piles in the game, and the second contains the number of stones in each of the piles.
Constraints
1 <= T <= 10
1 <= [Number of piles in all games in a test case] <= 105
1 <= [Number of stones in a pile] <= 109
Output Format
For each test case, output the winner, i.e. either Alice or Bob, on a line by itself.
If you want to solve this on your own, STOP RIGHT NOW!
Method to Solve
This may seems like a hard problem to some, but believe me it is not.
First of all we need to identify what are the facts that really matters when finding the winner of the game.
Take the fact ‘As this game is too simple for both of them, they decided to play multiple games in parallel’. Does playing multiple games really matter? No. If they have to play until all the piles are left with 1 stone, it is the same as playing one game which has all the piles of all the games at the beginning.
Hence ‘but at every turn, the one to play must first pick a game and then split a pile only in that game’ does not really matter.
Now think about this phrase. ‘Your task is to find the winner if both the players play optimally.’ Is there a way to play this game optimally? Let’s consider a game with only one pile which has 9 stones. Then keep breaking it down to 3 smaller piles with an odd number stones each until there is no possible splits further. Below are the all possible ways of doing it.
- 9 = (7+1+1) = ((5+1+1))+1+1) = (((3+1+1)+1+1)+1+1) = (1)*9
- 9 = (5+3+1) = (5+(1+1+1)+1) = (((3+1+1)+(1+1+1)+1) = (1)*9
- 9 = (5+3+1) = ((3+1+1)+3+1) = (((3+1+1)+(1+1+1)+1) = (1)*9
- 9 = (5+3+1) = ((3+1+1)+3+1) = (((1+1+1)+1+1)+3+1) = (1)*9
- 9 = (3+3+3) = ((1+1+1)+3+3) = ((1+1+1)+(1+1+1)+3) = (1)*9
So whatever the method you used to split the piles (without breaking rules of the game), it ends being piles of 1 stone in 4 turns. Try doing this for a pile of 7 stones, 11 stones, 13 stones,…
The number of turns need to end the pile would change with the starting number of stones in the pile, but it would not change with the way you split it.
The number of turns for a pile can be calculated by taking the integer division of stones in the pile with two. For a pile of 9 stones in the beginning would take 9//2 = 4 turns.
Then why the heck this much of unnecessary details??? Can’t you get it. Simple, to FOOL you!
Then what does really matter when deciding the winner? How can we select the winner?
That is easy..!
- Make a one big game which includes all the piles from all original games.
- Calculate the integer division of 2 for all piles.
- Take the sum of those values. (This sum equals to the number of turns the game can be played)
- If the sum is odd, ‘Alice’ wins else ‘Bob’ wins. (Remember Alice starts to play always and then Bob and so on.)
Code on Github
For more understanding, I have added a working code in python3 below.
Hope you guys understood what I said. If you need further clarifications do not hesitate to comment :). Thank you for reading.
