Facebook Billboards Problem Detailed Solution - Highly Optimized - On Special Request
I just received a request from Aniruddha Narayan asking for a detailed solution on the Facebook Billboards Problem. I had already posted about this earlier and given link to both the online working file and online ide. Still I would love to explain the code once again, the thing is my solution is much more optimized and efficient than the facebook's source code, you can read their source code here
My Algorithm:
- Calculate the maximum size possible, which will be max(S) = floor(sqrt((a(Billboard))/(n(Chars)))); which means if the string is "Facebook Hacker Cup" then the number of chars are 17, (remember counting spaces can ruin some results like "4 4 ab cd"). So if the area is 10*10, then max(S) = 5 , that means if the size is bigger than 5 then we cannot accomodate words at any cost even after splitting, so this halved the number of test cases
- what I did was, divide the billboard into rows and cols, (rows = h(bb)/max(s); cols = w(bb)/max(s);) so we have the billboard divided into cells, which mean we have to fill it like a telegram form.. :P
- we will now start reducing max(S) to get optimal value, at each point we need to check the following things, if its an error reduce the size and try again else if the cycle is successful, the max(S) in that case is the solution.
- 1st: check if max(S) is already less than 1, do not run the cycle, and out put 0
- 2nd: since we calculate max(s) based on area it is not necessary that rows*cols will be equal to number of chars for all cases, so we can optimize again here.
- We will start the cycle here, and check for many things in this cycle.
- 1st: check if by re-running the cycle we reduced the number lower than 1, kill the cycle and output 0.
- 2nd: if for that particular word in the cycle, if the n(word) < n(cols), which means if word is ABCD1234 and cols is 7, we cannot put it in here without dividing, so we reduce the size and restart the cycle.
- 3rd: check if it is a new line, if it is a new line, the deduct the word size, if it is the line you added earlier, then add a space and then add the word
- 4th: check if while adding the word you exceeded the cols (means cols will become negative) then reduce a row, and add the word to the new row
- 5th: finally check, if you reduced the row, then whether you ran out of rows or not, if you did, then reduce the size, and restart.
- 6th: if everything goes fine reduce the word from the string.
- output the attained max(S), make sure, whenever you reduce the size, you need to re-calculate the cols and rows to find the correct result.
You can use pretty much any language you are comfortable with to code with, I love PHP so did it in that, I am sure the solution can be written in a simpler language like JavaScript too.
I use some language specific functions, please check on PHP.net to find out more details regarding that particular functions.
My Source Code:<?php
$ip = fopen('php://stdin', "r"); //input resource can be a file
$op = fopen('php://stdout',"w"); //output resource can be a file
$test_cases = trim(fgets($ip)); //first line
$c = 0;
while($c < $test_cases){
$cc = $c+1; //just for outputting correct case #n
$input = trim(fgets($ip)); //getting the next line
$vals = explode(" ", $input); //converting values to array, because it can be easily handled
$w = array_shift($vals); //first array val the width
$h = array_shift($vals); //second array val the height
$string = trim(implode(" ",$vals)); //converting the array back to string
$type = (string)$string; //dealing with numbers in the input string, doing typecasting
$str = str_replace(" ","",$type); //to count just the chars we do not need spaces
unset($vals); //to make sure of garbage vals
$vals = explode(" ", $type); //after that we are back to what we left earlier, using less mem
$words = count($vals); //word count
$bill_area = $w * $h;
$chars = strlen($str);
$max_size = floor(sqrt($bill_area / $chars));
if($max_size < 1){ //last minute optimization improved performance
$status = 1; //just a switch to check when we want to end all the loops
}else{
$rows = floor($h / $max_size); //explained in 1st
$cols = floor($w / $max_size);
}
while(($rows * $cols) < $chars){ //optimizing... this was a winner!...
$max_size--; //explained in 2nd
$rows = floor($h / $max_size);
$cols = floor($w / $max_size);
}
while($status !== 1){ //We start the cycle here
$c_cl = $cols; //it is basically current_columns
for($i=0; $i<$words; $i++){
//if we decremented the max_size to 0 there is no point checking further... last minute addition
if($max_size < 1){
$status =1;
break 2;
}
//checking if the i th word cannot be accommodated in a single line
if($cols < (strlen($vals[$i]))){
$max_size = floor($w / (strlen($vals[$i])));
$rows = floor($h / $max_size);
$cols = floor($w / $max_size);
break;
}
//accomodating the new word
if($c_cl == $cols){
$c_cl = $c_cl - (strlen($vals[$i])); //if it is a new line
}else{
$c_cl = $c_cl - (strlen($vals[$i])) -1; //-1 is the space between the new and the old word
}
//backtracking if we made a wrong accommodation
if($c_cl < 0){
$rows--;
$c_cl = $cols - (strlen($vals[$i]));
}
//if we are out of rows
if($rows < 1){ //had to be placed here after error generated by backtracking in the last row
$max_size--;
$rows = floor($h / $max_size);
$cols = floor($w / $max_size);
break;
}
if($i == ($words-1)){
$status =1;
break 2;
}
}
}
if($status ==1){
fwrite($op, sprintf("Case #%d: %d\n", $cc, $max_size));
$status = 0;
}
$c++; //incrementing the while loop
}
?>
Hope you get it, just try to run it with different input sets on the ideone link above.
Cheers!
Post your comments and discussions here