BoundedOptimization | Topcoder Archive

Problem Statement

You are given an arithmetic expression. The expression is a sum of one or more terms. Each term is a product of exactly two variables. In each term, the two variables are distinct. No two terms contain the same pair of variables.

Additionally, the following constraints are given:

For each i, the i-th variable (0-based index) must have a value between lowerBound[i] and upperBound[i], inclusive. The bounds are integers, but the value of the variable can be any real number in the given range.
The sum of all variables must not exceed maxSum.

You are given a String[] expr, the int[]s lowerBound and upperBound, and the int maxSum. Concatenate the elements of expr to obtain the considered expression. For each i, the i-th variable will be denoted by the i-th lowercase letter of the English alphabet. (Both indices are 0-based, so variable 0 is 'a', variable 1 is 'b', and so on.)

Return the maximum value of the expression, given that all the above constraints have to be satisfied. Note that the constraints guarantee that it is possible to satisfy all the given constraints.

Definition

Class:: BoundedOptimization
Method:: maxValue
Parameters:: String[], int[], int[], int
Returns:: double
Method signature:: double maxValue(String[] expr, int[] lowerBound, int[] upperBound, int maxSum)
(be sure your method is public)

Notes

Your return value must have a relative or an absolute error of less than 1e-9.

Constraints

expr will contain between 1 and 50 elements, inclusive.
Each element of expr will contain between 1 and 50 characters, inclusive.
Each character in each element of expr will be '+' or one of the first n lowercase letters of the English alphabet, where n is the number of elements in lowerBound.
The concatenation of the elements of expr will consist of pairs of letters separated by '+' characters.
No unordered pair of consecutive letters will appear twice in the concatenation of the elements of expr.
No two consecutive letters in the concatenation of the elements of expr will be equal.
lowerBound will contain between 2 and 13 elements, inclusive.
Each element of lowerBound will be between 0 and 100, inclusive.
upperBound will contain n elements, where n is the number of elements in lowerBound.
For each i between 0 and n - 1, the i-th element of upperBound will be between lowerBound[i] and 100, inclusive.
maxSum will be between the sum of the elements of lowerBound and 1,300, inclusive.

Examples

```
{"ba+cb"}
```
```
{0,0,1}
```
```
{1,2,1}
```
```
3
```
```
Returns: 2.25
```
The maximum value is obtained by setting a = 0.5, b = 1.5, c = 1.
```
{"ab"}
```
```
{0, 0, 10}
```
```
{20, 20, 20}
```
```
12
```
```
Returns: 1.0
```
We have to set a proper value for c even though it is not present in the expression described by expr.

{"ca+fc+fa+d","b+da+","dc+c","b","+ed+eb+ea"}

{10,11,12,13,14,15}

{15,16,17,18,19,20}

Returns: 2029.25

{"db+ea+ik+kh+je+","fj+lk+i","d+jb+h","a+gk+mb+ml+lc+mh+cf+fd+","gc+ka+gf+bh+mj+eg+bf+hf+l","b+al+ja+da+i",
"f+g","h+ia+le+ce+gi+d","h+mc+fe+dm+im+kb+bc+","ib+ma+eb+mf+jk+kc+mg+mk+","gb+dl+ek+hj+dg+hi","+ch+ga+ca+fl+ij+fa+jl+dc+dj+fk","+li+jg"}

{57,29,50,21,49,29,88,33,84,76,95,55,11}

{58,80,68,73,52,84,100,79,93,98,95,69,97}

Returns: 294978.3333333333

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.