Facebook decided to launch Hacker Cup, a programming contest to attract the world’s best talents to their HQ. The qualification round started on Friday 4pm (US’s PST timezone) and continues for 72 hours, so go ahead and join now.

Just finished Facebook Hacker Cup Online Qualification Round and thought that I might share some of my thoughts about it.

Just like Google’s CodeJam, this round consisted a total of three problems, and you would need to solve just one of the problem correctly to qualify for the next round.

I admit, I had a lot of fun in this round (which had a lot of hidden surprise in the problems), but the contest’s interface totally suck the hell out of a rhino’s @$$. And seemed like I am not the only one who agrees on this.

**The first glitch that really got on my nerves —**

As you download the input file, the timer starts to countdown, without you knowing about it. Then, I found a little notice on the corner saying that you would have to refresh the browser after downloading the input file to see the timer. I don’t know why, but this seemed stupid and unacceptable to me.

Second, when you want to submit the answer, it opens up a small text box (by small I mean something like 10×100 pixels), and you are suppose to paste your program’s output to that little text box. What a FAIL — They could have done much better.

*original size*of the text box where you are suppose to paste your answer into.

Third, after you submitted the answer, there is a message box that mentioned that you would need to wait until the contest is over to find out if your answer is correct. Oh well… On the other hand, the timer just continue on ticking until it says “Time expired”. You get multiple chances to submit your answer, but ONLY within the limited time. I learned the hard way. My advice to you is test your code carefully for edge cases before downloading the input. During the limited time you won’t be able to do much about it if you find that your code has a bug.

Anyway, enough ranting and let’s move on to the fun part, which are the problems itself.

**Double Squares:**

This is a really fun problem with a little surprise behind it. While you are reading the problem, you would notice a little subtitle under the main title “Facebook Hacker Cup” that says “*Too hard for brute force, switching to dp*“. It’s there for a purpose. I knew I did not get this correct because of their timer display requires a browser reload…

**Peg Game:**

You need to read this problem carefully. Don’t worry, you won’t need much from theory of probability. Reminds me of the binomial theorem. If there are no missing pegs, then the probability of each column could be calculated easily using binomial coefficients. This problem is pretty straight forward, but you need to be some what careful.

**Studious Student:**

This is a fun problem. It is easy to understand the problem statement and it is also easy to fall into a trap. This problem is not as straight forward as you think it might be.

I will post my analysis and solution after the contest is over. Till then have fun solving the problems!

Facebook Hacker Cup Online Qualification Round Begins Now!,
I found that reading the rules prior to the start of the competition helped me to fully understand what would happen during the competition. Who would have thought?

0can someone explain how the answer "0 0.375000"

for 5 4 0 1 2 2

if i am not wrong this shud be the pegs positions

…x-x-x-x

-x-x-x-

x-x—x

-x-x-x-

x-x-x-x

right ????

please help!

0I do not understand the "peg game"!!

0@Anonymous:

Your pegs' position should be correct. You are probably miscalculating your probability as 0.3333, which is a common error people made.

0@…:

All I can say is read the problem description properly again. I found their problem description for this question is not that clear, which is why most of you have problem understanding it.

0Regarding the pegs, if there is a missing peg, does the ball fall vertically or does it carry on at and angle until it does hit a beg? If if goes at an angle what happens when it hits the side

Also what happens if the ball is dropped straight into a hole?

0@Anthony:

Don't over-think. It does not go at an angle. It either drops to the left or to the right 50-50 when it hits a peg. It will then continue dropping vertically (not at an angle) until it hits another peg again.

Yes, it is possible that the ball is dropped straight to the hole (no pegs in between), which means 100% chance of getting the ball to the hole.

+1am i wrong if i say i their very first example in description its not 50%?

i count just 3 correct and 4 incorrect ways…

+1for 5 4 0 1 2 2

I get 0.625

???

+1how? i got only 0.5 from point 0. (5 correct, 5incorrect ways)

+1This is the "map":

X 0 X 1 X 2 X <—- Start in 0

A X B X C X D

X E X F – G X <—- Dash = missing peg

H X I X J X K

X 0 X 1 X 2 X <—- The target is 0

Correct ways:

0-A-E-H-0 = 0.5 * 1.0 * 0.5 * 1.0 = 0.25

0-A-E-I-0 = 0.5 * 1.0 * 0.5 * 0.5 = 0.125

0-B-E-H-0 = 0.5 * 0.5 * 0.5 * 0.125 = 0.125

0-B-E-I-0 = 0.5 * 0.5 * 0.5 * 0.5 = 0.0625

0-B-F-I-0 = 0.5 * 0.5 * 0.5 * 0.5 = 0.0625

Total = 0.25 + 0.125 + 0.125 + 0.0625 + 0.0625 = 0.625

