This code appeared in the Facebook Hacker Cup 2012 – Qualification Round

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

Sample 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

Sample Output
Case #1: 3
Case #2: 10
Case #3: 2
Case #4: 8
Case #5: 7

My Solution

My first approach was to develop a simple solution that would start with font size 1 and increase it gradually, until a certain font size wouldn’t fit anymore, returning the previous font value.

#include <cstdio>
#include <string>
using namespace std;

int maxFont(int width, int height, int stringLengths[], int z){
    int font = 1;
    int widthLeft,lines,i;

    while(font<=height){
        lines = height/font;
        widthLeft = width;

        for (i=0;i<z;i++){
            if (stringLengths[i]*font<=widthLeft){
                widthLeft-=(stringLengths[i]*font+font);
            }
            else if (lines>1){
                lines--;
                widthLeft=width;
                if (stringLengths[i]*font<=widthLeft){
                    widthLeft-=(stringLengths[i]*font+font);
                }
                else{
                    break;
                }
            }
            else{
                break;
            }
        }/* end of for */

        if (i==z)
            font++;
        else
            break;
    } /* end of while */

    return font-1;

} /* end of maxFont */

int main(){
    int t,i,z;
    int width,height;
    int stringLengths[500];
    char c;

    scanf("%d",&t);

    for (i=0;i<t;i++){
        scanf("%d %d", &width, &height);
        z=0;
        c=getchar();
        while (c==' '){
            stringLengths[z]=0;
            c=getchar();
            while(c!=' '&&c!=10){
                stringLengths[z]++;
                c=getchar();
            }
            z++;
        }
        printf("Case #%d: %d",i+1,maxFont(width,height,stringLengths,z));
        if (i<t-1)
          printf("n");
    }

    return 0;
}

Since I would have only 6 minutes to submit my answer file, I wanted to have a backup algorithm in case the above one was too slow (or didn’t work at all). So I developed one where I would search for the max font size with binary search.

#include <cstdio>
#include <string>
using namespace std;

#define min(a,b) (a<b?a:b)
int array[1000];

int fontFits(int font, int width, int height, int stringLengths[], int z){
    int lines = height/font;
    int widthLeft = width;
    int i;

    for (i=0;i<z;i++){
        if (stringLengths[i]*font<=widthLeft){
            widthLeft-=(stringLengths[i]*font+font);
        }
        else if (lines>1){
            lines--;
            widthLeft=width;
            if (stringLengths[i]*font<=widthLeft){
                widthLeft-=(stringLengths[i]*font+font);
            }
            else{
                break;
            }
        }
        else{
            break;
        }
    }/* end of for */

    if (i==z)
        return 1;
    else
        return 0;
}

int bSearch(int start, int end, int width, int height, int stringLengths[], int z){
    if (start>end)
        return -1;

    int mid = (start+end)/2;

    if (fontFits(array[mid], width, height, stringLengths, z)){
        if (fontFits(array[mid+1], width, height, stringLengths, z)){
            return bSearch(mid+1,end,width,height,stringLengths,z);
        }
        else{
            return mid;
        }
    }
    else{
        if (fontFits(array[mid-1], width, height, stringLengths, z)){
            return mid-1;
        }
        else{
            return bSearch(start,mid-1,width,height,stringLengths,z);
        }
    }

    return -1;
}

int maxFont(int width, int height, int stringLengths[], int z){
    int fontLimit = min(int(width/stringLengths[0]),height) + 1;
    int i,result;

    if (fontLimit==1){
        if (fontFits(1,width,height,stringLengths,z))
            return 1;
        else
            return 0;
    }

    else{
        for (i=0;i<fontLimit;i++){
            array[i]=i+1;
        }

        result = bSearch(0,fontLimit-1,width,height,stringLengths,z);

        if (result==-1)
            return 0;
        else
            return array[result];
    }
}

int main(){
    int t,i,z;
    int width,height;
    int stringLengths[500];
    char c;

    scanf("%d",&t);

    for (i=0;i<t;i++){
        scanf("%d %d", &width, &height);
        z=0;
        c=getchar();
        while (c==' '){
            stringLengths[z]=0;
            c=getchar();
            while(c!=' '&&c!=10){
                stringLengths[z]++;
                c=getchar();
            }
            z++;
        }
        printf("Case #%d: %d",i+1,maxFont(width,height,stringLengths,z));
        if (i<t-1)
          printf("n");
    }

    return 0;
}

It turns out that both algorithms were fast enough, and the solution was correct. Yay. This was the first out of 3 problems on the qualification round. I’ll talk about the other two on other posts.