EPIJ 16.11 Pretty printing problem variant 2

#1

For variant 2 of this problem, to minimize the messiness in O(n) time and O(1) space, is it sufficient to maximize the number of words on each line, and minimize the number of lines?

0 Likes

#2

My guess is similar to yours. Here’s my attempt to prove the correctness, which may be wrong, so take it with a grain of salt.

Let’s say we have n words and two possible ways to break the words into lines where we have m and m-1 lines respectively. Denote the total length of all the words as W and the line length as L. In the case of m lines, the messiness is X=m*L-W-(n-m). Similarly, the messiness for the case of m-1 lines is Y=(m-1)*L-W-(n-m+1). Clearly, X>Y, so we conclude that minimizing the number of lines can lead to the optimal result.

0 Likes