# 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

Ndifferent attractions, numbered from 1 toNin decreasing order of popularity. Alex visitsKattractions 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 numberV?

The variables above are constrained as follows:

1<=K<=N<=50

1<=V<=10^{12}

## 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)))
```