← All solutions

Shortest judge solution: 872 bytes. Shortest team solution (during contest): 869 bytes.

This was one of the easiest problems in the set. The most straightforward approach is to try all line lengths from the shortest possible and upwards, until there is only one line. To try a given line length, we essentially just simulate – place word by word, and keep track of where in the previous line there was a river and how long it was.

A priori, the running time of this sounds dangerous – there are potentially Θ(nL) line lengths to try (where L = 80 is the max word length) and trying a line length naively takes Θ(nL) time for a total of Θ(n²L²) time which sounds pretty dangerous for n = 2500, L = 80. As far as we know it was not possible to get this to pass, but there are several easy optimizations that can be made, and doing any one of them was sufficient to pass:

1. Instead of going all the way up until we just have one line, we can stop when the longest river found is at least as long as the current number of lines.
2. Instead of checking a line length in Ω(nL) time we can do it in O(n) time.
3. Instead of checking every possible line length, we can check “what’s the next line length that will cause the words to be wrapped differently?” and jump directly to that one.

Optimizations 1 and 3 are very hard to analyze exactly how well they perform, and in general it is very hard to craft test data for this problem. To do well against optimization 1, it is useful to have cases with 2500 words where the longest river is as short as possible. The best such case we have (which was found only during the night before the contest!) has a longest river of 3 (but its average word length is not very high, which would be needed to really make optimization 1 work poorly). However, we don’t even know whether it is possible to make such a case with maximum river length 1 or not (we suspect that this is impossible with word lengths bounded by 80, and if anyone finds a proof we would be very interested in seeing it)!