[Update@2012-01-24] I made a little mistake in a `if...else...`

statement.

Facebook started **Facebook Hacker Cup 2012** from January 20 at 4:00pm PST, and until January 23 at 4:00pm PST, the event is closed to receive submission.

There are three questions, when I learned the event, the event is already started and left me only near 16 hours to take some challenge.

I picked “Billboard problem”.

## The original question

## 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 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

## 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`

## My Solution

I used Objective-C to resolve this problem. I created a Mac app project. Later I think it’s completely unnecessary. I will try to use maybe pure `C`

or `Cocoa Console`

later.

Here is the my solution on github

The key idea behind my solution is divide and conquer.

### 1. Find the possible max font size

- Assume the billboard only show one line or one column, the
`MIN(width, height)`

will give the first guess of the max font size. - Assume all the characters without space will be layout on the billboard one by one, the biggest font to whole all characters will be our
**possible max font size**. Because if we add any space or non-hyphenation constraints to layout, we must shrink the font to hold these extra constraints.

Here I used the D&C to find the possible max font size:

```
- (NSInteger)maxFontSizeForText:(NSString *)text
withTextInArray:(NSArray *)textInArray
constraintToArea:(NSInteger)rectArea
withBounds:(NSDictionary *)bounds
{
NSParameterAssert(text);
NSParameterAssert(textInArray);
NSParameterAssert(bounds);
NSInteger upperSize = [[bounds objectForKey:UPPER_BOUND_KEY] integerValue];
NSInteger lowerSize = [[bounds objectForKey:LOWER_BOUND_KEY] integerValue];
// NSLog(@"*** finding max size between %4ld...%ld", lowerSize, upperSize);
NSInteger upperArea = upperSize * upperSize * ([text length] - ([textInArray count] - 1));
NSInteger lowerArea = lowerSize * ([text length] - ([textInArray count] - 1));
// No need to go further, there will be one size suitable for rectArea
if (1 >= (upperSize - lowerSize)) { // there could be a case of 0
if (upperArea <= rectArea) {
return upperSize;
}else if (lowerArea <= rectArea){
return lowerSize;
}else {
return 0;
}
}
// Otherwise, we need to go recursive routine to find the max size in lower...upper
NSInteger middleSize = lowerSize + ((upperSize - lowerSize) >> 1);
NSInteger middleArea = middleSize * middleSize * ([text length] - ([textInArray count] - 1));
if (middleArea > rectArea) {
NSDictionary *boundsDict = [NSDictionary dictionaryWithObjectsAndKeys:
[bounds objectForKey:LOWER_BOUND_KEY], LOWER_BOUND_KEY,
[NSNumber numberWithInteger:middleSize], UPPER_BOUND_KEY,
nil];
return [self maxFontSizeForText:text withTextInArray:textInArray constraintToArea:rectArea withBounds:boundsDict];
}else {
NSDictionary *boundsDict = [NSDictionary dictionaryWithObjectsAndKeys:
[NSNumber numberWithInteger:middleSize], LOWER_BOUND_KEY,
[bounds objectForKey:UPPER_BOUND_KEY], UPPER_BOUND_KEY,
nil];
return [self maxFontSizeForText:text withTextInArray:textInArray constraintToArea:rectArea withBounds:boundsDict];
}
}
```

### 2. Find the correct max font size

Try to fit the text start with `possible max font`

, then shrink the font size to meet the constraints.

This is simple but have some complex `if...else...`

statements.

[Update 2012-01-24] Thanks to Chong, the following algorithm failed to find the correct font size for Case #7, it should be

`9`

instead of`8`

, to fix this, I need to modify 2 places, change`realFontSize = width/[aWord length];`

to`realFontSize--;`

and change`realFontSize = height/(currentLineIndex + 1);`

to`realFontSize--;`

```
// Another core algorithm that will try and shrink the font size to fit the billboard
- (NSInteger)correctMaxFontSizeForNoHyphenationFor:(NSArray *)textInArray
constraintTo:(NSInteger)possibleMaxFontSize
boardWidth:(NSInteger)width
boardHeight:(NSInteger)height
{
NSParameterAssert(textInArray);
if (possibleMaxFontSize == 0) {
return 0;
}
NSInteger realFontSize = possibleMaxFontSize;
BOOL finished = NO;
do {
NSInteger currentLineWidth = 0;
NSInteger currentLineIndex = 0;
for (int idx= 0; idx < [textInArray count]; idx++) {
NSString *aWord = [textInArray objectAtIndex:idx];
NSInteger wordLengthAppliedFontSize = [aWord length]*realFontSize;
// width is not enough for a single word
if (wordLengthAppliedFontSize > width) {
realFontSize = width/[aWord length];
currentLineIndex = 0;
currentLineWidth = 0;
break;
}
// current word is safe for at least one line, see if it is safe to add to current line.
if (currentLineWidth + wordLengthAppliedFontSize > width) {
// need a new line
currentLineIndex++;
currentLineWidth = wordLengthAppliedFontSize;
}else{
currentLineWidth += wordLengthAppliedFontSize;
}
if (currentLineWidth + realFontSize < width) {
// current line is safe for one more space.
currentLineWidth += realFontSize;
//}else{ //<- Here cause the case #1 failed
}else if (idx != ([textInArray count] -1)){
// need a new line
currentLineIndex++;
currentLineWidth = 0;
}
// height is not enough for the whole text
if ((currentLineIndex + 1) * realFontSize > height){
realFontSize = height/(currentLineIndex + 1);
currentLineIndex = 0;
currentLineWidth = 0;
break;
}
// done.
if (idx == [textInArray count] -1) {
// last line
finished = YES;
}
}
} while (realFontSize > 0 && !finished);
return realFontSize;
}
```

### 3. Verify it

I created some test cases to test on it. It includes some extra test cases that need to be omitted when read in the file.

Meanwhile, Facebook has an input file, you can also download it.

## Output

Here is my output, what’s yours? Whose one is correct?

```
Case #1: 30 //<- Wrong, should be 60
Case #2: 5
Case #3: 31
Case #4: 6
Case #5: 30
Case #6: 83
Case #7: 8 //<- Wrong, should be 9
Case #8: 80
Case #9: 21
Case #10: 4
Case #11: 31
Case #12: 21
Case #13: 30
Case #14: 21
Case #15: 30
Case #16: 21
Case #17: 4
Case #18: 21
Case #19: 4
Case #20: 4
```

After modified step2, I think the following result is correct:

```
Case #1: 60
Case #2: 5
Case #3: 31
Case #4: 6
Case #5: 30
Case #6: 83
Case #7: 9
Case #8: 80
Case #9: 21
Case #10: 4
Case #11: 31
Case #12: 21
Case #13: 30
Case #14: 21
Case #15: 30
Case #16: 21
Case #17: 4
Case #18: 21
Case #19: 4
Case #20: 4
```

It’s fun, **I’m no longer qualified for next round now, good luck, my friends.** *(hope I can enter the qualification round. And so do you.)*