Question

This text is justified, meaning that the words are arranged so that both the left and right margins form straight lines. This is accomplished by varying the amount of space between words and characters in the text. Unfortunately, there are limits to this technique since uneven spacing eventually becomes noticeable to the human reader. Your job in this problem is going to be determining where to put line breaks in a sequence of words to make the most visually-pleasing justified paragraph.

You are given an array of word lengths (the lengths include space needed for whitespace and punctua- tion). We are assuming the every character occupies the same amount of space and that lines have room for 80 characters. You need to determine the number of words to put onto each line. Your selection must limit the number of characters per line to 80 or less. For example, consider the sequence 20, 20, 20, 10, 10, 10, 20, 15, 40. One possible solution would be 5, 3, 1 (i.e. 5 words on the first line, 3 on the second, and 1 on the third), which puts 80 characters on line 1, 45 on line 2, and 40 on line 3. A second solution would be 4, 4, 1, which puts 70 characters on line 1, 55 on line 2, and 40 on line 3.

The quality of your line breaks will be judged based on all lines except the last, which is ignored since the last line of a paragraph can be of any length. Every other line contributes the square of the number of unused characters on that line. You are asked to minimize the sum of these squares. For example, the first solution above has cost 02 + 252 = 1, 225 while the second has cost 102 + 252 = 725.

Give a fast dynamic programming algorithm to find the optimal set of line breaks. Be sure to explain how to get the actual locations of the line breaks (not just the optimal cost). Argue for your algorithm’s correctness and analyze its running time.

Answer 1

#include <bits/stdc++.h>
using namespace std;
#define INF INT_MAX

int printSolution (vector<int>print,int n)
{
int k;
if (print[n] == 1)
k = 1;
else
k = printSolution (print, print[n]-1) + 1;
cout<<"Line number "<<k<<": From word no. "<<print[n]<<" to "<<n<<endl;
return k;
}
void solve(vector<int>line, int m)
{
int n=line.size();
vector<vector<int> >extras(n+1,vector<int>(n+1));
vector<vector<int> >cost(n+1,vector<int>(n+1));
vector<int>cumulative_cost(n+1);
vector<int>print(n+1);
int i, j;
for (i = 1; i <= n; i++)
{
extras[i][i] = m - line[i-1]; //calculate extra words if i to j words place in a single line
for (j = i+1; j <= n; j++)
extras[i][j] = extras[i][j-1] - line[j-1] - 1;
}
for (i = 1; i <= n; i++)
{
for (j = i; j <= n; j++) //calculate extra words if i to j words place in a single line
{
if (extras[i][j] < 0)
cost[i][j] = INF;
else if (j == n && extras[i][j] >= 0)
cost[i][j] = 0;
else
cost[i][j] = extras[i][j]*extras[i][j];
}
}
cumulative_cost[0] = 0;
for (j = 1; j <= n; j++)
{
cumulative_cost[j] = INF;
for (i = 1; i <= j; i++) //calculate minimum cumulative cost from 1 to j
{
if (cumulative_cost[i-1] != INF && cost[i][j] != INF &&
(cumulative_cost[i-1] + cost[i][j] < cumulative_cost[j]))
{
cumulative_cost[j] = cumulative_cost[i-1] + cost[i][j];
print[j] = i;
}
}
}
printSolution(print,n);
}
int main()
{
int i,n,m=6;
cin>>n;
vector<int>a(n);
for(i=0;i<n;i++)
cin>>a[i];
solve(a,m);
return 0;
}
Time Complexity:O(n^2)

Space Complexity:O(n^2)

where n is length of array

Quick Explaination:

• First we compute costs of all possible lines .
• If a sequence of words from i to j cannot fit in a single line, then lc[i][j] is considered infinite
• cumulative cost upto j is zero if j is zero
• otherwise it is minimum of (for all i (1<=i<=j) min(cumulative cost[i]+cost[i+1][j]
• we can keep a parallel p array that points to where each c value came from.