Number Theory Problem: Zonal Informatics Olympiad Help?!

Question

In Gutenberg’s printing press, each line of text is assembled by placing individual metal letters in a rack, applying ink to the letters and then pressing them onto paper. Gutenberg needs to print N words using his printing press, one word at a time. The printing press allows the following operations:

• Add a letter to the end of the word currently in the rack.

• Remove the last letter from the word currently in the rack.

• Print the word currently in the rack.

Initially, the rack is empty; it contains no metal letters. At the end of printing, Gutenberg is allowed to leave letters in the rack. Also, he is allowed to print the words in any order that he likes. As each operation requires time, he wants to minimize the total number of operations.

For instance, if Gutenberg is supposed to print out three words, {print, the, poem},

he could do it using 20 operations:

add t, add h, add e, print, remove last letter (three times), add p, add o, add e, add m, print, remove last letter (three times), add r, add i, add n, add t, print.

In each of the following cases, determine the minimum number of operations required to print out all the words in the set, in any order, one word at a time.

(a) { there, theirs, her, shore, three, tree, rest, hence, thorium, therefore, threshold }

Please help on the logic of this question.I'm able to make a python code out of it but no formal math logic dawned to me!

Answer 1

Hint: consider a directed graph with vertices corresponding to the words to print and a "start" and "stop" vertex, and edge weights corresponding to the number of steps to get from one vertex to the other. You want to visit all vertices, starting at "start" and ending at "stop", with least total weight. This is essentially a Travelling Salesman problem.

Answer 2

First, determine the edit distances between any two words. Here, the edit distance between two words $\alpha$, $\beta$ with common prefix $ \gamma$ (i.e., $\alpha=\gamma\alpha'$ and $\beta=\gamma\beta'$ where one of $\alpha',\beta'$ is empty or theit first letters differ) equals $d(\alpha,\beta)=|\alpha|+|\beta|-2|\gamma|$.

Then, your task is to find a path $v_1v_2\ldots v_n$ through all vertices of the graph with the given words as vertices, an edge between any two words $\alpha,\beta$ with an associated edge cost $d(\alpha,\beta)$, that minimizes the total cost $|v_1|+\sum_{i=2}^n d(v_{i-1},v_i)$.