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, then that expression can achieve any value in the interval [0, X]. Because of this, it is sufficient to calculate the maximum for each subexpression.

Let a quality expression A consist of expressions 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 is equal to the sum of the maximums of expressions A_1, A_2, \dots, A_k or 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, 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 and assume, without loss of generality, that it holds V_1 \le V_2 \le \dots \le V_k. Let's denote with 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

      In this case, the best solution is obtained by setting all expressions to Z_k/k.

    • Z_k/k > V_1

      In this case, we set X_1 = V_1, reduce Z_k by V_1 and repeat the procedure for 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 between X_1, \dots, X_k such that X_i < V_i, X_i < X_j. Then a positive real number d exists such that, if X_i is increased by d, and X_j reduced by d, the product of numbers X_1, \dots, X_k is increased, and all other conditions remain satisfied.


Comments

There are no comments at the moment.