Problem Statement
Stone Piles
https://www.hackerrank.com/challenges/stone-piles
There are
N piles of stones where the ith pile has
xi stones in it. Alice and Bob play the following game:
- Alice starts, and they alternate turns.
- In a turn, a player can choose any one of the piles of stones and
divide the stones in it into any number of unequal piles such that no
two of the newly created piles have the same number of stones. For
example, if there 8 stones in a pile, it can be divided into one of
these set of piles: (1,2,5), (1,3,4), (1,7), (2,6) or (3,5).
- The player who cannot make a move (because all the remaining piles are indivisible) loses the game.
Given the starting set of piles, who wins the game assuming both players play optimally?
Input:
The first line contains the number of test cases
T.
T test cases follow. The first line for each test case contains
N, the number of piles initially. The next line contains
N space delimited numbers, the number of stones in each of the piles.
Output:
Output
T lines, one corresponding to each test case containing "
ALICE" if Alice wins the game and "
BOB" otherwise.
Constraints:
1 ≤ T ≤ 50
1 ≤ N ≤ 50
1 ≤ x
i ≤ 50
Sample Input
4
1
4
2
1 2
3
1 3 4
1
8
Sample Output
BOB
BOB
ALICE
BOB
Explanation
For the first case, the only possible move for Alice is (4) -> (1,3).
Now Bob breaks up the pile with 3 stones into (1,2). At this point
Alice cannot make any move and has lost.
Solution:
To solve this problem we need some basic knowledge in game theory. There is a well-written tutorial
about impartial games online. (
http://web.mit.edu/sp.268/www/nim.pdf)
Now back to our problem. The basic idea is to compute the Sprague-Grundy function. We can apply the same argument about the Nim game mentioned in the tutorial, meaning if we have SG function eaqual to zero in the current step, we will get a non-zero value in the next step and if we have a non-zero value at current step, we can always construct a strategy that brings the value to zero again.
Given the initial array, we can compute the SG value, if it is zero then print "BOB", otherwise print "ALICE".
Code:
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <vector>
#include <climits>
#include <list>
#include <unordered_map>
#include <algorithm>
using namespace std;
typedef vector< vector<bool> > myVector;
void compute_sg_fun(int prev, int start, int rest, int key, vector<int>& sg_fun, myVector& record) {
for (int i = start; i <= rest / 2; i++) {
if (rest-i > i) {
int res = prev ^ sg_fun[i] ^ sg_fun[rest-i];
record[key][res] = true;
compute_sg_fun(prev ^ sg_fun[i], i+1, rest - i,key, sg_fun, record);
}
}
int k = 0;
while (record[key][k]) ++k;
sg_fun[key] = k;
}
int main(void)
{
myVector record(51, vector<bool>(51,false));
vector<int> sg_fun(51,-1);
sg_fun[0] = 0;
sg_fun[1] = 0;
sg_fun[2] = 0;
sg_fun[3] = 1;
for (int i = 4; i <= 50; i++) compute_sg_fun(0,1,i,i,sg_fun,record);
int t; cin >> t;
for (int i = 0; i < t; i++) {
int n;
cin >> n;
int res = 0;
for (int j = 0; j < n; j++) {
int c; cin >> c;
res = res ^ sg_fun[c];
}
printf("%s\n", res == 0 ? "BOB" : "ALICE");
}
return 0;
}
