Facebook Hacker Cup 2012: Billboards Solution | Programming Logic

Facebook Hacker Cup 2012: Billboards Solution | Programming Logic
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.
Let's say we want to print the text "Facebook Hacker Cup 2013″ on a 350×100″ 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

Why the correct approach to a problem is important

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.

eter, 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.

   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++;
        }
    }
    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;
    }

http://notes.tweakblogs.net/blog/7524/facebook-hacker-cup-qualification-round-problem-analysis.html
That leaves the question of how to determine whether a certain text fits on the billboard. A nice trick is to not scale up the text, but to scale down the billboard and pretend our font always needs exactly 1 unit of length per letter. Then, we simply try to put as many words on each line as possible, truncating lines if necessary to end on a word boundary.

def fits(W, H, L):
    'Returns whether text L fits on a W by H billboard.'
    pos = 0
    for line in range(H):
        pos += W
        if pos >= len(L):
            return True
        pos = L.rfind(' ', 0, pos + 1) + 1
    return False

def solve(W, H, L):
    size = 0
    while fits(W//(size + 1), H//(size + 1), L):
        size = size + 1
    return size

http://www.programminglogic.com/facebook-hacker-cup-2012-billboards-solution/
https://www.facebook.com/notes/facebook-hacker-cup/2012-qualification-round-solutions/371108282905079
Read full article from Facebook Hacker Cup 2012: Billboards Solution | Programming Logic