Connection Status:
Competition Arena > CountPalindromes

CountPalindromes

SRM 337 · 2007-02-03 · by soul-net

SRM 337 · 2007-02-03 · by soul-net · Dynamic Programming
Class Name: CountPalindromes
Return Type: int
Method Name: count
Arg Types: (vector<string>, int)
Problem Statement

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.

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.

4)
{"a"}
100
Returns: 50

You can use the word up to 50 times for 50 different palindromes.

Submissions are judged against all 84 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CountPalindromes with a public method int count(vector<string> words, int k) · 84 test cases · 2 s / 256 MB per case

Submitting as anonymous