SRM 350 D2, 250-Pointer (DistanceBetweenStrings)

SRM 350, D2, 250-Pointer (DistanceBetweenStrings)

James S. Plank

Original notes: January, 2014
Latest revision: Sun Jan 27 13:31:37 EST 2019

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
My Solution.cpp.
Problem Given in Topcoder: 2007
Competitors who opened the problem: 523
Competitors who submitted a solution: 503
Number of correct solutions: 303
Accuracy (percentage correct vs those who opened): 57.9%
Average Correct Time: 13 minutes, 54 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are given two strings, a and b, composed of lower and uppercase letters.
The "difference" between a and b with respect to a letter c is:

(number_of_occurences_of_c_in_a - number_of_occurences_of_c_in_b)²
You ignore case in this problem -- in other words, you treat upper and lower case versions of a letter identically.
You are given a third string, letterSet.
Calculate and return the sum of the differences betwen a and b with respect to all of the letters in letterSet.
All strings are between 1 and 50 characters long.

The examples

Example	Input	Answer
0	`a = "topcoder" b = "contest" letterSet = "tcp"`	2
1	`a = "abcdef" b = "fedcba" letterSet = "fed"`	0
2	`a = "aaaaa" b = "bbbbb" letterSet = "a"`	25
3	`a = "aaAaB" b = "BbaAa" letterSet = "ab"`	2
4	`a = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" b = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb" letterSet = "ba"`	5000
5	`a = "ToPcOdEr" b = "tOpCoDeR" letterSet = "wxyz"`	0

Testing yourself

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.

Hints

First, read the problem description and make sure that you understand what it's asking. Go through each example, and make sure that you know why each answer is correct. With example 4, use math rather than counting digits:

The answer is 5000, and the first string is all a's, while the second string is all b's. And the strings are the same size. So, let that size be s. You know that the distance between the two strings with respect to the character 'a' is s². And the distance between the two strings with respect to the character 'b' is also s². So, you need to find an s such that 2s² equals 5000. That means s² equals 2500. So s is 50: the first string is 50 a's, and the second is 50 b's. Excellent.

Now, let's start programming a solution. Your first job is to set up the DistanceBetweenStrings class, which has a public method called getDistance(). getDistance() should take three strings as parameters, and return an integer.

Now, implement getDistance() so that it simply returns zero. Get that to compile and test it. You'll see that it gives the right answer for examples 1 and 5. Ha ha.

Now, update your program so that it goes through a and b and converts upper case to lower case. Have it print out a and b, but still have it return 0. It won't be correct, but you can now test whether you did it correctly by looking at the output, especially for examples 3 and 5. Remember from class -- you can test whether a character is uppercase by testing it against the characters 'A' and 'Z'. Then you can convert uppercase to lowercase by subtracting 'A' and adding 'a'.

Now, go through every character in letterSet, and count the occurrences of that character in a and in b. Print that out. You should still return 0 -- you just want to make sure you have your code running correctly. Here it is on all of the examples:

Example 0

t 1 2
c 1 1
p 1 0

Example 1

f 1 1
e 1 1
d 1 1

Example 2

a 5 0

Example 3

a 4 3
b 1 2

Example 4

b 0 50
a 50 0

Example 5

Now finish your program by calculating the distances and returning the total.