709 - Formatting Text

[j0ker]

Is there a faster way to solve this problem? My algorithm was taken from a book and it takes O(n^3) to run. I got accepted in 3.470secs but I

[kostik]

Which algorithm for this problem? pleaze HELP !

[Ryan Pai]

I think this problem is fairly straight forward. A hint would be, for each word, see how good you can do if the message started with just that word.

Also remember to satisfy the condition:

If there are several ways to format a paragraph with the same badness, use the following algorithm to choose which one to output: Let A and B be two solutions. Find the first gap which has not the same length in A and B. Do not output the solution in which this gap is bigger.

[fushar]

Got WA....
Do anyone have tricky I/O for this problem?

[Landertxu]

I don't understand wich should be the output for:

5
La la la

It could be:

La la
la

or:

La
la la

I don't undestand if the newline is considered a "gap" or not, and if it's, if is taken as a 1-gap or as a oo-gap. Could you help me?

Also, some tricky output wouldn't hurt

[fushar]

My AC code produces:

Code: Select all

La la
la