WPLAY - Editorial

Problem Link:

Practice

Contest

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

4 Likes

Difficulty EASY? are u sure…? it had submissions comparable to TRIQUERY…

3 Likes

Time limit was strict!

My top down approach timed out!

And Bottom Up approach was well within limits

Don’t go by number of submissions. ROC is also classified as “Easy”.
It turns out that this contest had more people attempting the medium problems and the easy ones got passed off as harder than they were.

1 Like

So why was this happening ? I think to come up with a easy solution for them was the difficult part…

Instead of using Trie, which could be a bit advanced for newbies, one could simply store all words in the sorted array of strings and check whether subset of the grid is a word by binary search.

Of course, we should memoize the information about subsets - for each subset of the grid we check whether it is a word only once and save this information at some array.

Also it should be mentioned how to iterate over all non-empty subsets of the given set when they represented using bitmasks:

submask = mask
while submask > 0
    // do the job with the submask
    submask = (submask - 1) AND mask

where AND is a bitwise and operation. It is very remarkable that simple operation

submask = (submask - 1) AND mask

iterate over all submasks without repetition.

The overall complexity of such solution is

O(D * N * log N + D * log D * N + T * (2^N * N * log D + 3^N))

where N = R * C. Here

  1. D * N * log N corresponds to input the dictionary and sorting letters of each word.

  2. D * log D * N corresponds to the sorting of dictionary.

  3. 2^N * N * log D corresponds to checking for each subset of the grid whether it is a correct word.

  4. Finally 3^N corresponds to the finding losing/winning positions.

You can check my solution as a clear and concise implementation of this approach.

10 Likes

I used both this hack and TRIE for a good timing :smiley:

Thanks for this analysis. The Trie only saves you the logD term.

Yes. But the main bottleneck is 3^N part so trie should not save much time.

My solution to the problem is the same as according to the editorial, but I was getting TLE constantly. Could someone take a look at my solution? http://www.codechef.com/viewsolution/1820806

1 Like

Why have the tester and setter used XOR with subsets? Can someone please explain theory behind the same

Can you please show how
submask = mask
while submask > 0
// do the job with the submask
submask = (submask - 1) AND mask
iterates over all submasks

Nothing is special about the XORs used there. They are just shifting bits having 1 to 0. So if you had 110110 and you wanted to remove 010010, doing an XOR is as good as doing a SUBTRACT [this is once you’ve figured that 010010 is a “sub-bitmask” of 110110].

Can anyone please explain me the reason for 3^rc component in the time complexity? How can we calculate the order for the process of characterizing states as winning or losing?

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 SW is a losing state. If every word W that can be formed from characters in S leads to a winning state SW, then S is a losing state.

Can somebody please elaborate this?