Optimal Line Arrangement

Moderate

0/80

0 upvote

Problem statement

You are tasked with formatting a document composed of N words. You are given the length of each word. These words must be arranged into lines, preserving their original relative order.

The formatting rules are as follows:

Each line can have a maximum of K characters.

Words on the same line are separated by a single space.

A line is considered "correct" if the number of empty spaces at the end of the line is less than or equal to a given threshold, M. Otherwise, the line is "incorrect".

Your goal is to arrange the words into lines to achieve the maximum possible score, where the score is defined as (number of correct lines) - (number of incorrect lines).

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains three space-separated integers: N (number of words), K (max line length), and M (correctness threshold).
The second line contains N space-separated integers, representing the lengths of the words in order.

Output Format:

The output should be a single integer representing the maximum possible score.

Note:

The length of a line containing words from index i to j is calculated as (sum of lengths of words from i to j) + (j - i). The (j - i) term accounts for the single spaces between the j - i + 1 words.
Remaining spaces on a line = K - (total length of that line).
A line is correct if remaining spaces <= M.
A line is incorrect if remaining spaces > M.
A word's length will never be greater than K.

Sample Input 1:

3 10 1
6 2 5

Sample Output 1:

Explanation for Sample 1:

There are two ways to arrange the words:
Arrangement 1:
  Line 1: [6, 2]. Length = 6 + 2 + 1 = 9. Remaining spaces = 10 - 9 = 1. This is a correct line (since 1 <= M=1).
  Line 2: [5]. Length = 5. Remaining spaces = 10 - 5 = 5. This is an incorrect line (since 5 > M=1).
  Score = 1 (correct) - 1 (incorrect) = 0.
Arrangement 2:
  Line 1: [6]. Length = 6. Remaining spaces = 10 - 6 = 4. This is an incorrect line.
  Line 2: [2, 5]. Length = 2 + 5 + 1 = 8. Remaining spaces = 10 - 8 = 2. This is an incorrect line.
  Score = 0 (correct) - 2 (incorrect) = -2.
The maximum possible score is 0.

Expected Time Complexity:

The expected time complexity is O(N^2), where N is the number of words.

Constraints:

1 <= N <= 2000
1 <= word_length[i] <= K <= 1000
0 <= M < K
Time limit: 1sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Optimal Line Arrangement

Console