Editorial for COCI '16 Contest 3 #4 Kvalitetni
Submitting an official solution before solving the problem yourself is a bannable offence.
Let's assume that we've processed the expression in the standard way, using the stack data structure and therefore obtained a tree of expressions.
First, let's notice that, if an expression can achieve value , then that expression can achieve any value in the interval . Because of this, it is sufficient to calculate the maximum for each subexpression.
Let a quality expression consist of expressions .
We distinguish between two cases:
Smaller expressions are combined with an addition operation: Then the maximum of expression is equal to the sum of the maximums of expressions or if the sum is too high.
Smaller expressions are combined with a multiplication operation: If we assume that we don't have the constraint on the maximum of subexpressions, we could assume, for each subexpression, that its value is exactly , and then it is easily shown (for example, using the inequality of arithmetic and geometric means) that it is the maximum.
Let's denote the maximums of subexpressions with and assume, without loss of generality, that it holds . Let's denote with the values that these subexpressions will hold in our solution.
We distinguish between two cases:
In this case, the best solution is obtained by setting all expressions to .
In this case, we set , reduce by and repeat the procedure for . It is easily shown that, this way, we get the optimal solution, and for the formal proof it is crucial to take advantage of the following lemma. We leave the proof as an exercise to the reader.
Let there exist between such that , . Then a positive real number exists such that, if is increased by , and reduced by , the product of numbers is increased, and all other conditions remain satisfied.
Comments