Topics

The problem asks us to minimize the width of an advertisement text, given a maximum line count . We can wrap lines at spaces or hyphens within words.

Idea

The core idea is to use binary search on the possible ad widths (answer space). This works because if for width , we can’t format the ad in atmost lines, then anything smaller than will not work as well (so, try increasing width). Similarly, if works, then anything greater than will also work, but since we want the min width, try decreasing width. Thus, we can observe monotonicity in our search space.

We can check if a given width is feasible, using at most lines. Note that the search space is:

  • lo: maximum token length (a single word segment between hyphens or spaces cannot be broken further)
  • hi: total length of the input string (the worst case width if no wrapping occurs)

Checking Feasibility

For a given width mid, we simulate the line wrapping process greedily. We iterate through the text “tokens” (segments of words separated by spaces or hyphens). We maintain a tokens_on_line counter, representing the current line’s width. For each token, we check:

  1. If adding the token to the current line (tokens_on_line + token) does not exceed mid, we add it to the current line
  2. Otherwise, we must start a new line. We increment the lines count and set tokens_on_line to the current token’s length (as this token starts a new line)

After processing all tokens, we check if the total lines count is less than or equal to . If it is, the width mid is feasible.

Time Complexity: The check function iterates through the tokens, taking linear time proportional to the number of tokens, which is bounded by the length of the input string . Binary search performs iterations. Thus, the total time complexity is .

Space Complexity: We store the tokens in a vector. The number of tokens is also bounded by . Therefore, the space complexity is .

Code

bool check(vector<int> &tokens, int mid, int k) { int tokens_on_line = 0; int lines = 1; for (int &token : tokens) { if (tokens_on_line + token <= mid) { tokens_on_line += token; } else { tokens_on_line = token; lines++; } } return lines <= k; } void solve() { int k; cin >> k; string s, _; getline(cin, _); getline(cin, s); vector<int> tokens; int prev = 0; int curr = 1; for (auto &c : s) { if (c == '-' or c == ' ') { tokens.pb(curr - prev); prev = curr; } curr++; } // don't forget the last token tokens.pb(curr - prev - 1); int lo = *max_element(all(tokens)); int hi = s.size(); int ans = hi; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (check(tokens, mid, k)) { ans = mid; hi = mid - 1; } else lo = mid + 1; } cout << ans << endl; }