Our Spotify engineers love puzzles, and we are sure you do too. Here are some brain-teasers submitted by our engineers that you can try to test your own problem solving and programming skills.

## 1. Cat vs. Dog (Difficulty Level: Hard)

Problem ID: catvsdog

The latest reality show has hit the TV: “Cat vs. Dog”. In this show, a bunch of cats and dogs compete for the very prestigious Best Pet Ever title. In each episode, the cats and dogs get to show themselves off, after which the viewers vote on which pets should stay and which should be forced to leave the show.

Each viewer gets to cast a vote on two things: one pet which should be kept on the show, and one pet which should be thrown out. Also, based on the universal fact that everyone is either a cat lover (i.e. a dog hater) or a dog lover (i.e. a cat hater), it has been decided that each vote must name exactly one cat and exactly one dog.

Ingenious as they are, the producers have decided to use an advancement procedure which guarantees that as many viewers as possible will continue watching the show: the pets that get to stay will be chosen so as to maximize the number of viewers who get both their opinions satisfied. Write a program to calculate this maximum number of viewers.

### Input

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

- One line with three integers
*c*,*d*,*v*(1 ≤*c*,*d*≤ 100 and 0 ≤*v*≤ 500): the number of cats, dogs, and voters. *v*lines with two pet identifiers each. The first is the pet that this voter wants to keep, the second is the pet that this voter wants to throw out. A pet identifier starts with one of the characters ‘C’ or ‘D’, indicating whether the pet is a cat or dog, respectively. The remaining part of the identifier is an integer giving the number of the pet (between 1 and*c*for cats, and between 1 and*d*for dogs). So for instance, “D42” indicates dog number 42.

### Output

Per testcase:

- One line with the maximum possible number of satisfied voters for the show.

1 1 2

C1 D1

D1 C1

1 2 4

C1 D1

C1 D1

C1 D2

D2 C1

3

## 2. Zipf’s Song (Difficulty Level: Medium)

Your slightly pointy-bearded boss has assigned you to write software to find the best songs from different music albums. And the software should be finished in an hour. But don’t panic, you don’t have to solve the problem of writing an AI with good taste. At your disposal is the impeccable taste of a vast horde of long-tailed monkeys. Well, at least almost. The monkeys are not very communicative (or rather, you’re not sure which song “Ook!” is supposed to refer to) so you can’t ask them which songs are the best. What you can do however is to look at which songs the monkeys have listened to and use this information to deduce which songs are the best.

At first, you figure that the most listened to songs must be the best songs. However, you quickly realize that this approach is flawed. Even if all songs of the album are equally good, the early songs are more likely to be listened to more often than the later ones, because monkeys will tend to start listening to the first song, listen for a few songs and then, when their fickle ears start craving something else, stop listening. Instead, if all songs are equal, you expect that their play frequencies should follow *Zipf’s Law*.

Zipf’s Law is an empirical law originally formulated about word frequencies in natural languages, but it has been observed that many natural phenomena, such as population sizes and incomes, approximately follow the same law. It predicts that the relative frequency of the*i*’th most common object (in this case, a song) should be proportional to 1/*i*.

To illustrate this in our setting, suppose we have an album where all songs are equally good. Then by Zipf’s Law, you expect that the first song is listened to twice as often as the second song, and more generally that the first song is listened to *i* times as often as the *i*’th song. When some songs are better than others, those will be listened to more often than predicted by Zipf’s Law, and those are the songs your program should select as the good songs. Specifically, suppose that song *i* has been played *f*i times but that Zipf’s Law predicts that it would have been played *z*i times. Then you define the quality of song *i* to be *q*i = *f*i / *z*i. Your software should select the songs with the highest values of *q*i.

### Input

The first line of input contains two integers *n* and *m* (1 ≤ *n* ≤ 50000, 1 ≤ *m* ≤ *n*), the number of songs on the album, and the number of songs to select. Then follow *n* lines. The *i*’th of these lines contains an integer *f*i and string *s*i, where 0 ≤ *f*i ≤ 10^12 is the number of times the *i*’th song was listened to, and *s*i is the name of the song. Each song name is at most 30 characters long and consists only of the characters ‘a’-‘z’, ‘0’-‘9’, and underscore (‘_’).

### Output

Output a list of the *m* songs with the highest quality *q*i, in decreasing order of quality. If two songs have the same quality, give precedence to the one appearing first on the album (presumably there was a reason for the producers to put that song before the other).

30 one

30 two

15 three

25 four

two

197812 re_hash

78906 5_4

189518 tomorrow_comes_today

39453 new_genious

210492 clint_eastwood

26302 man_research

22544 punk

19727 sound_check

17535 double_bass

18782 rock_the_house

198189 19_2000

13151 latin_simone

12139 starshine

11272 slow_country

10521 m1_a1

clint_eastwood

tomorrow_comes_today

## 3. Reversed Binary Numbers (Difficulty Level: Easy)

ProblemID: Reversebinary

Yi has moved to Sweden and now goes to school here. The first years of schooling she got in China, and the curricula do not match completely in the two countries. Yi likes mathematics, but now… The teacher explains the algorithm for subtraction on the board, and Yi is bored. Maybe it is possible to perform the same calculations on the numbers corresponding to the reversed binary representations of the numbers on the board? Yi dreams away and starts constructing a program that reverses the binary representation, in her mind. As soon as the lecture ends, she will go home and write it on her computer.

### Task

Your task will be to write a program for reversing numbers in binary. For instance, the binary representation of 13 is 1101, and reversing it gives 1011, which corresponds to number 11.

### Input

The input contains a single line with an integer *N*, 1 ≤ *N* ≤ 1000000000.

### Output

Output one line with one integer, the number we get by reversing the binary representation of *N*.

## How to Submit Your Solution

To submit a solution to a problem, send an email to Puzzle@spotify.com. Include all your source code files as attachments and the problem ID or problem name as subject. Within minutes you will get a reply indicating whether your source code solved the problem, and if it didn’t, an indication of what was wrong. Your source code can be in C, C++, Java or Python (version 2.6). Input is read from stdin.

[…] Yi has moved to Sweden and now goes to school here. The first years of schooling she got in China, and the curricula do not match completely in the two countries. Yi likes mathematics, but now… The teacher explains the algorithm for subtraction on the board, and Yi is bored. Maybe it is possible to perform the same calculations on the numbers corresponding to the reversed binary representations of the numbers on the board? Yi dreams away and starts constructing a program that reverses the binary representation, in her mind. As soon as the lecture ends, she will go home and write it on her computer. See Spotify Puzzles. […]

[…] Spotify Puzzle ‘Zipf’s Song’ (Difficulty Level: Medium) […]