Facebook Hacker Cup

Yes, thanks for sharing!

I recommend everyone who have a couple hours of free time this weekend at least try to participate in this qualification round!

It's over now! Who have participated?

I've spent about hour with a half to solve first and second problems. I discussed solutions shortly in my blog.

Then I thought I can make replicas of these problems for those who did not participate, so there they are #191 and #192.

Have anyone tried / solved the third problem?

I answered both the first and second problems.

I need to tweak my solution for the first problem so that it'll accept hexadecimal input. That was a nice twist in the problem.

I'll also need to improve my solution for the second problem as it's a brute force solution. My current solution took 5:20 to calculate, barely within time limits. Effectively, for M cases, with N yes/no decisions, I have to check M x (2^N - 1) possibilities. For the contest data set, that was 2,097,152 possibilites in under six minutes. I recognize that broadly the problem is a variation of the knapsack problem. I haven't quite figured out how to get the classical algorithm to get what I'm looking for yet.

The last problem, I had an idea, but not enough time to implement. The way I see it, you must recognize that the game board (lasers, walls and open space) exists in four states: turn 0, turn 1, turn 2, turn 3 because the group of lasers each have four and only four configurations. Each space in the 4 MxN matrices represents safe spaces on each turn that do not collide with a wall or a laser beam. Next, you build a tree data structure with the position-state at each turn being a node, the children being the position-state in next turn, and the turn for calculating the lasers' aim equal to mod(tree level, 4).

You return an answer by looking at the minimum depth in the tree that has a position equal to the finish position. You return 'impossible' if the tree reaches a height of 100 and you haven't found a solution, or if all remaining leaves have no children.

> I need to tweak my solution for the first problem so that it'll accept hexadecimal input

My main idea was to prevent solutions working on integers instead of strings... While for original problem this was ok... I did not want to plainly borrow their statement.

> For the contest data set, that was 2,097,152 possibilites in under six minutes.

Hm... That is exactly why I thought that brute-force is the supposed way to do this. I usually assess that modern computers (even my old netbook) perform about 10^6 or more iterations of some simple loop per second.

So my code (in Java) worked for about 5 seconds overall... If you used Python I think it could be 3-5 times slower, but not too long also...

I mean if they wanted users to invent some whimsical solution (I know not any) they will make K=50 or more, so that brute-force was out of question... In such challenges limits are often a hints...

I hope to take a look into the third problem, but I doubt my skills would be relevant to it :)

I've missed this competition.

But during last 2 weeks I has a rest from work and I've used this time for playing with kids, skiing, hoсkey and simple forest walking outside the city.

This sounds as you were quite lucky - here pleasant weather with enough snow for outdoors activities came only a couple days ago... So we were mostly spending time at homes or with relatives, occasionally visiting some concertoes and exhibitions... Glad to return to work again, ha-ha! :)

P.S. I think there will be more similar competitions. E.g. Google Code Jam is scheduled at beginning of March. I hope I will not forget to announce it in time.

I solved all the first two , i have two ticks so hopefully both of them are correct.

Did anyone of you have participated in the last year's competition. Does the level increases a lot ?

Thanks Matthew Cole , I will try to solve it your way and see if i succeed.

> i have two ticks so hopefully both of them are correct.

If they turned to green in the score board today (after end of the round) - they are correct. :)

> Did anyone of you have participated in the last year's competition. Does the level increases a lot ?

I did. I'd say the level remains pretty the same. If I'm not mistaken you can find old problems here and for Round 1 here.

Congrats Rodion. It seems we solved the same problems. My solution to Cooking the Books was alarmingly similar to yours. :)

I managed to solve 3rd but ran into some trouble during submission. :S

See you next round.

Thanks - though I do not think I will be able to achieve much more in this contest... :)

Reminder Round 1 will took place this weekend: see time and date for your zone

Contest will long for 24 hours.

Did anyone from here clear the round 1 ??

I do not think so :)

I myself had no idea how to save the 4-th problem. So even if I coded remaining three without mistakes I could not advance (you see, people from first 500 positions have all problems solved). Even more so since I made shameful mistake in the 2-nd problem (it worked for all cases except ones with X-0, so silly).

(FB shows me that Moriarty and Eugene Lim also did not try the 4-th - perhaps it required the knowledge of some more special algorithm - I hope to study it later)

One need to build skills in Competitive Programming methodically and strategically to advance high in such contests :)

I.e. being "orange" or "red" at dedicated sites like CodeForces is roughly the measure of required skills. I've never managed to get higher than "violet". But if you are curious, I dare to recommend to try - it is at least funny... :)

P.S. I know at least several masters of competitive programming registered at CodeAbbey, but usually for them our problems are bit too easy and somewhat boring - that is what I meant by "I do not think so".

Same here , It was also my first online programming contest :)

I'd say you both are pretty cool. My first (and second, and third...) contest were mainly a total failure.

By the way do you know Zuckerberg himself was not very strong in online competitions (though it was many years ago)? Look at his TopCoder profile for curiosity :)

Thank you Sir .

Its pretty interesting to know cause he was shown as a genius programmer in the movie :P

You see, Sir, it is hard to tell what makes "genius" programmer :)

Problem solving is useful, but to build social network, to manage, develop and promote it carefully it, probably, is not the most important :D

Otherwise guys like Petr Mitrichev and Gennadiy Korotkevich would build some famous projects and not Zuckerberg...