Editorial for COCI '16 Contest 3 #4 Kvalitetni

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
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 $X$ ~X~, then that expression can achieve any value in the interval $[0, X]$ ~[0, X]~. Because of this, it is sufficient to calculate the maximum for each subexpression.

Let a quality expression $A$ ~A~ consist of expressions $A_1, A_2, \dots, A_k$ ~A_1, A_2, \dots, A_k~.

We distinguish between two cases:

Smaller expressions are combined with an addition operation: Then the maximum of expression $A$ ~A~ is equal to the sum of the maximums of expressions $A_1, A_2, \dots, A_k$ ~A_1, A_2, \dots, A_k~ or $Z_k$ ~Z_k~ 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 $Z_k/k$ ~Z_k/k~, 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 $V_1, V_2, \dots, V_k$ ~V_1, V_2, \dots, V_k~ and assume, without loss of generality, that it holds $V_1 \le V_2 \le \dots \le V_k$ ~V_1 \le V_2 \le \dots \le V_k~. Let's denote with $X_1, \dots, X_k$ ~X_1, \dots, X_k~ the values that these subexpressions will hold in our solution.

We distinguish between two cases:
- $Z_k/k \le V_1$ ~Z_k/k \le V_1~
  
  In this case, the best solution is obtained by setting all expressions to $Z_k/k$ ~Z_k/k~.
- $Z_k/k > V_1$ ~Z_k/k > V_1~
  
  In this case, we set $X_1 = V_1$ ~X_1 = V_1~, reduce $Z_k$ ~Z_k~ by $V_1$ ~V_1~ and repeat the procedure for $X_2, \dots, X_k$ ~X_2, \dots, X_k~. 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 $i, j$ ~i, j~ between $X_1, \dots, X_k$ ~X_1, \dots, X_k~ such that $X_i < V_i$ ~X_i < V_i~, $X_i < X_j$ ~X_i < X_j~. Then a positive real number $d$ ~d~ exists such that, if $X_i$ ~X_i~ is increased by $d$ ~d~, and $X_j$ ~X_j~ reduced by $d$ ~d~, the product of numbers $X_1, \dots, X_k$ ~X_1, \dots, X_k~ is increased, and all other conditions remain satisfied.

Comments

There are no comments at the moment.