Gutenberg's algorithmic printing press - 1

Computer Science Level 4

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.

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

 [This is question from zonal Informatics Olympiad , India ]

The answer is 88.

1 solution

Ryandk St
Jun 25, 2014

classical bit mask dymanic programming, use $dp[1<<w][w]$ represt for the state $(done,lw)$ , $1's$ in $done's$ binary representation shows words has beed printed, and the last printed word was $lw$ ,

we enum the next word $nw$ which hasn't beed printed, and built a array like $dis[i][j]$ , represented for the number of operations to print word $j$ after we have wrote word (\i ), which is the $length(i)+length(j)-2*prefix$ ,

the transform equation looks like: $dp[set(done,new)]=min(dp[set(done,new)],dp[set][last]+dis[last][new])$ while she $set$ function means set the $new$ 's bit to be $1$ and the final answer is min of ${dp[all\_the\_word\_printed\_state][last]}$

but could you please explain it more simply . I am not able to understand this as i am a beginner

Dhruva Kothari - 6 years, 11 months ago

Err...let's see an example similiar to the problem provided, there're 4 words: print, the, poem, aaaaa , we label them as 0, 1, 2, 3 , and an obivous $4!$ brute search can solve the problem,but if the number increases, the brute search's time cost tremendously increased.

Let's read the problem again, luckily we found that among all the $n!$ possibilities, a lot of them were calculated repeatedly, for example, from the problem statement we can infer that the order the,poem,print,aaaaa must be no worser than poem, the, print, aaaaa and any other print order ends in word aaaaa , why?Because the order the,poem,print is the best among all permutation of there $3$ words.

Now use the above idea to optimize our program:among all the combinations of the printed word permutation combines with the last printed word, we just need to record the best one, because the other combinations wiill never gain less operations then the best one.

Still remember we labeled the words?Yeah here they came, we use a positive integer to represent the printed state, for example, $0$ means none has beed print, $1$ means the word with label 0 printed, $2$ for word labeled 2 printed, $6$ means the words with label $1,2$ have beed printed.Do you find the pattern?If the word with label $i$ has beed printed, then we set the $i's$ bit in state to be $1$ . Remember we need to record the state of the last printed word, otherwise we can't get the new state, this can be solved by simply add another variable.

Finally, the code includes 3 nested for loops, we enumerate the printed
words, then last printed word, the a new word hasn't beed printed, and it works……

ryandk st - 6 years, 11 months ago

thank you so much

Dhruva Kothari - 6 years, 11 months ago

Gutenberg's algorithmic printing press - 1

The answer is 88.

1 solution

0 pending reports