TopCoder problem "ChartError" used in TCCC05 Semi 2 (Division I Level Three)



Problem Statement

    Given a collection of real values, we want to represent them with a bar chart. Each value will be represented by a number of characters, and the bar chart will also display the value per character. For example, 
   Sales :  XXXXXXXXXX
   Profit:  XXXX
   Costs :  X
   (Each X has a value of 8.8)
In this bar chart, the "bar_value" of the first bar, which contains 10 characters, is 10*8.8 = 88.0

No bar in our chart is allowed to contain more than 15 characters, and each bar must contain an integer number of characters. Unfortunately, we may not be able to represent all the values exactly. We define the "bar_error" for a bar to be the absolute value of the difference between its bar_value and the true value that it is meant to represent. We define the "chart_error" for the bar chart to be the maximum bar_error.

Construct a class ChartError that contains a method minErr that is given a String[] val containing the values we want to represent in our bar chart as decimal strings, and that returns the minimum chart_error that is possible.

 

Definition

    
Class:ChartError
Method:minErr
Parameters:String[]
Returns:double
Method signature:double minErr(String[] val)
(be sure your method is public)
    
 

Constraints

-val will contain between 1 and 50 elements inclusive.
-Each element of val will contain between 2 and 10 characters inclusive.
-Each element of val will consist of digits '0'-'9' and exactly one decimal point.
-Each element of val will have no more than 2 digits before the decimal point.
 

Examples

0)
    
{"88.0","44.0","8.8"}
Returns: 0.0
Use 8.8 as the value per character. Then assign 10 characters to 88.0, 5 to 44.0, and 1 to 8.8. The bar chart might appear as in the problem description.
1)
    
{"9.0","10.","08.9",".1"}
Returns: 0.1
Use 1.0 as the value per character. Assign 10 characters to the second bar, 0 characters to the last bar, and 9 characters to the others. Then 0, 0, .1, and .1 are the resulting bar_errors.
2)
    
{"3.123456","3.123556","3.123456","3.123456","3.123456","3.123456",
 "3.123456","3.123456","3.123456","3.123456","3.123456","3.123456",
 "3.123456","3.123456","3.123456","3.123456","3.123456","3.123456",
 "3.123456","3.123456","3.123456","3.123456","3.123456","3.123456",
 "3.123456","3.123456","3.123456","3.123456","3.123456","3.123456",
 "3.123456","3.123456","3.123456","3.123456","3.123456","3.123456",
 "3.123456","3.123456","3.123456","3.123456","3.123456","3.123456",
 "3.123456","3.123456","3.123456","3.123456","3.123456","3.123456",
 "3.123456","3.123456"}
Returns: 5.000000000008195E-5

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6551&pm=2873

Writer:

dgoodman

Testers:

PabloGilberto , lbackstrom , vorthys

Problem categories:

Brute Force, Search