SRM 700, D2, 250-Pointer (Xylophone)

James S. Plank

Sun Oct 23 14:43:39 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: October, 2016
Competitors who opened the problem: 287
Competitors who submitted a solution: 281
Number of correct solutions: 212
Accuracy (percentage correct vs those who opened): 73.87
Average Correct Time: 8 minutes, 47 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

There are keys on a xylophone, numbered 1 to 50.
Each key corresponds to a note which is identified by a letter from A to G.
Key 1 corresponds to A; key 2 corresponds to B, and so on up to key 7, which corresponds to G.
Then, they start over, so key 8 corresponds to A; key 9 corresponds to B, and so on up to key 14, which corresponds to G.
They keep cycling like that.
You are given a vector keys, which contains up to 50 elements, which are each numbers between 1 and 50.
You should return the number of distinct notes in key.

Examples

Number   Input                              Answer
-----    ---------------------------------- ------
0)       {1,8,3}                            2: The notes are A, A and C.  That's two distinct notes.
1)       {7,3,2,4,1,5,6}                    7: A through G are all in keys
2)       {1,8,15}                           1: These are all A
3)       {25,1,17,9,8}                      4
4)       {11,11,11,11,11,11,11,11,11,11,11} 1
5)       {50,10,20,30,11,30,24,38,5,2,9}    6

Testing yourself

Like the Cryptography Problem, I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt.

Try this one without any hints. If you get stuck or frustrated, come back here, and there are hints if you scroll down.

Each key on the Xylophone maps to one of seven notes. You don't care what the notes are. You just want to know which distinct notes are played. So, take each key played, and calculate its value mod 7. That value will be different for each note (For example, if you play an A, and then a B, the first key mod 7 will not equal the second key mod 7. However, if you play two A's, even on different keys, then their values mod 7 will be the same).

So what you want to do is count the number of distinct values there are when you take each key mod 7. There are two straightforward ways to do this:

Have a vector whose size is seven. Set a vector's entry to one, whenever the key mod 7 equals the entry's index. Then sum the vector's entries.
Have a set of integers, and insert each (key mod 7) into the set. Since you cannot insert duplicates into sets, at the end, the size of the set will be your answer.

Which of these is faster? The first one -- it is O(n), where n is the number of keys. The second one is O(n log(n)).