Who would've thought? I found this problem easier to solve than the 250-point one. Solving palindromes is a tradition in computer science. I only scored 150 points out of a possible 500, and while that's not too shabby it's still 350 points short of the perfect score.
My first version was comparatively slow. It took about three-and-a-half minutes compiled with -O0 and about twenty seconds compiled with -O3:
1 #include <string>
2 #include <vector>
3 #include <iostream>
4 #include <utility>
5
6 using namespace std;
7
8 struct PalindromePhrases {
9 typedef vector<string> Words;
10 typedef vector< pair<string, bool> > TaggedWords;
11
12 bool isPalindrome(string phrase) {
13 int len = phrase.length();
14 if (!len) {
15 return false;
16 }
17
18 for (int i=0, j=len-1; i<=len/2 && j>=len/2;
19 i++, j--) {
20 if (phrase[i] != phrase[j]) {
21 return false;
22 }
23 }
24 return true;
25 }
26
27 string extrapolate(Words phrase) {
28 string extrapolated;
29 for (Words::iterator it = phrase.begin(); it != phrase.end(); it++) {
30 extrapolated += *it;
31 }
32 return extrapolated;
33 }
34
35 long long getAmountIter(TaggedWords words, Words phrase) {
36 long long amount = 0;
37
38 if (isPalindrome(extrapolate(phrase))) {
39 amount++;
40 }
41
42 if (words.size() > 0) {
43 for (int i=0; i<words.size(); i++) {
44 if (words[i].second == true) {
45 continue;
46 }
47 else {
48 phrase.push_back(words[i].first);
49 words[i].second = true;
50 amount += getAmountIter(words, phrase);
51 phrase.pop_back();
52 words[i].second = false;
53 }
54 }
55 }
56
57 return amount;
58 }
59
60 long long getAmount(vector<string> words) {
61 TaggedWords tw;
62 for (vector<string>::iterator it = words.begin(); it != words.end(); it++) {
63 tw.push_back(make_pair(*it, false));
64 }
65 for (TaggedWords::iterator it = tw.begin(); it != tw.end(); it++) {
66 cout << ((*it).first) << endl;
67 }
68 return getAmountIter(tw, vector<string>());
69 }
70 };
To me the obvious improvements here are to:
This version finished the test case in about sixteen seconds when compiled with -O0 and about 1.1 seconds when compiled with -O3:
1 #include <vector>
2 #include <iostream>
3 #include <utility>
4
5 using namespace std;
6
7 struct PalindromePhrases {
8 typedef vector<string> Words;
9 typedef vector< pair<string, bool> > TaggedWords;
10
11 bool isPalindrome(string* phrase) {
12 int len = phrase->length();
13 if (!len) {
14 return false;
15 }
16
17 for (int i=0, j=len-1; i<=len/2 && j>=len/2;
18 i++, j--) {
19 if ((*phrase)[i] != (*phrase)[j]) {
20 return false;
21 }
22 }
23 return true;
24 }
25
26 long long getAmountIter(TaggedWords* words, string* phrase) {
27 long long amount = 0;
28
29 if (isPalindrome(phrase)) {
30 amount++;
31 }
32
33 if (words->size() > 0) {
34 for (int i=0; i<words->size(); i++) {
35 if ((*words)[i].second == true) {
36 continue;
37 }
38 else {
39 (*phrase) += (*words)[i].first;
40 (*words)[i].second = true;
41
42 amount += getAmountIter(words, phrase);
43
44 phrase->resize(phrase->length() - (*words)[i].first.length());
45 (*words)[i].second = false;
46 }
47 }
48 }
49
50 return amount;
51 }
52
53 long long getAmount(vector<string> words) {
54 TaggedWords tw;
55 string phrase;
56 for (vector<string>::iterator it = words.begin(); it != words.end(); it++) {
57 tw.push_back(make_pair(*it, false));
58 }
59 for (TaggedWords::iterator it = tw.begin(); it != tw.end(); it++) {
60 cout << ((*it).first) << endl;
61 }
62 phrase.reserve(13 * 13);
63 return getAmountIter(&tw, &phrase);
64 }
65 };
I think that's quite an improvement over the first version, but pales in comparison to the top coder's solution. I decided not to dwell deeply into other people's solutions and do some research on my own.