Problem Link:
Difficulty:
Easy
Pre-requisites:
2-player games
Problem:
Alice and Bob play a game. You have a dictionary of D words, and you have a set of T r x c boards having characters in each cell. Each player in their turn takes a set of characters from the remaining on the board and makes a word from the dictionary. The player who cannot make a word loses. For each of the T boards, determine if Alice wins when she plays first.
Explanation:
There are a few observations to be made.
Observation 1: Order of letters of words in the dictionary do not matter. That means, dictionary words that are anagrams of each other as good as equivalent. For example, if your dictionary had the words TIME, ITEM, EMIT, MITE, it would have been equivalent had the dictionary just had the word ITEM. This is because we are picking characters from anywhere on the board and making words irrespective of the ordering.
Thus, instead of storing the words of the dictionary, we instead just store certain representative samples (so that anagrams map to the same representative). A good choice would be the word formed by sorting the characters. So in the example, we would have just EIMT as our “word”.
Now, given a set of characters with which we wish to form a dictionary word, in order to check if there is some word that can be formed, we just need to check if the sorted-characters-word is in the dictionary.
Observation 2: Order of characters on the board also doesn’t matter, since we’re ultimately making words by picking some set of characters. Similarly, we can store the board as a bitmask. If we were to initially sort the characters of the board, then a particular bitmask would map to the representative of that word in fact.
Next, we need an efficient way to check if a given string is in the dictionary or not. This can be done by storing the dictionary in the form of a Trie. Using a Trie, checking if a string S is a word takes only O(|S|) time.
Now, you have a game, where a state consists of the set of characters left on the board. We wish to determine if a state S is a winning state or not. S is a winning state if there is a word formed by the characters W, such that the state S*W* is a losing state. If every word W that can be formed from characters in S leads to a winning state S*W*, then S is a losing state.
We can now traverse over all the reachable states from the complete board, and check whether each a winning or losing state. This can be memoized.
Algorithm:
winning (state S):
for all subsets of state S: W
if(W is in dictionary and S\W is losing)
S is winning
S is losing.
Finally, we need to check if the state of the whole board is winning or not.
Thus overall complexity: O(Drc) for constructing the Trie + O(3^(r*c) * small qty) per testcase.
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here
