BoundedOptimization
SRM 560 · 2012-06-05 · by meret
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
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.
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.
{"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}
85
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}
845
Returns: 294978.3333333333
{"ab+ac+ad+ae+af+ag+ah+ai+aj+ak+al+am+bc+bd+be+bf+bg","+bh+bi+bj+bk+bl+bm+cd+ce+cf+cg+ch+ci+cj+ck+cl+cm+d","e+df+dg+dh+di+dj+dk+dl+dm+ef+eg+eh+ei+ej+ek+el+em+","fg+fh+fi+fj+fk+fl+fm+gh+gi+gj+gk+gl+gm+hi+hj+hk+hl","+hm+ij+ik+il+im+jk+jl+jm+kl+km+lm"}
{10 ,11 ,12 ,13 ,14 ,15 ,16 ,17 ,18 ,19 ,20 ,21 ,22}
{15 ,16 ,17 ,18 ,19 ,20 ,21 ,22 ,23 ,24 ,25 ,26 ,27}
260
Returns: 31155.6
Submissions are judged against all 137 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BoundedOptimization with a public method double maxValue(vector<string> expr, vector<int> lowerBound, vector<int> upperBound, int maxSum) · 137 test cases · 2 s / 256 MB per case