I think that I'm right, but I'm not sure

0i did it differently, i count ways – possibilities

in your map

1. 0 – a – e – h – 0

2. 0 – a – e – i – 0

3. 0 – a – e – i – 1

4. 0 – b – e – h – 0

5. 0 – b – e – i – 0

6. 0 – b – e – i – 1

7. 0 – b – f – i – 0

8. 0 – b – f – i -1

9. 0 – b – f – j -1

10. 0 – b – f – j – 2

so thats all ways = 10 and 5 are correct. 5/10 = 0.5

so who's right? probably neither of us cause the result:D

0That's what I thought, hence asking about falling at angles. However, you can't go between the end peg and the side I don't think. So you may not use routes going via A or H.

0-B-E-I-0 = 1 * 0.5 * 1 * 0.5 = 0.25

0-B-F-I-0 = 1 * 0.5 * 0.5 * 0.5 = 0.125

Total = 0.25 + 0.125 + 0.375

It sounds weird but it works for all the test cases.

0it doesnt work for example, would be just 25%

0I think that Anthony is right…

0To all:

If you are calculating the probability as the number of correct ways divide by total number of ways, this is incorrect, although it seems correct. This is because not each of the way is equally likely to reach the goal. Anthony's calculation is correct.

0Also what about posting source code? There are a few comments on the event page saying you don't need to, however, none of the cite anything and the rules clearly contradict? How am I meant to submit the solution. Also how would I upload zip files? Finally is it ok to just read input.txt.

Many thanks and good luck everyone.

0@Anthony:

You do not need to post source code for the qualification round, however you would need to do so from the next round onwards. This is confusing for so many people that most of them even tried appending the source code right after their answers.

0Also, for the studious students one. Lexicographically speaking, is zea < zeabb < zeabbbb

0@Anthony:

Yup, that's correct.

0seems anthony is really right. thanks for hint:)

you dont need to post source code in this round, only if you get to next, i read it somewhere in coments from admin on the wall

0Yes, Anthony's calculation is correct….

X 0 X 1 X 2 X <— Line 0

A X B X C X D

X E X F – G X

H X I X J X K

X 0 X 1 X 2 X <— Line 4

in my map, the A, H, D and K should not be considered…. (in all maps the ends of lines 1, 3, 5…. should not be considered)

0@1337c0d3r

Where did you find this information?

0Your hotseny is like a beacon

0You’ve managed a first class post

0Wow, that’s a really clever way of thinking about it!

0@Anthony:

What information do you mean?

0That you don't need to provide the source code.

0@Anthony:

It was posted in the Wall by the admin. I couldn't find it anymore.

Here is the proof:

http://d2o7bfz2il9cb7.cloudfront.net/main-qimg-0b16a9431249da6a7617bdfd5c0dce2f

0Ok thanks.

Just discovered that my program doesn't work for 100*100 grids (well it does but way too slow)

0Since its a smaller board, can someone explain the last sample input for Peg Game: 3 4 0 1 1 1

This is what it looks like (i think)

X-X-X-X

-X—X-

X-X-X-X

I get .75. Someone want to explain how it's supposed to be .5?

Facebook should definitely have a Q/A interface like Google during the code jam.

Thanks

0According to what Anthony said about end pegs, it has to be something like:

X _ X _ X _ X

X _ _ _ X

X _ X _ X _ X

I'm still not sure how it got 0.5

0http://www.facebook.com/permalink.php?story_fbid=184183884944253&id=148059031890072

this link should help you all ðŸ™‚

0If we use Anthonys solutio, we'll get a tie for the second input:

3 4 1 1 1 0

Will give you those probabilities:

0: 0.000000

1: 0.500000

2: 0.500000

3: 0.000000

But FB says that there are no ties. So something has to be wrong.

As far as I checked on the net, that problem is quite common.

Can someone show how they calculated this case?

The other cases work fine, it's just that tie, that I don't get.

Thanks

0The problem is that the grid is not a grid, the correct layout is something like this:

X 0 X 1 X 2 X <— Line 0

X A X B X

X C X D – E X

X F X G X

X 0 X 1 X 2 X <— Line 4

0@Anonymous:

Yeah I get a tie for that case "3 4 1 1 1 0" too. Does anyone know is this a FB being mistaken saying "There are no ties"?

0look this -> http://illya-keeplearning.blogspot.com/search/label/hackercup

0Look at this great blog explaining the solutions of qualification round of Hacker Cup.

Double Squares: http://itbhu.ac.in/codefest/blog/?p=159

Peg Game: http://itbhu.ac.in/codefest/blog/?p=172

Studious Student : http://itbhu.ac.in/codefest/blog/?p=180

Hope you will love this.

0Pingback: LeetCode | Technical interview solutions