[Hackerrank] Manasa and Prime Game

Problem Description (Credited to Hackerrank)
Manasa loves the NIM Game, but having played the same game so many times, she gets bored one day. So she wants to change the rules of the game. As she loves prime numbers, she makes a new rule: any player can remove only prime number of balls from a bucket. But there are infinite prime numbers. So to keep the game simple, a player can remove only x number of balls from a bucket, where x belongs to the set S.




 S={2,3,5,7,11,13}

Now whole game can be described as follows:
Given N number of buckets and kth bucket having Ak number of balls, a player can choose a bucket and remove x number of balls from that bucket where x belongs to S. Manasa plays the first move against Sandy. Who will win if both of them play optimally?

Input Format 
The first line contains an integer T i.e. the number of test cases.
First line of each test case will contain an integer N i.e. number of buckets.
Next lines will contain N integers.

Output Format 
Print the name of the winner - "Manasa" or "Sandy".

Constraints
1≤T≤10 
1≤N≤104 
1≤Ak≤1018

Sample Input

2
2
10 10
3
2 2 3

Sample Output

Sandy
Manasa

Solution

This is another example of problems in game theory. If Permutation Game is solved using Minimax algorithm, this problem requires some knowledge about Nim games, and Grundy number (or Nimber).
You can read more about Nim Games and Grundy number using reference links at the end of the post, but I will describe it shortly so that you get how to do (even without understanding Nim Games and Grundy numbers!!!).

In this type of problem, one game is a combination of multiple sub-games. At each time, a player chooses a sub-game to play. Who is the last person to make a move is the winner. And to decide who is the winner, we need to calculate Grundy numbers for all the sub-games, and take the XOR value of them. If this value > 0, then the first player is the winner. Otherwise, the second player is the winner !!! Sound like magic? Again, I suggest you read through everything I put in reference links to understand the theory behind.

So what is the sub-games here? Assuming that the 2 players play only with a bucket. So this is a sub-game.

Now, how to calculate Grundy number for a sub-game? Call C is the current state of the sub-game (In this problem, C is the number of balls in the bucket). Call T1, T2, ..., Tn are all possible states can be reached from C within a single move. And call G is a function on these states. G is defined as followed:

G map a state to non-negative integer.
G(losing state) = 0
G(C) = smallest number that not in the set {G(T1), G(T2), ..., G(Tn)} where T1, T2, ..., Tn are all possible states reached from current state C by a single move.

How to apply for this problem?
First, we need to define losing state. Losing state is the state a player cannot remove balls. In this problem, losing states are 0 and 1. Therefore, we have G(0) = G(1) = 0.

So we have: G(2) = 1. (Why?), G(3) = 1 (Why?), G(4) = 2 (Why?), and so on.

And the problem ask us to calculate Grundy number for 1<=Ak <= 10^18!
The Grundy number G(Ak) can be calculated using Dynamic Programming if Ak is small. But 10^18 is way too big. We have to find another way.

We see that, from the current state C, we can only move to maximum 6 other states. This means that the Grundy numbers may be at most 6 (Why?). That means there is a high chance that they are periodic! Yes, they are periodic.

Hence, I wrote a quick Python script to see if it is periodic.

def run():
  n = 100
  dp = [0]*(n+1)
  a = [2,3,5,7,11,13]
  b = [0] * (23)
  for i in range(2, n+1):
    for k in a:
      if i >= k:
        b[dp[i-k]]= 1
    for k in range(len(b)):
      if b[k] == 0: 
        dp[i] = k
        break
    for k in range(len(b)): b[k] = 0
  print dp
if __name__ == "__main__":
  run()

And the result is

[0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1
, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2,
2, 3, 3, 4, 0, 0]

So the period will be values = [0, 0, 1, 1, 2, 2, 3, 3, 4]. Simple, isn't it?
And G(Ak) = values[ Ak % 9].
Now, we just need to XOR up all Grundy numbers G(A1) ^ G(A2) ^ ... ^ G(An).

Below is the code in java for your reference.
Before seeing the solution, try yourself with the following test case:

5
10
84 87 78 16 94 36 87 93 50 22
10
63 28 91 60 64 27 41 27 73 37
10
12 69 68 30 83 31 63 24 68 36
10
30 3 23 59 70 68 94 57 12 43
10
30 74 22 20 85 38 99 25 16 71

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        int t = ni();
        for(int i=0; i<t; i++){
            System.out.println(solve());
        }
    }
    
    public static int[] values = new int[]{0, 0, 1, 1, 2, 2, 3, 3, 4};
    public static String solve(){
        int n = ni();
        long ak;
        long nimber = 0; //or grundy number
        for(int i=0; i<n; i++){
            ak = nl();
            nimber ^= values[(int) (ak % values.length)];
        }
        if(nimber > 0) return "Manasa";
        return "Sandy";
    }
    
    public static Scanner sc = new Scanner(System.in);
    public static int ni(){
        return sc.nextInt();
    }
    public static long nl(){
        return sc.nextLong();
    }
}

Reference links:
Combinatorial Games - PDF (Standford course)
Sprague-Grundy Theorem (Wiki)
Grundy Numbers (Nice blog post)