JOIN
Get Time

   Problem Statement  

 Problem Statement for CountPalindromes

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.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 337 Round 1 - Division I, Level Three