 # WGME - Editorial

## WGME - Editorial

Practice

Contest

Author, Tester and Editorialist:-
dragonemperor

Medium

### Explanation:

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.

{

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

{

int temp = solve(mask);    //find the grundy value of the present substring

mylist.push_back(temp);	//adding the grundy values of the next moves
``````

}

}

//find the minimum non-negative 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?

1. empty string that is when mask is 0

2. if the present string doesn’t have any duplicates

For first condition:

``````return 0;
``````

for second condition:

int hash;

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 initialized to -1.
in solve, we need to add grundy array in three places.

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.

if(flag == 0)
``````{