SRM 673, D2, 250-Pointer (BearSong)

James S. Plank

Tue Aug 30 00:47:32 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
A solution.
tests.sh. MD5 hash: 081764748781f1acd439c528c3122686
answers.txt. MD5 hash: aff52e280b117d5ac6b23bed4fdf5802
Problem Given in Topcoder: November, 2015
Competitors who opened the problem: 528
Competitors who submitted a solution: 500
Number of correct solutions: 452
Accuracy (percentage correct vs those who opened): 85.60%
Average Correct Time: 9 minutes, 12 seconds.

In case Topcoder is down

You are given a vector of integers called notes.
Return how many integers appear exactly once in the vector.
The Topcoder constraint is that the vector has at most 50 elements and each element is a number from 1 to 1000. I'm bumping these constraints up so that the vector has at most 100,000 elements and the elements may be any integer.

The Examples

Example 0: notes = { 9, 10, 7, 8, 9 }.
Answer: 3 - 7, 8 and 10 appear exactly once.
Example 1: notes = { 8, 8, 7, 6, 7, 3, 5, 10, 9, 3 }.
Answer: 4 - 5, 6, 9 and 10 appear exactly once.
Example 2: notes = { 234, 462, 715, 596, 906 }.
Answer: 5 - each number appears exactly once.
Example 3: notes = { 17 }.
Answer: 1.
Example 4: notes = { 1000, 1000, 1000, (repeated 50 times) }.
Answer: 0.

Testing yourself

Like always, if you give the example number on the command line, it will run that example. If you specify "-" on the command line, you can enter the vector on standard input. If you give a number greater than 4 on the command line, then it will generate a random example, using the number as a seed. If you give a number less than -4, then it will generate a random example, using the negated number as a seed, and it will print the vector on standard output. So, for example, if you want to see the vector for seed 2006, then do "./a.out -2006".

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

Examples with small vectors: 5907, 8051, 2006, 4150, 6294, 249, 8438, 2393 and 4537. ~\>

Hints

This is a map problem (unordered is better than ordered). Create a map whose key is the pitch, and whose value is the number of times that you see the pitch. Your first step is to run through the pitches, and create/update the elements in the map.

Your second step is to traverse the map and count the number of entries whose second field equals one.