Since there will be exactly ~N~ instructions to print a word, we may ignore these for the discussion of this problem. We define a word ~W~ to appear on the type printer if at some moment the printer contains exactly the word ~W~. Our goal now is to make each of the words appear on the type printer.

Given a set of words, we can store them in a simple tree structure, known as a trie. A trie is a rooted tree where each edge is assigned a letter. Reading down from the root, these letters form the words stored in the trie.

Below you can find an example of a trie for the set of words ~\{\text{cat}, \text{car}, \text{do}, \text{dog}, \text{eel}\}~. In the picture, the root node is the one at the top.

An empty type printer corresponds to the root node of the trie. Each command corresponds to moving one step in the trie: Adding a letter at the end corresponds to moving one level down in the trie, and deleting a letter corresponds to returning one level up. Try to trace this sequence of commands in the trie pictured above: c, a, t, -, r. You should end in the node that corresponds to the word car.

Now consider a slightly different version of our task. Suppose that we want to find the minimal number of operations that prints all words, and after printing the last word returns the type printer to the empty state.

In our graphical representation this task can be rephrased as follows: find the shortest walk that starts in the root node, visits each node of our trie at least once, and ends in the root node again. Clearly, for each edge in our trie, at some point we have to walk down that edge to reach the nodes in the subtree below. And as the trie is a tree, we have no other way but to use the same edge later to get back from that subtree.

This means that each edge of our trie will be used at least twice. Therefore a solution that uses each edge exactly twice must be optimal. We obtain such a solution simply by running a depth-first search from the root node of the trie.

Now consider the original problem, where you can leave some letters in the printer at the end. The only thing that will change is that now we can save a few 'minus' commands – we can stop immediately after the last word appears, we do not have to delete it. And the longer the last word, the more 'minus' commands we save, and thus the shorter our solution will be. Therefore our goal is to maximize the length of the last word that appears on the printer.

It is always possible to end with the longest word. One way how to construct such a sequence of commands is to modify the depth-first search as follows: First, pick the longest word you want to print last. Mark the nodes of the trie that we visit when reading this word. Now, run the depth-first search with the additional constraint: 'if I am in a marked node that is not a leaf, first process all children that are not marked, and only at the end process the marked child node'. This will force the depth-first search to enter the marked branch at the end, and finish in the leaf node we wanted it to.

Note that it is possible to solve this task without actually implementing the trie. One possible solution that is really simple to implement:

Suppose that we pick one longest word ~W~ and then sort all the words in the input, using the length of the common prefix with ~W~ as the primary key, and the actual word as the secondary key. In other words, we sort words according to the number of first letters they share with ~W~, breaking ties alphabetically. It can easily be proved that we will get one possible optimal order in which to print the words.

To see why this is the case, note that we are actually doing exactly the same thing as in the previous approach: first we print all the words that have the first letter different from the first letter of ~W~, then all the words that share exactly the first letter with ~W~, and so on. The alphabetical order within each group is there to ensure that words with a common prefix are always processed at the same time, as in the depth-first search solution above.

The solution with a trie is linear in the input size, the one with sorting has an additional logarithmic factor if you use a library function to do the sorting. Both approaches were expected to score 100 points.