2018 Facebook Hacker Cup qualification

When you think of Facebook, there is a good chance the first thing that comes to mind isn't programming contests. However Facebook do run an annual contest called the Hacker Cup which is worth having a look at if you're interested in programming.

This post is going to go through a solution to the tourist problem from this years qualification round. If you've not done so already, have a go at solving the problem first. If you don't mind spoilers feel free to read on.

The problem

For reference below is an abridged summary of the problem for a single case:

The Facebook campus has N different attractions, numbered from 1 to N in decreasing order of popularity. Alex visits K attractions each time he visits, starting with the attraction he's visited the least and breaking ties by visiting the most popular attraction first. Which attractions does Alex visit on visit number V?

The variables above are constrained as follows:

1 <= K <= N <= 50

1 <= V <= 10¹²

Working through an example

The following is one of the example cases:

4 3 3
LikeSign
Arcade
SweetStop
SwagStore

In the example above there are four attractions (N = 4), Alex visits 3 attractions per visit (K = 3), and we need to work out which attractions he sees on the third visit (V = 3).

On the first visit Alex will visit the three most popular attractions (LikeSign, Arcade, and SweetStop) because he's not seen any attractions yet. On the second visit he will visit the SwagStore because he's not been there, followed by the two most popular attractions (LikeSign and Arcade). Finally on his third visit he will visit the SweetStop and SwagStore so he's seen each attraction an equal number of times, followed by the most popular attraction (LikeSign) to make the number of attractions on his visit 3.

A good way to visualise this is to imagine a repeating list of the attractions being grouped by each visit:

           _
LikeSign    |
Arcade      |-- visit 1
SweetStop  _|
           _
SwagStore   |
LikeSign    |-- visit 2
Arcade     _|
           _
SweetStop   |
SwagStore   |-- visit 3
LikeSign   _|
           _
Arcade      |
SweetStop   |-- visit...
...

Once you've got the attractions for the visit, they need to be output from most to least popular, e.g.:

Case #4: LikeSign SweetStop SwagStore

Repeating patterns

The key to solving this problem is considering how big V can be, (Alex obviously likes visiting Facebook campuses). For very large values of V, iterating through each visit is going to be very slow, and trying to generate an array which is V * N long to answer the problem will need at least one terabyte of memory if the attraction names are long, and V and N are near the top end of their constraints.

Thankfully there is a quicker way. Alex's visits very quickly begin to follow a repeating pattern. In the case above, on Alex's 5^th visit he will simply repeat his first visit:

           _
LikeSign    |
Arcade      |-- visit 5
SweetStop  _|

This pattern will repeat every K * N attractions.

Writing a solution

Once you've worked out the pattern repeats, the modulus operator can be used to work out where in the repeating pattern you are, and therefore which attractions Alex will visit. This can be done with Python code similar to the following:

def solve_case(n, k, v, attractions):
    """ Return the attractions for visit v"""
    attractions = attractions.copy() * 2
    offset = (k * (v - 1)) % n
    return attractions[offset:(offset + k)]

Note: the attractions list is copied and duplicated to handle visits which include attractions from both the end and start of the list.

Once the function above is written, the input file can be parse to produce the correct output with a script similar to the following:

import sys

def solve_case(n, k, v, attractions):
    """ Return the attractions for visit v"""
    attractions = attractions.copy() * 2
    offset = (k * (v - 1)) % n
    return attractions[offset:(offset + k)]

with open(sys.argv[1]) as input_file:

    T = int(input_file.readline())
    for case in range(T):
        N, K, V = map(int, input_file.readline().split())
        attractions = []
        for _ in range(N):
            attractions.append(input_file.readline().strip())
        visited = solve_case(N, K, V, attractions)

        # Sort attractions by popularity
        visited = [place for place in attractions if place in visited]

        print("Case #%d: %s" % (case + 1, ' '.join(visited)))