TopCoder problem "PalindromeGame" used in SRM 499 (Division II Level Three)



Problem Statement

    You are playing a simple one-player game in which you are given a set of cards. Each card has a string written on the front and a number on the back. The strings on all the cards have the same length. You must choose some of these cards (at least one, possibly all) and place them in a row with the front sides visible, such that the concatenated string is a palindrome. A palindrome is a string that reads the same forward and backward. Your score is the sum of the numbers on the back sides of the chosen cards.



You are given a String[] front and a int[] back describing the set of cards you are given. The i-th card has front[i] written on the front and back[i] on the back. Return the maximum possible score you can achieve with these cards. If it is impossible to compose a palindrome from the given cards, return 0 instead.
 

Definition

    
Class:PalindromeGame
Method:getMaximum
Parameters:String[], int[]
Returns:int
Method signature:int getMaximum(String[] front, int[] back)
(be sure your method is public)
    
 

Constraints

-front will contain between 1 and 50 elements, inclusive.
-Each element of front will contain between 1 and 50 characters, inclusive.
-Each element of front will contain the same number of characters.
-Each character in front will be a lowercase letter ('a' - 'z').
-front and back will contain the same number of elements.
-Each element of back will be between 1 and 1,000,000, inclusive.
 

Examples

0)
    
{ "topcoder", "redcoder", "redocpot" }
{ 7, 5, 3 }
Returns: 10
You can choose "topcoder" with 7 and "redocpot" with 3 to get a palindrome "topcoderredocpot".
1)
    
{ "rabbit" }
{ 1000000 }
Returns: 0
No palindrome can be made.
2)
    
{ "abc", "abc", "def", "cba", "fed" }
{ 24, 7, 63, 222, 190 }
Returns: 499

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14428&pm=11331

Writer:

lyrically

Testers:

PabloGilberto , ivan_metelsky , nika

Problem categories:

Greedy, Simple Search, Iteration