Facebook Hacker Cup 2016: High Security
It is 2016 and therefore Facebook started its Facebook Hacker Cup 2016. It has some challenging exercises which you need to solve in a few hours. But you also need to write efficient code. If you don’t do that, you will not have enough time to solve an exercise and points will be lost. In this article, I will highlight the “High Security” exercise in the Facebook Hacker Cup qualification round. I will first give the problem description which was posted on Facebook and then tell how I tackled the problem.
Problem description
A top-secret algorithmic research facility has decided to up its security by hiring guards to keep watch over the premises. After all, they don’t want anyone sneaking in and learning the answers to questions such as “does P = NP?” and “what are the solutions to the 2016 Facebook Hacker Cup problems?”.
When viewed from above, the facility can be modeled as a grid G with 2 rows and N columns. The jth cell in the ith row is either empty (represented by Gi,j = “.”) or occupied by a building (Gi,j = “X”), and the grid includes at least one empty cell.
Guards may be potentially stationed in any of the empty cells. A guard can see not only their own cell, but also all contiguous empty cells in each of the 4 compass directions (up, down, left, and right) until the edge of the grid or a building. For example, in the grid below, the guard (“G”) can see every cell marked with an asterisk (“*”):
.*.X.X.. *G*****X
What is the minimum number of guards required such that every empty cell in the grid can be seen by at least one of them?
Input
Input begins with an integer T, the number of facilities that need guarding. For each facility, there is first a line containing the integer N. The next line contains the grid cells G1,1 to G1,N in order. The third line contains the grid cells G2,1 to G2,N in order.
Output
For the ith facility, print a line containing “Case #i: ” followed by the number of guards required to guard the facility.
Constraints
1 ≤ T ≤ 200
1 ≤ N ≤ 1,000
My solution
I few years ago, I started with the course “Algorithms” on the TU/e (Eindhoven University of Technology). Without this course, I could not find the answer to this question.
Lets define a segment. A segment is sequence of characters in a row that is “free”; it contains no guards and no sights of guards and also no buildings. First notice that there are many segments in which we can place a guard. What is the most greedy choice to place a guard? If I would place a guard insight the segment, then the whole segment is filled with the guard and its sight. I can get one other segment for free if I place the guard such that its adjacent cell is also a segment.
Implementation
I started by finding the smallest segment in Python and then place a guard opposite to that segment. I could later proof that this implementation ran in
time where
is the number of cells in the grid.
Conclusion
I handed in my solution and it was accepted by Facebook and gave me access to the first round. Saddly, I could join the first round since I had no time on the date of the first round. If you followed any algorithms related course, this cup is highly recommended and it is returning every year.