[UPDATE]
I had trashed the post for several days as the solution was shown incorrect in final result and the post was getting high traffic. I didn’t have enough time to fix the post and didn’t wanted to mislead the visitors, so trashing was the easiest option to choose. 😉
For those who don’t know what Facebook Hacker Cup is, it an annual event hosted by Facebook itself which test your skill in Algorithms and problem solving.
Facebook Hacker Cup 2012 Qualification Round ended some hours ago and now I can post my solutions here and that won’t be cheating. 😉 Final scoreboard is still not updated but I believe my solutions are correct, at least for example input/output, they worked correctly & efficiently.
Last year, I successfully solved all three problems of Qualification round ( 2 medium level and 1 hard) and 2 problems of Round 1 (hard level but didn’t work efficiently in time limit for their huge constraints). Sadly, this year, I could solve only two problems out of three. I failed to solve Auction problem. Don’t know whom to blame, my skill, lack of interest (as only 1 problem needs to be solved to qualify) or my laziness. I solved Billboard and Alphabet Soup problems. Solutions are in java.
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
UPDATE: While my solution seemed correct conceptually and even for the example input, it yielded correct output, final scoreboard said, my output was incorrect. I have not try to find the correct solution due to lack of time but if you guys can figure out my mistake, please feel free to comment. 🙂
The problem seems simple for some but it wasn’t that simple because you are not suppose to split a word. After thinking enough, I came to the solution that we should solve it by increasing font size linearly and wrapping text in billboard. Here wrapping was main thing, I mean, if total width exceed available space, just put last word in new row and follow these steps until new rows are available. And when total height of rows exceed the available height, you have your maximum size available.
I had implemented it much earlier but wasn’t getting correct answers and after a day, I realized, algorithm was correct but I was passing parameters in wrong sequence, i.e. passing height and width as width and height while function call! 😛
Lets have a look at implementation of this algorithm in Java:
[sourcecode language=”java”]
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package hackercup;
/**
*
* @author kishan
*/
import java.io.*;
public class BillBoard1 {
int h,w;
String s;
int rows=1;
int maxSize=1;
String rowText[]=new String[1000];
public BillBoard1(int w,int h, String s)
{
this.h=h;
this.w=w;
this.s=new String(s);
rowText[0]=new String(s);
}
int getMaxSize()
{
while(true)
{
//System.out.println(maxSize);
boolean b=wrapText();
if(b)
return maxSize-1;
if(rows*maxSize&gt;h)
break;
maxSize++;
}
return (maxSize-1);
}
boolean wrapText()
{
for(int i=0;iw)
{
int lastIndex=rowText[i].lastIndexOf(&quot; &quot;);
if(lastIndex==-1)
return true;
if(i==rows-1)
{
rowText[i+1]=new String(rowText[i].substring(lastIndex+1)).trim();
rows++;
}
else
{
//System.out.println(&quot;kjsdfl&quot;);
rowText[i+1]=new String(rowText[i].substring(lastIndex+1)+&quot; &quot;+rowText[i+1]).trim();
}
rowText[i]=rowText[i].substring(0,lastIndex).trim();
}
//System.out.println(rowText[i]);
}
//System.out.println(rows+&quot; &quot;+maxSize);
return false;
}
public static void main(String[] args) throws IOException
{
//int r;
FileInputStream fl=new FileInputStream(&quot;D:input1.txt&quot;);
DataInputStream dis=new DataInputStream(fl);
int t=Integer.parseInt(dis.readLine());
for(int i=1;i {
//String[] s=dis.readLine().split(&quot; &quot;);
String os=dis.readLine();
String[] s=os.split(&quot; &quot;);
String str[]=os.split(&quot;[0-9]+ [0-9]+&quot;);
//System.out.println(str[1].trim());
BillBoard1 obj=new BillBoard1(Integer.parseInt(s[0]),Integer.parseInt(s[1]),str[1].trim());
System.out.println(&quot;Case #&quot;+i+&quot;: &quot;+obj.getMaxSize());
}
}
}
[/sourcecode]
|
|
I consider this to be efficient because considering the constraints, this implementation gave output in less than a second.
Alphabet Soup
Alfredo Spaghetti really likes soup, especially when it contains alphabet pasta. Every day he constructs a sentence from letters, places the letters into a bowl of broth and enjoys delicious alphabet soup.
Today, after constructing the sentence, Alfredo remembered that the Facebook Hacker Cup starts today! Thus, he decided to construct the phrase “HACKERCUP”. As he already added the letters to the broth, he is stuck with the letters he originally selected. Help Alfredo determine how many times he can place the word “HACKERCUP” side-by-side using the letters in his soup.
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 with a sequence of upper-case letters and spaces: the original sentence Alfredo constructed.
Output
Output T lines, one for each test case. For each case, output “Case #t: n”, where t is the test case number (starting from 1) and n is the number of times the word “HACKERCUP” can be placed side-by-side using the letters from the sentence.
Constraints
1 < T ? 20
Sentences contain only the upper-case letters A-Z and the space character
Each sentence contains at least one letter, and contains at most 1000 characters, including spaces
Example input
5
WELCOME TO FACEBOOK HACKERCUP
CUP WITH LABEL HACKERCUP BELONGS TO HACKER
QUICK CUTE BROWN FOX JUMPS OVER THE LAZY DOG
MOVE FAST BE BOLD
HACK THE HACKERCUP
Example output
Case #1: 1
Case #2: 2
Case #3: 1
Case #4: 0
Case #5: 1
This problem is quite simple. You are suppose to count the frequency of character, we require to form hackercup. Each time you create hackercup, you need h, a, 2x c, k, e, r, u, p. Simple implementation of this problem in java is here:
[sourcecode language=”java”]&lt;/pre&gt;
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package hackercup2;
import java.io.*;
/**
*
* @author kishan
*/
public class Alphabet {
void calculateAlphaFor(String s,int tc)
{
int h=0,a=0,c=0,k=0,e=0,r=0,u=0,p=0;
int count=0;
for(int i=0;i {
switch(s.charAt(i))
{
case ‘H’:
h++;
break;
case ‘A’:
a++;
break;
case ‘C’:
c++;
break;
case ‘K’:
k++;
break;
case ‘E’:
e++;
break;
case ‘R’:
r++;
break;
case ‘U’:
u++;
break;
case ‘P’:
p++;
break;
default:
break;
}
}
while(true)
{
if(c<=1 || h==0 || a==0 || k==0 || e==0 ||r==0 || u==0 ||p==0 )
break;
c–;
h–;
a–;
c–;
k–;
e–;
r–;
u–;
p–;
count++;
}
System.out.println(&quot;Case #&quot;+tc+&quot;: &quot;+count);
}
public static void main(String[] a) throws IOException
{
FileInputStream fl=new FileInputStream(&quot;D:input.txt&quot;);
DataInputStream dis=new DataInputStream(fl);
Alphabet obj=new Alphabet();
int t=Integer.parseInt(dis.readLine());
for(int i=1;i {
obj.calculateAlphaFor(dis.readLine(),i);
}
}
}
[/sourcecode]
I don’t think more explanation for this solution is needed. It’s quite simple and straight forward.
Tags: 2012, algorithm, alphabet soup, billboard, facebook, hacker, hacker cup, hackercup, java, qualification round
