Minimizing the operations to be done on letters - ZIO $2014$, P$1$

Question

Hello everybody! The above problem is a combinatorics problem I could not solve. :( This is ZIO $2014$, P$1$.

Here is my approach (feel free to point out any mistakes in it, that's why I am asking this question for): The example given provides a really neat walk-through of how to solve the problem. Also, noticing the fact that the words in the sets have a lot in common motivates us to use the approach. I first began trying to find out elements that share a lot in common and then group them into different sets and then try to find the elements in the sets with common parts. Rearrange accordingly and what we have got there is how to solve the problem. I made this: {there, theirs, therefore, three, threshold, thorium, tree} ; {hence, her} ; {shore, rest} Now for the master-plan, I tried to put the "th" so that it is always there and change the rest, then we can remove the "h" and write "tree" and then the rest similarly. But apparently, this doesn't seem to be the optimal solution.

How do we solve this problem?

The answers are - $88, 120, 115$.

Any help would be appreciated. Thanks!

Answer 1

Here's an optimal strategy, with proof that there isn't a better strategy:

Let $w$ be your word set.

• Pick a word $x$ of maximum length in $S$, call the length $n$.
• Partition $S$ into subsets $S_0, \ldots, S_n$ such that for all $i$ and for all $y \in S_i$ the longest common prefix of $x$ and $y$ has length $i$.
• Sort each subset $S_i$ lexicographically into a list $L_i$.
• Concatenate the lists $L_0 \cdots L_n$ into a list $L$ in this order.
• Print the words according to their order in $L$ using the least necessary operations.

Proof that this is optimal:

Consider the set $T := \{w' : w' \text{ is a nonempty prefix of some }w \in S\}$.

For each $w' \in T$, at least one "add" operation needs to be performed to make the prefix show up on the rack, namely the operation that adds the prefix's last character. These operations must all be distinct.

For each $w' \in T$ that is not a prefix of the last printed word, a "remove" operation needs to be performed to make the prefix stop being on the rack, namely the operation that removes the prefix's last character. Again, these operations must all be distinct.

For each word, at least one "print" operation needs to be performed.

The total amount of operations is therefore bounded from below by $|T| + (|T|-n) + |S|$.

It is easy to verify that the aforementioned algorithm does indeed complete each prefix only once, and dismantle each prefix only once (except the prefixes of $x$, which are permanent), and print each word only once. Therefore the algorithm is optimal.

Example: The word set $S = \{their, her, tree, three, there\}$ would be sorted as follows (given $x = their$): $$L = (her, tree, three, there, their)$$

There are 16 distinct prefixes in these words, so the number of required operations is $16 + (16 - 5) + 5 = 32$.

Answer 2

I think your approach is sound, the only change you need to make is the order in which you tackled the words. The key is in the fact that the last word can remain on the rack, so you want to end with the word that would require the removal of the most letters to make another word. In this case, either 'threshold' or 'thorium" should be the last word, either would require removing at least five letters to make any other word.

I got 88 with the following order, but I'm certain it's not unique:

rest - 9 operations

shore - 11 operations

her - 5 operations

hence - 9 operations

tree - 8 operations

thorium - 12 operations

theirs - 8 operations

there - 3 operations

therefore - 12 operations

three - 5 operations

threshold - 6 operations

Answer 3

You can solve this as an asymmetric traveling salesman problem on a directed graph with one node per word and a dummy depot node. The arc cost from node $i$ to node $j$ is the number of operations needed to print word $j$ immediately after word $i$. The cost from each node to the depot is 0.