SRM 564, D2, 250-Pointer (FauxPalindromes)

James S. Plank

Fri Dec 21 14:24:29 EST 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
tests.sh. MD5 hash: d28e3ae56ae1f8ce03ac631fbae2da3e
answers.txt. MD5 hash: 6e0336d91bff65fa3938c2ed9a5919c2
Problem Given in Topcoder: December, 2012
Competitors who opened the problem: 854
Competitors who submitted a solution: 773
Number of correct solutions: 681
Accuracy (percentage correct vs those who opened): 88.1%
Average Correct Time: 16 minutes, 49 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are given a string composed of upper-case letters, whose size is between 1 and 50 characters.
If the string is a palindrome (meaning it reads the same backward and forward), the return the string "PALINDROME".
Otherwise, if the string is a "faux" palindrome (defined below), return the string "FAUX".
Otherwise, return the string "NOT EVEN FAUX".
A "faux" palindrome is a string where, if you replace all consecutive occurrences of the same letter with a single occurrence of that letter, is a palindrome.
For example, "AABBAAAA" is a faux palindrome, because when you replace all consecutive occurrences of the same letter with a single occurrence of that letter, you get "ABA", which is palindrome.

The examples


"PALINDROME"
"FAUX"
"NOT EVEN FAUX"
"FAUX"
"PALINDROME"
"FAUX"
"NOT EVEN FAUX"

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.

You have three cases to determine:

Palindrome?
Not Palindrome, but Faux?
Not even Faux?

It's best to tackle these in order. My strategy here was to write a procedure (or method) called ispal(string s), which returned 1 if the string was a palendrome, and 0 otherwise. I then called it on word, and returned "PALINDROME" if it was a palindrome, and "NOT" otherwise. I tested this on examples 0 through 6.

Next, I constructed a new string s, which was equal to word with no consecutive identical characters. After testing this, I called ispal() on it, and that let me return either "FAUX" or "NOT EVEN FAUX".

Done.

Example	Input	Answer
0	"ANA"	"PALINDROME"
1	"AAAAANNAA"	"FAUX"
2	"LEGENDARY"	"NOT EVEN FAUX"
3	"XXXYTYYTTYX"	"FAUX"
4	"TOPCOODEREDOOCPOT"	"PALINDROME"
5	"TOPCODEREDOOCPOT"	"FAUX"
6	"XXXXYYYYYZZXXYYY"	"NOT EVEN FAUX"