PROBLEM LINKS
DIFFICULTY
CHALLENGE
PREREQUISITES
Dynamic Programming, Greedy, Maximum Bipartite Matching
PROBLEM
You are playing a simplified version of WordNinja (note! CodeChef is not affiliated with iTunes/Apple in any ways). In this game, you have a slot that can be filled by 7 tiles. You are also given M blocks, each containing at most 10 tiles. Each tile can be a letter tile, a blank tile, or a bonus tile. You have M moves. On the i-th move, you may take a single tile from the i-th block, and then optionally throw one or more tiles from the slot, and then optionally play a word that can be created by the tiles in your slot. You will receive points for each bonus tiles and each played word (and other factors; see problem statement for details).
Your task is to design a solution that will obtain as much score as possible in this game.
QUICK EXPLANATION
We will discuss many possible solutions with different total scores.
EXPLANATION
Solution 1 (1282.96 points)
This solution uses the hint that we can output “Take A” M times and then “Play AA” as AA is a correct word in the dictionary. However, since the judge will ignore incomplete and invalid words, we can always play AA on each move. After playing a word AA, one letter A tile will be left in the array. Therefore, if there are N blocks containing at least one letter A, you will receive (N-1) × (score for word AA).
Solution 2 (1293.6 points)
This solution is similar to Solution 1 except that it takes Z and plays ZZZ (another correct word) instead of AA, because the letter Z is more valuable. However, letter Z tiles are very rare according to the test case generation section. Therefore, this solution only adds few additional points from Solution 1.
Solution 3 (2016.92 points)
According to the rule of the game, by playing any 7-letter word will obtain additional 42 points. We can use 7 blank tiles to create any 7-letter word (for example, “problem”). In this solution, we will take a blank tile and plays “problem” on each move. Since we must wait collect 7 tiles before we can play a word, this solution may score lower than the previous solutions. However, taking a blank tiles scores additional 5 points each and there are approximately 180 blocks with blank tiles (5 × 180 = 900), so eventually this solution has a higher score.
Solution 4 (3363.4 points)
So far, we only use the first type of bonus tiles (i.e., blank tiles). Now, we will try to make use of the double/triple letter/word tiles. Recall that in the previous solution we attempt to take a blank tile from each block. We can improve the previous solution considering bonus tiles in this way:
- If the current block contains a blank tile, take it.
- Otherwise, if the current block contains any multiplier tile, take it.
- Otherwise, skip the current block.
Of course, we still play “problem” at the end of each move.
Solution 5 (8702.76 points)
We will combine Solution 2 and Solution 4 to achieve better score. The letter Z is very rare so we can take many multipliers from the blocks. Fortunately, letter Z is also very valuable.
Considering the value of each bonus tile, let’s use the following strategy. For each block,
- If it contains a better word multiplier tile than the current word multiplier, take it.
- Otherwise, if it contains a letter Z tile, take it.
- Otherwise, if it contains a better letter multiplier tile for positions 1, 2, 3 in the slot, take it.
- Otherwise, if it contains a blank tile, take it.
- Otherwise, it it contains a multiplier tile that does not decrease the multiplier for word or positions 1, 2, 3, take it.
- Otherwise, skip it.
We prefer a word multiplier to letter Z because it would decrease the score if we consider the other way around (tested with the official test case). We prefer a blank tiles to a multiplier tile since a blank tile adds 5 points while a multiplier tile only adds 2 points.
In this solution, we will play the word ZZZ only when there are 3 letter Z tile in the slot (not at the end of each move) so that the multipliers will not be reset after each move.
The conditions above can be very tricky to code especially the ones that deal with multiplier tiles. Please refer to the setter’s solution for details.
Solution 6
The previous solutions only consider a single word from the dictionary. If we play different words, we should obtain greater score. Unlike the previous solutions that use greedy, we will use dynamic programming approach this time.
Let dp[i][p] = the best score we can obtain considering only blocks i, i+1, …, M and the slot currently contains a single tile p in position 1. The recurrence is as follows. We try to play a word by taking tiles from blocks i, i+1, …, j-1. Suppose that the word ends with a tile q. Since the last tile (i.e. tile q) will remain in the slot, then we have
dp[i][p] = max{ score(p, q, i, j) + dp[j][q] | i < j ≤ M; q is a blank or letter tile}
where score(p, q, i, j) is the maximum score we can obtain by playing a single word that ends with letter q with tiles from blocks i, i+1, …, j-1 when the slot contains a single letter p.
Although this DP formula is exact, the total number of states is large and the number of transitions for each state is even larger. Therefore, we have to approximate this DP solution as follows.
Reducing the number of states
We can reduce the number of states by considering only j that is close to i; for example, j < i+12. This way the DP formula is not exact anymore, but we will save a lot of time and memory.
Use top-down DP
We also should use top-down DP approach, i.e. recursion with memoization as the number of possible q for each j is quite small. Therefore, we visit only reachable states and save time as well.
Greedy approach in choosing word to be played
The value of score(p, q, i, j) is also hard to compute exactly. We have to approximate it as well. Instead of fixing q and j and then finding the most valuable word, we will fix the word and the value of q and j will be automatically determined. Also, we will play only 7-letter words as they add additional 42 points.
Let’s sort all 7-letter words in non-increasing order of their points, assuming that all multipliers are 1. The point of the last letter of each word should be doubled as it will remain in the slot after the word is played. Then, iterate the words in non-increasing order of their points. For each word, we try to find a way to play it with the highest possible score using as small number of blocks as possible.
First, for each word we check whether we can obtain good word/tile multipliers near block i. If we can, it’s always better to use multipliers since they are quite rare and will increase the points a lot.
Then, after we fix the multipliers to be used, we have to determine whether the word can be composed from the letters of the remaining blocks. This becomes a bipartite matching problem: there is an edge from a letter in the word to a block in the remaining blocks if the block contains the letter. We can check it with a fast algorithm such as Hungarian algorithm. We also want to have minimum j such that the word can be played. So, we will build the matching on the fly: each time we increment j, we add the block and reconstruct the matching. This way, we can find the minimum number of blocks required to build a word very fast.
Note that a block that contains a blank tile should be connected to all letter tiles of the word. However, since a blank tile decreases the score, it is better to try 2 possibilites: either find a matching with blank tiles or without them. Actually we can use weighted matching by assigning the edge weight to the score of the letter multiplied by the corresponding letter and word multiplier. However, this will slow down the solution.
We have find a way to play a word. Should we check all possible 7-letter words in each DP state? This will be time-consuming. So we have to use some heuristics to skip the words that are probably not too good to be played. For example, we can skip a word that requires too many consecutive blocks to take. We can check this by counting how many consecutive blocks starting with i we should take in order to have the required number of letter, for each letter of the word. To do this fast, we can precompute this in advance; for example, we can build an array blocks[a][b][c] = the number of consecutive blocks starting with block a that is required to have b letter c’s. Since the most valuable words have rare letters Z, Q, J, X, this check allows to skip a lot of words.
Since the letters {Z, Q, J, X} are rare, we could even filter the dictionary beforehand. For each subset of {Z, Q, J, X}, we have a list of words without the letters in the subset. Then, for each i in the DP state we can analyze which of these 4 letters it is better skip the words containing them and use words only from the corresponding list.
The above solution is very complicated and tricky to code. In order to verify the correctness of the solution effectively, a contestant should code an independent function that checks whether the output is valid. See ACRush’s _evaluate function for reference.
SETTER’S SOLUTION
Can be found here
TESTER’S SOLUTION
Can be found here.