TopCoder problem "CountPalindromes" used in SRM 337 (Division I Level Three)



Problem Statement

    

A palindrome is a string that reads the same from left to right as it does from right to left, ignoring spaces. We are building a machine that makes the best palindromes in the world and we need you to make a function that calculates the number of possible results before trying it for the first time.

You will be given a String[] words and an int k. Each palindrome generated by the machine will be a single space separated list of words, without leading or trailing spaces, that contains at most k characters (including spaces). Each word is an element of words, and each word can be used zero or more times in each palindrome. Return the number of different palindromes that can be generated by the machine modulo 835454957.

 

Definition

    
Class:CountPalindromes
Method:count
Parameters:String[], int
Returns:int
Method signature:int count(String[] words, int k)
(be sure your method is public)
    
 

Notes

-Returning the answer modulo 835454957 means that you have to return the remainder of dividing the answer by 835454957.
-The empty string does not count as a palindrome.
 

Constraints

-words will contain between 1 and 50 elements, inclusive.
-Each element of words will contain between 1 and 15 characters, inclusive.
-Each character of each element of words will be a lowercase letter ('a'-'z').
-No two elements of words will be equal.
-k will be between 1 and 100, inclusive.
 

Examples

0)
    
{"tragic","cigar"}
24
Returns: 1
The only palindrome with no more than 24 characters is "cigar tragic" with 12 characters. "cigar tragic cigar tragic" is also a valid palindrome, but has 25 characters.
1)
    
{"z","zz"}
4
Returns: 5
The 5 different palindromes are (quotes for clarity): "z","zz","z z","z zz","zz z".
2)
    
{"aba","acaba","baca","cac","b","c","a"}
70
Returns: 370786966
Remember to return the answer modulo 835454957.
3)
    
{"hello"}
100
Returns: 0
There is no way to make a palindrome.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7418

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10661&pm=7418

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , Olexiy , Andrew_Lazarev

Problem categories:

Dynamic Programming