TopCoder problem "NumericalSequence" used in SRM 259 (Division I Level One , Division II Level Three)



Problem Statement

    

A numerical sequence is called a palindrome if the reverse of the sequence is the same as the original. For example sequences {1, 2, 1}, {15, 78, 78, 15} and {112} are palindromes, but {1, 2, 2}, {15, 78, 87, 51} and {112, 2, 11} are not.

You will be given a int[] sequence. You can replace any two adjacent numbers with their sum. Your method should return a minimal number of such operations required to make the given sequence a palindrome.

 

Definition

    
Class:NumericalSequence
Method:makePalindrome
Parameters:int[]
Returns:int
Method signature:int makePalindrome(int[] sequence)
(be sure your method is public)
    
 

Constraints

-sequence will contain between 1 and 50 elements, inclusive.
-Each element of sequence will be between 1 and 10000, inclusive.
 

Examples

0)
    
{15,78,78,15}
Returns: 0
The sequence is a palindrome already.
1)
    
{1,1,1,3}
Returns: 2
We should replace two ones with 2 and afterwards replace 2 and 1 with 3.
2)
    
{15,78,87,51}
Returns: 3
3)
    
{3,23,21,23,42,39,63,76,13,13,13,32,12,42,26}
Returns: 8

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8012&pm=4619

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , lbackstrom , brett1479 , Olexiy

Problem categories:

Greedy