Home » programming » Facebook Hacker Cup 2014 Qualification Round

Facebook Hacker Cup 2014 Qualification Round

I was lucky enough to get notified by someone about this competition. There is already a very nice write-up of the solutions. Here, I am presenting briefly alternative solutions about the first two problems. You can find the problem statements on facebook.

Square Detector

The problem: “You are given a grid of N×N square cells. Each cell is either white or black. Your task is to detect whether all the black cells form a square shape.”

My solution was to count the number of consecutive filled in cells in every row and in every column. Because that would allow some gaps, we require non-empty rows/columns to be consecutive.

Basketball Game

There are two useful observations.

First, if T_{k} is the number of players of the team k, then every T_{k} minutes, that team has the same players on the field. Therefore, we are interested only in number of minutes m %= T_{k}.

Second, we can figure out that a player enters the field after all the rest of the players of his team have played. Therefore, if we sort again the array of players in such a way that in every round we remove a player from the beginning of the array, we put him at the end of the array and we know that only the first P players are still on the field. The array is already sorted in such a way (we did it in order to find the squad number of each player) apart from the first positions (the players that start on the field) which should be reversed.

Using these two observations, we can find the players on the field easily. If we are towards the end of the sorted array and we need more players, we just take them from the first positions of the array.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: