JANUARY 26, 2012
Programming contests are interesting to say the least. The sheer feeling of knowing you have a limited amount of time to come up with a solution that will not only be correct but fast enough to handle large and purposefully tricky inputs is a challenge few programmers can resist.
One thing is vital in programming challenges though, figuring out what you actually need to solve and what is just noise for the particular problem at hand. As an example of this I will use the “Billboards” problem that was on the qualification round for Facebook’s 2012 edition of its Hacker Cup programming contest and compare the solution I made to the much better solution Peter Yongwen Liang, an acquaintance of mine, made.
While both solutions produce the correct answers and both work fine for the trivial inputs given in the problem description, for the actual test input (provided below), Peter’s solution works nearly instantly while mine took about 7 minutes to run (4 test cases in particular: 9, 11, 18 & 20 took very long, the rest were “fast”) which was more than the 6 minute time limit Facebook had for this problem.
This post will analyze the different approaches we took and exemplify what is “wrong” with my solution. First though, here’s a copy of the problem description:
Billboards
We are starting preparations for Hacker Cup 2013 really early. Our first step is to prepare billboards to advertise the contest. We have text for hundreds of billboards, but we need your help to design them.
The billboards are of different sizes, but are all rectangular. The billboard widths and heights are all integers. We will supply you with the size in inches and the text we want printed. We want you to tell us how large we can print the text, such that it fits on the billboard without splitting any words across lines. Since this is to attract hackers like yourself, we will use a monospace font, meaning that all characters are of the same width (e.g.. 'l' and 'm' take up the same horizontal space, as do space characters). The characters in our font are of equal width and height, and there will be no additional spacing between adjacent characters or adjacent rows. If you print a word on one line and print the next word on the next line, you do not need to print a space between them.
Let's say we want to print the text "Facebook Hacker Cup 2013" on a 350x100" billboard. If we use a font size of 33" per character, then we can print "Facebook" on the first line, "Hacker Cup" on the second and "2013" on the third. The widest of the three lines is "Hacker Cup", which is 330" wide. There are three lines, so the total height is 99". We cannot go any larger.
Input
The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case in the form "W H S". W and H are the width and height in inches of the available space. S is the text to be written.
Output
Output T lines, one for each test case. For each case, output "Case #t: s", where t is the test case number (starting from 1) and s is the maximum font size, in inches per character, we can use. The size must be an integral number of inches. If the text does not fit when printed at a size of 1", then output 0.
Constraints
1 <= T <= 20 1 <= W, H <= 1000 The text will contain only lower-case letters a-z, upper-case letters A-Z, digits 0-9 and the space character The text will not start or end with the space character, and will never contain two adjacent space characters The text in each case contains at most 1000 characters Example input
5
20 6 hacker cup
100 20 hacker cup 2013
10 20 MUST BE ABLE TO HACK
55 25 Can you hack
100 20 Hack your way to the cup
Example output
Case #1: 3
Case #2: 10
Case #3: 2
Case #4: 8
Case #5: 7
As one can see, the problem consists in maximizing the font size that can be used for a given message on a particular billboard size. Where it gets tricky is that it seems that you need to determine the optimum layout of the text to maximize the possible font size, I did this while Peter solved the problem in a more clever way. While my experience with programming contests hinted at my solution being too complicated, I went ahead and did it anyway without stepping back and re-analyzing the problem, this proved to be a mistake.
The issue here is that determining the optimum layout is NOT a trivial problem and it is the main source of the high runtime complexity in my solution; basically I made a solution for something that did not need to be solved in this particular problem.
My solution took the desired text and calculated the minimum width for the longest line if it is to be fitted into N lines, I basically went through the entire sentence and implemented a decision tree to determine where to cutoff a particular line. Afterwards, I calculated the font size that should be used based on that minimum width for N lines and the billboard dimensions.
While I did add pruning to the algorithm to prevent making unnecessary operations and did optimize it to use an estimated width, this was still a complex algorithm that requires O((2^m)*m) operations in the worst case (where m is the number of words). Although the average case is much better, programming contests usually have inputs that are made to test these worst case scenarios and several of the cases made my pruning operations useless.
Peter, on the other hand, decided to do a binary search on the possible font sizes and see whether a particular size can be fit onto the billboard. To do this he just used up space on the billboard at a given size until he ran out of words or ran out of space. In the first case it means the text did fit and went on to try larger font sizes while the second case means it did not fit and went on to try smaller sizes.
In retrospective, this makes much more sense because the limitations of the problem allow for far fewer font sizes than text distributions and ultimately this takes care of the problem at hand without having to go through the tricky part of arranging the words. His solution is roughly O(n*logm) where n is the number of characters that need to be printed and m is the billboard size on its smallest side.
As one can see, the main lesson to be learned here is that approaching a problem from the correct angle allows you to come up with a solution that avoids having to bother with solving things that are not really relevant to that particular problem. “Billboards” requires you to maximize a font size and my solution did much more than that; while those other thing that were solved can be useful in other situations, it is not really relevant for the purpose of the contest.
This is why in contests and many other programming challenges, one has to take a step back and really figure out what needs to be solved and what doesn’t.
With that in mind, here’s my code and Peter’s code, as well as the input and output.
import java.util.Scanner;
/**
* @author Luis Edgardo Argote Bolio
*
* This code has a worst case performance of O((2^m)*m) where m is the
* number of words, however, the average case is much better
*/
public class Main {
private static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
// Gets the number of cases that we need to do
int cases = Integer.parseInt(in.nextLine());
for (int caseNo = 0; caseNo < cases; caseNo++) {
// This section just parses the input so it can be used later
String line = in.nextLine();
int billboardWidth = Integer.parseInt(line.split(" ")[0]);
int billboardHeight = Integer.parseInt(line.split(" ")[1]);
String text = line.substring(line.indexOf(' ', line.indexOf(' ') + 1) + 1);
// Calls the method that actually obtains the desired result
int bestSize = getBest(text, billboardWidth, billboardHeight);
// Prints out the results in the desired format
System.out.println("Case #" + (caseNo + 1) + ": " + bestSize);
}
}
/**
* This method initiates a call for different text distributions to see
* which one allows for the biggest font size
*
* @param text
* The actual text that must be printed out on the billboard
* @param bbWidth
* The width of the billboard
* @param bbHeight
* The height of the billboard
* @return Returns the largest possible font size given the above parameters
*/
private static int getBest(String text, int bbWidth, int bbHeight) {
// Obtains the best case for when everything is written on a single line
int currentBest = (int) bbWidth / text.length() < bbHeight ? (int) bbWidth
/ text.length() : bbHeight;
String[] words = text.split(" ");
int[] wordLength = new int[words.length];
int longestWord = 0;
// Determines the length of each word that needs to be placed as well as
// the longest one
for (int ii = 0; ii < words.length; ii++) {
wordLength[ii] = words[ii].length();
// Determines the length of the longest word that needs to be
// placed which is used for pruning later on.
if (wordLength[ii] > longestWord) {
longestWord = wordLength[ii];
}
}
int totalLength = text.length();
// Determines the max font size for a given line count >= 2
for (int lines = 2; lines <= words.length; lines++) {
int bestHeight = (int) bbHeight / lines;
// In case there is no possible way that more lines can allow for
// bigger fonts, there is no need to keep looking at more lines
if (currentBest >= bestHeight) {
return currentBest;
}
// Decrease the totalLength count by one as there will be a space
// replaced by a newline
totalLength--;
// Determine the line length cutoff
int lineLengthCutoff = longestWord > (int) Math
.ceil((totalLength + 0.0) / lines) ? longestWord
: (int) Math.ceil((totalLength + 0.0) / lines);
// Determines the max text width size for the line count in
// characters
int nLinesWidth = getBestWidth(wordLength, 0, lines, lineLengthCutoff);
int bestWidth = (int) bbWidth / nLinesWidth;
int bestSize = bestWidth < bestHeight ? bestWidth : bestHeight;
// If using N lines allows for a better result than the current
// best, use that
if (bestSize > currentBest) {
currentBest = bestSize;
}
}
return currentBest;
}
/**
* This method gets the best possible width (in number of characters) required
* to accommodate the words for the initial line value in the optimum arrangement
*
* This method is recursive in nature. This method should be called with a
* value for index that exists in the wordLengths array.
*
* @param wordLengths
* An int array containing the lengths of the words to put on the
* billboard
* @param index
* The index in the array of the next word that needs to be added
* @param lines
* The remaining number of lines that should be accommodated
* @param lineLengthCutoff
* A reference cutoff point for when to go into the next line
* @return The width (in number of characters) required to accommodate the
* words for the initial line value in the optimum arrangement
*/
private static int getBestWidth(int[] wordLengths, int index, int lines,
int lineLengthCutoff) {
// Takes the first word
int maxWidth = wordLengths[index];
index++;
// If there are no more words, return
if (index >= wordLengths.length) {
return maxWidth;
}
// The base case, all the remaining words NEED to be on the final line
if (lines <= 1) {
while (index < wordLengths.length) {
maxWidth += wordLengths[index] + 1;
index++;
}
} else {
// Keeps adding words while adding it does not pass the lineLengthCutoff
while (maxWidth + wordLengths[index] + 1 <= lineLengthCutoff) {
maxWidth += wordLengths[index] + 1; // The +1 is for the space (' ')
index++;
// Returns if it runs out of words
if (index >= wordLengths.length) {
return maxWidth;
}
}
// Recursive call, calculates the best possible scenario for the
// remaining words if we exclude the border word
int maxExcludeLast = getBestWidth(wordLengths, index, lines - 1,
lineLengthCutoff);
// Include the border word for the local calculation
int maxWidth2 = maxWidth + wordLengths[index] + 1;
index++;
// Determines whether this line or some line "below" it is the
// longest one for the case where the border word is excluded
if (maxExcludeLast > maxWidth) {
maxWidth = maxExcludeLast;
}
// If there is still something to add to a new line, do it
if (index < wordLengths.length) {
// Recursive call, calculates the best possible scenario for the
// remaining words if we include the border word
int maxIncludeLast = getBestWidth(wordLengths, index,
lines - 1, lineLengthCutoff);
// Determines whether this line or some line "below" it is the
// longest one for the case where the border word is included
if (maxIncludeLast > maxWidth2) {
maxWidth2 = maxIncludeLast;
}
}
// Determines whether taking the second path (including the border word)
// eventually yields a better result than the first one (excluding it).
if (maxWidth2 < maxWidth) {
maxWidth = maxWidth2;
}
}
return maxWidth;
}
}
import java.util.Scanner;
/**
* @author Peter Yongwen Liang
*
* Commented and modified for better readability by Luis Argote
* This solution is O(n*logn)
*/
public class Main {
private static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
int cases = in.nextInt();
int caseNumber = 1;
in.nextLine(); // Discards the remaining input line
while (cases-- > 0) {
int width = in.nextInt();
int height = in.nextInt();
String[] message = in.nextLine().trim().split(" ");
int minSize = 1;
int maxSize = Math.min(height, width);
int bestSize = -1;
// Does a binary search on the possible font sizes to see which fits
while (minSize <= maxSize) {
// The font size that will be attempted
int currentTargetSize = (minSize + maxSize) / 2;
// See if the given font size fits
if (sizeIsDoable(currentTargetSize, width, height, message)) {
// It fits, save as largest so far and try even larger
minSize = currentTargetSize + 1;
bestSize = currentTargetSize;
} else {
// Doesn't fit, try smaller sizes
maxSize = currentTargetSize - 1;
}
}
System.out.println("Case #" + caseNumber + ": " + bestSize);
caseNumber++;
}
}
/**
* This method determines whether a given font size and message will fit in
* a billboard of a given height and width
*
* @param targetSize
* The font size that is being attempted
* @param width
* The width of the billboard
* @param height
* The height of the billboard
* @param message
* The text that needs to be printed on the billboard
* @return Whether the given font size fits on the billboard or not
*/
private static boolean sizeIsDoable(int targetSize, int width, int height,
String[] message) {
int currentWidth = 0;
int currentHeight = 0;
int currentMessagePosition = 0;
// While it can keep adding lines
while (currentHeight + targetSize <= height) {
// If the entire message has been fitted in, return true
if (currentMessagePosition == message.length) {
return true;
}
int nextWordLength = message[currentMessagePosition].length();
// If the next word will still fit in the current line
while (currentWidth + nextWordLength * targetSize <= width) {
currentWidth += nextWordLength * targetSize;
currentMessagePosition++; // Accounts for the space
// If the entire message has been fitted in, return true
if (currentMessagePosition == message.length) {
return true;
}
nextWordLength = message[currentMessagePosition].length() + 1;
}
currentWidth = 0;
currentHeight += targetSize;
}
// Did not fit, return false
return false;
}
}
For reference, I have included download links to Facebook’s Test Input and the Correct Output.