SRM 604, D2, 250-Pointer (FoxAndWord)

James S. Plank

Sat Jan 18 09:54:26 EST 2014

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: September, 2014
Competitors who opened the problem: 1426
Competitors who submitted a solution: 1208
Number of correct solutions: 976
Accuracy (percentage correct vs those who opened): 68.4%
Average Correct Time: 20 minutes, 23 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are given a vector of strings named words. It has at most 50 words. Each word is composed of lower case letters and is at most 50 characters in size.
Two words a and b are considered "interesting", if you can split word a into two parts, reverse the parts, and end up with string b. For example, the strings "tokyo" and "kyoto" are interesting, because you can split "tokyo" into "to" and "kyo", and when you reverse them, you get "kyoto".
Return the number of pairs of interesting words in words.

The examples

Example	Input	Answer
0	{"tokyo", "kyoto"}	1
1	{"aaaaa", "bbbbb"}	0
2	{"ababab","bababa","aaabbb"}	1
3	{"eel", "ele", "lee"}	3
4	{"aaa", "aab", "aba", "abb", "baa", "bab", "bba", "bbb"}	6
5	{"top","coder"}	0

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.

Hints

Give this one a try, and if you want help, then scroll down and read below.

There are two parts to this problem. First, you need to write a loop that allows you to compare every pair of words in words. For example, in Example 2, you will check:

"ababab" and "bababa"
"ababab" and "aaabbb"
"bababa" and "aaabbb"

Go ahead and make that your first job -- write a nested loop which simply prints out each pair of words. Here's mine on examples 2, 3 and 4. Yours doesn't have to work in the same order, but it does need to generate the same pairs.

Example 2:

bababa ababab
aaabbb ababab
aaabbb bababa

Example 3:

ele eel
lee eel
lee ele

Example 4:

aab aaa
aba aaa
aba aab
abb aaa
abb aab
abb aba
baa aaa
baa aab
baa aba
baa abb
bab aaa
bab aab
bab aba
bab abb
bab baa
bba aaa
bba aab
bba aba
bba abb
bba baa
bba bab
bbb aaa
bbb aab
bbb aba
bbb abb
bbb baa
bbb bab
bbb bba

Now, given a pair of words, like "tokyo" and "kyoto", how do we determine that they are interesting? One simple way is to break up the first word into every combination of two substrings (which we'll call A and B below), concatenate the substrings in reverse order, and see if they equal the second word. For example:

A	B	B + A	Does it equal "kyoto"?
t	okyo	okyot	No
to	kyo	kyoto	Yes
tok	yo	yotok	No
toky	o	otoky	No

To break up strings into substrings, see the substr() method. I provide examples in the string lecture notes for CS140.

Running Time

One of the skills of a computer scientist is being able to determine the running time of his or her program. In this instance, we ask the question -- if the size of words is W and the maximum size of a word is S, then how does the performance of our program scale with W and S.

In this instance, you are generating all pairs of words of words, and there are (W(W+1))/2 of these. For each pair of words, you are calculating S-1 values of A and B, and the work required to compute A+B is roughly S. Therefore, your program scales with W and S roughly as:

W²S²

With topcoder, the maximum W is 50, and the maximum S is also 50, so the equation above gives you 6,250,000. That's going to be pushing topcoder's time limits, but it is fast enough. Later in the semester, when we study maps, you'll be able to see how to make this program faster.