WGME - Editorial

editorial
, ,
1

WGME - Editorial

Problem Link:

Practice

Contest

Author, Tester and Editorialist:-
dragonemperor

Difficulty:

Medium

Pre-Requisites:

bit-masking, recursive memoization, Grundy numbers

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.

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 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

Let’s add the code.

For first condition:

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

if(grundy[mask]!=-1) 
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) 
{

     grundy[mask] = 0;

     return 0;

}

third position is at the end (same reason as second one)

grundy[mask] = min

return min

Solution : Here