289 - A Very Nasty Text Formatter

[Adrian Kuegel]

Can someone explain me this problem?

You should do as few hyphenations as possible. However, if it is impossible to justify a line of the text, output it left-justified.

Does it mean, that I should minimize the number of lines that can't be printed with length n, and then minimize the number of hyphenations?
If yes, why the output for last sample test case is not:

Code: Select all

This
is a-
n ex-
ample
of  a
para-
graph
whic-
h  is
pret-
typr-
inte-
d  on
a  r-
ow w-
ith a
leng-
th of
five.

The only way how I can reproduce the sample output is by using greedy, but I got WA when I submitted a program with it. Did someone solve this problem with DP, or is greedy the algorithm that is wanted here?

[Adrian Kuegel]

Well, it seems greedy is the wanted solution, at least I got Accepted now.
Here is a test case where my first greedy program failed, perhaps it will help someone else, too:
4 Te s t.

Output is:
Te s
t.

[..]

Thanks for your post.
Once you tell the word "greedy", I suddednly understand what it is asking.
Before that, I have no way to solve it as I even don't know what it requires....

[little joey]

Yes, thanks.
The sentence "You should do as few hyphenations as possible." is wrong, because the only way to achieve that is DP. But than there would be a better solution for the second example:

Code: Select all

This    is   an<CR> 
example      of<CR>
a     paragraph<CR>
which        is<CR>
prettyprinted<CR>
on a row with a<CR>
length       of<CR>
fifteen.<CR>

which has zero hyphens.
I guess the sentence should read "You should only hyphenate when you are forced to", or something like that, altough it doesn't clear matters that much.
Greed is indeed the method, and the problem can be solved by using a buffer of only n+1 characters.
Not so much a 'nasty' text formatter, but rather a 'nasty' problem description.

[Adrian Kuegel]

I just looked at the ps file. It probably shows the original problem description, and there is only one sample test case, and this test case is also possible to reach with DP (minimize number of hyphenations).
I fear that the one who generated the judge input/output made a mistake.