EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
ICPC 2018
ICPC 2018

F. Go with the Flow

In typesetting, a “river” is a string of spaces formed by gaps between words that extends down sev- eral lines of text. For instance, Figure F.1 shows several examples of rivers highlighted in red (text is intentionally blurred to make the rivers more visib...

Updated May 21, 2026
Track ICPC
Year 2018
Statement Text + PDF
TeXC++Statement textStatement PDF
Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF
Time limit 12 seconds

In typesetting, a “river” is a string of spaces formed by gaps between words that extends down sev- eral lines of text. For instance, Figure F.1 shows several examples of rivers highlighted in red (text is intentionally blurred to make the rivers more visible).

Figure F.1: Examples of rivers in typeset text.

Celebrated river authority Flo Ng wants her new book on rivers of the world to include the longest typographic rivers possible. She plans to set the text in a mono-spaced font (all letters and spaces have equal width) in a left-aligned column of some fixed width, with exactly one space separating words on each line (the text is not aligned on the right). For Flo, a “river” is defined as a sequence of spaces lying in consecutive lines in which the position of each space in the sequence (except the first) differs by at most 1 from the position of the space in the line above it. Trailing white space cannot appear in a river. Words must be packed as tightly as possible on lines; no words may be split across lines. The line width used must be at least as long as the longest word in the text. For instance, Figure F.2 shows the same text set with two different line widths.

Line width 14: River of length 4      Line width 15: River of length 5
The Yangtze is|                       The Yangtze is |
the third          |                  the third           |
longest river |                       longest*river |
in*Asia and        |                  in Asia*and the|
the*longest in|                       longest*in the |
the*world to |                        world to*flow |
flow*entirely |                       entirely*in one|
in one country|                       country             |
Figure F.2: Longest rivers (*) for two different line widths.

Given a text, you have been tasked with determining the line width that produces the longest river of spaces for that text.

Input

The first line of input contains an integer n (2 ≤ n ≤ 2 500) specifying the number of words in the text. The following lines of input contain the words of text. Each word consists only of lowercase and uppercase letters, and words on the same line are separated by a single space. No word exceeds 80 characters.

Output

Display the line width for which the input text contains the longest possible river, followed by the length of the longest river. If more than one line width yields this maximum, display the shortest such line width.

Sample Tests

Sample 1
Sample Input 
 21
 The Yangtze is the third longest
 river in Asia and the longest in
 the world to flow
 entirely in one country
Sample Output 
15 5
Sample 2
Sample Input 
 25
 When two or more rivers meet at
 a confluence other than the sea
 the resulting merged river takes
 the name of one of those rivers
Sample Output 
21 6
Editorial

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

  • Write the structural observations that make the problem tractable.

  • State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.

  • If the constraints matter, explain exactly which part of the solution they enable.

Algorithm

  1. Describe the data structures and the state maintained by the algorithm.

  2. Explain the processing order and why it is sufficient.

  3. Mention corner cases explicitly if they affect the implementation.

Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

State the first key claim.

Proof.

Provide a concise proof.

Lemma 2.

State the next claim if needed.

Proof.

Provide a concise proof.

Theorem.

The algorithm outputs the correct answer for every valid input.

Proof.

Combine the lemmas and finish the argument.

Complexity Analysis

State the running time and memory usage in terms of the input size.

Implementation Notes

  • Mention any non-obvious implementation detail that is easy to get wrong.

  • Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.

Implementation

Code

C++ solution used for this page.

C++

Clean code view with a raw-file link when you want the original source.

Raw file 
#include <bits/stdc++.h>
using namespace std;

namespace {

void solve() {
    // Fill in the full solution logic for the problem here.
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
TeX write-upcompetitive_programming/icpc/2018/F-go-with-the-flow/solution.texC++ implementationcompetitive_programming/icpc/2018/F-go-with-the-flow/solution.cppStatement textcompetitive_programming/icpc/2018/F-go-with-the-flow/statement.txtStatement PDFcompetitive_programming/icpc/2018/F-go-with-the-flow/statement.pdfMetadatacompetitive_programming/icpc/2018/F-go-with-the-flow/meta.jsonYear packetcompetitive_programming/icpc/2018/contest_problems.pdf