TopCoder problem "OperationsArrangement" used in SRM 285 (Division II Level Three)



Problem Statement

    

You are given a sequence of digits. You must insert either a '+' (addition) operator or a '*' (multiplication) operator between each pair of adjacent digits in such a way that minimizes the value of the resulting expression. The expression should be evaluated using the standard order of operations (multiplication has a higher precedence than addition).

You will be given a String sequence. Perform the procedure described above on the sequence and return the resulting expression. If there are several possible answers, return the one that comes first lexicographically. Note that '*' comes before '+' lexicographically.

 

Definition

    
Class:OperationsArrangement
Method:arrange
Parameters:String
Returns:String
Method signature:String arrange(String sequence)
(be sure your method is public)
    
 

Constraints

-sequence will contain between 2 and 50 characters, inclusive.
-Each character in sequence will be a digit ('0'-'9').
 

Examples

0)
    
"222"
Returns: "2*2+2"
The minimal result can be obtained in three ways: "2*2+2", "2+2*2" and "2+2+2". The first one comes first lexicographically.
1)
    
"322"
Returns: "3+2*2"
2)
    
"307"
Returns: "3*0*7"
3)
    
"391118571"
Returns: "3+9*1*1*1+8+5+7*1"
4)
    
"111221911212"
Returns: "1*1*1*2*2*1+9*1*1+2*1*2"

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8082&pm=5952

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Dynamic Programming, Math