SRM 700, D2, 250-Pointer (Xylophone)

James S. Plank

Sun Oct 23 14:43:39 EDT 2016

In case Topcoder's servers are down

Here is a summary of the problem:

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:

  1. 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.
  2. 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)).