
As we know that Facebook's online programming contest known as "Hacker Cup" is going on. I solved first question yesterday and wanted to share the algorithm with you. I will certainly not share the code until the Contest ends. I will edit the same post once the contest gets over.
But For now I can tell you that I have used brute force algorithm with an optimization which will give me result in lesser complexity. I tried to formulate a mathematical equation but failed to solve it mathematically because of the space problem. A space will not occur in case of new line is added.
Edit[3:40 PM 22-January-2012] ::Anyways wait for the hacker cup to end only then I can conceal my algorithm. For now I can give you a hint that use brute force with doing some range based optimization or find the maximum size a font can have to accommodate all characters and then decrease font size and check if it is fitting into the billboard.
Edit[6:23 PM 22-January-2012] ::Well because of overwhelming page views of this particular post in past 3 hours. I will elaborate my algorithm a little bit more.
take an example:
10 20 MUST BE ABLE TO HACK
Lets not treat this as sentence and lets assume that each character is a square and we have to accommodate each square We will have a formula
C(h)² - (H/h)*(h)² ≤ W*H
where C is number of characters in the sentence H is Height of billboard and W is width of billboard. 'h' would be the font size we need to get.
Remember by using this equation you will get maximum size that can be attained by the font but not the actual once you will get 'h' you will iterate each time that is it the correct solution and each time reducing h by 1. finally you will get the maximum font size which can be accommodated on the billboard.
So in our example :
C = 20
H = 20
W = 10
putting it in our equation
20*h*h - H*h ≤ 200
we can find integer h can be 3 at max.
now we will check is 3 is working as brute-force testing function if it fails we will test it for 2 and bingo we will get our right answer.
Edit[4:18 PM 24-January-2012] ::Source code of my solution for more clarity
##############
#Puneet Singh#
##############
use POSIX;
open(MYINPUTFILE, "<$ARGV[0]");
# This is a Perl code by the way
@text=<MYINPUTFILE>;
$T= shift(@text);
$p=0;
foreach (@text)
{
$line=$_;
@parse=split(/[\n]/,$line);
$Width = shift(@parse);
$Height = shift(@parse);
$test= join(" ",@parse);
$changed=0;
#print $line;
$a = ($test =~ tr/[a-zA-Z0-9]//);
$b = ($test =~ tr/[ ]//) + 1;
$c = ($test =~ tr/[a-zA-Z0-9 ]//);
$x = int(($Height+sqrt($Height*$Height+(4*$c*$Width*$Height)))/(2*$c));
print $x;
$lineno = int($Height/$x);
$mciol = int($Width/$x);
$chars = $line*$mciol;
#print $x." ".$test." ".$mciol." ".$lineno." ". $b." ". $a."\n";
while(!check($test,$mciol,$lineno, $b, $a))
{
#print $x." ".$test." ".$mciol." ".$lineno." ". $b." ". $a."\n";
$x--;
$lineno = int($Height/$x);
$mciol = int($Width/$x);
$chars = $line*$mciol;
}
$p++;
#print $mciol." ";
print "Case #$p: ".$x."\n";
}
sub check{
$line=$_[0];
$maxchars = $_[1];
$lines = $_[2];
$wordcount = $_[3];
$charcount = $_[4];
@parse=split(/[]/,$line);
for($i=0;$i<$lines;$i++)
{
$word=shift(@parse);
#print "$word";
$cnt=($word =~ tr/[a-zA-Z0-9 ]//);
#print " --- ".$cnt ." --- ". $maxchars;
if($cnt > $maxchars)
{
return 0;
}
$word=@parse[0];
$newcnt=$cnt+($word =~ tr/[a-zA-Z0-9 ]//)+1;
$first=0;
while($newcnt<=$maxchars)
{
$word=shift(@parse);
#print " $word";
$word=@parse[0];
$newcnt=$newcnt+($word =~ tr/[a-zA-Z0-9 ]//)+1;
$cnt=$cnt+($word =~ tr/[a-zA-Z0-9 ]//);
}
out:
if($cnt == $charcount)
{
goto loop;
}
#print " ::: ".$newcnt;
$cnt=0;
#print "\n";
}
loop:
$last = @parse[0];
if($last)
{
return 0;
}
else
{
return 1;
}
}