WGME  Editorial
Problem Link:
PracticeAuthor, Tester and Editorialist:
dragonemperor
Difficulty:
MediumPreRequisites:
bitmasking, recursive memoization, Grundy numbersExplanation:
Grundy number: Tutorial
Brief explanation of Grundy number:
Basically, we assign a number to each of the possible moves in a game. The terminal points will have value 0. For a given position, we collect all the valid moves and collect the Grundy value of the moves. Then we find the smallest positive number that is not present in the collection. That smallest number is the Grundy number of the present value (state).
If the initial position has Grundy value 0, the player who starts loses, else he wins.
Now how to implement this?
First observation is the length of the string (10 at max). This suggests a brute force approach. Since we can remove character from any position, lets remove the character from each position of the string and check for that string (which would represent one of the next move). How to keep track of which position we have removed?
Let’s use bit masking for that. For initial string of length ‘n’ let’s use the mask 2^n – 1. This is the entire string. For each position, if the bit of that position in the mask is set, then that character is included in the present set.
int solve(int mask)
{
List mylist; //to store grundy value of the present string
for(int i = 0; i < 20; i++) //I < length of string, 20 is sufficiently large
{
if(mask & (1 << i)) //means bit is set
{
mask = mask ^ (1 << i); //flip the bit
int temp = solve(mask); //find the grundy value of the present substring
mask = mask ^ (1 << i); //make mask as it was
mylist.push_back(temp); //adding the grundy values of the next moves
}
}
//find the minimum nonnegative number not present in the list, say min
//that number is the grundy value of the present string
return min; //find yourself
}
We can store the grundy value of each move in a list and at the end find the smallest number not present in the list.
Now the function solve is recursive, so we need to add terminating condition, else the function will run indefinitely. What could be the terminal condition?

empty string that is when mask is 0

if the present string doesn’t have any duplicates
Let’s add the code.
if(mask == 0)
return 0;
for second condition:
int hash[26];
for(int i = 0; i < 20; i++)
{
If(mask & (1 << i))
{
Hash[ip[i]‘a’]++;
}
}
int flag = 0; //set it to 1 if an element is present more than 1 time
for(int i = 0; i < 26; i++)
{
if(hash[i] > 1)
flag = 1;
}
if(flag == 0) //present string is terminal condition
return 0;
Now the final part is to avoid repeated calculation of overlapping subproblem. (memoization or dynamic programming). We are using memoization here. Let’s store the result in an array say grundy[100000] initialized to 1.
in solve, we need to add grundy array in three places.
first, if the present mask is already solved, grundy[mask] will not be 1.
So in the beginning of the function solve(), add
return grundy[mask];
second place is when the present string itself is a terminal condition. There we are returning 0, at that point set the grundy array as well.
{
grundy[mask] = 0;
return 0;
}
third position is at the end (same reason as second one)
grundy[mask] = min
return min
Solution : Here