SRM 719, D2, 250-Pointer (LongLiveZhangzj)

James S. Plank

Thu Sep 14 11:21:29 EDT 2017

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: August, 2017
Competitors who opened the problem: 195
Competitors who submitted a solution: 185
Number of correct solutions: 180
Accuracy (percentage correct vs those who opened): 92.3
Average Correct Time: 8 minutes, 3 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are given two vectors of string, speech and words.
All strings are composed solely of lower case letters.
Although the topcoder constraints say that each vector is limited to 50 strings in size, I am increasing those constraints to 10000.
The strings in words are unique.
Return the number of strings in speech that are also in words.

The examples

Example 0:

speech = {"make", "topcoder", "great", "again"}
words  = {"make", "america", "great", "again"}
return value: 3

Example 1:

speech = {"toads"}
words  = {"toad"}
return value: 0

Example 2:

speech = {"a", "a"}
words = {"a"}
return value: 2

Example 3:

speech = {"je", "le", "ai", "deja", "vu", "et", "je", "le", "veux", "encore"}
words  = {"i", "am", "having", "deja", "vu", "please", "stop", "the", "encore"}
return value: 3

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, and the running time should be well less than a second, total.

Hints

With the topcoder constraints being so low, a simply double-nested for loop will work. However, being the good computer scientist that you, dear reader, are, (and given the fact that my testing script increases those constraints), you will naturally take offense at writing an O(n²) solution to this problem.

Instead, insert the words in words into a set, and then for each word in speech(), try to find it in the set. Now your solution is O(n log n), and all is alsmost right with the universe.

Instead, substitute an unordered_set for the set, and your solution is O(n). Now all is indeed right with the universe.