Contest Duration: - (local time) (100 minutes) Back to Home
Official

## E - Average and Median Editorial by en_translator

The common approach to maximization of average or median is to boil it down to the predicate of “does the answer exceed $$K$$?” and find the answer by binary search.

### Does the average exceed $$K$$?

“The average of $$x_1, \dots, x_n$$ is greater than $$K$$ $$\Leftrightarrow$$ $$(x_1 - K) + \dots + (x_n - K)$$ is more than $$0$$,” so, defining $$B_i = A_i - K$$, it is sufficient to check if the maximum sum of $$B_i$$ corresponding to the chosen cards is greater than $$0$$.

### Does the median exceed $$K$$?

“The median of $$x_1, \dots, x_n$$ is greater than $$K$$ $$\Leftrightarrow$$ the number of elements greater than $$K$$ in $$x_i$$ is greater than the number of elements less than or equal to $$K$$,” so, defining $$B_i = 1$$ if $$A_i \ge K$$ or otherwise $$B_i = -1$$, it is sufficient to check if the maximum sum of $$B_I$$ corresponding to the chosen cards is positive.

### Maximization of sum of $$B_i$$

In order to evaluate the above-mentioned predicates, we need to find the maximum sum of $$B_I$$ corresponding to the chosen cards. This can be computed with the following Dynamic Programming (DP).

• $$f_k :=$$ the maximum sum of $$B_i$$ when the cards are chosen from the first $$k$$ elements so that the $$k$$-th card is chosen
• $$g_k :=$$ the maximum sum of $$B_i$$ when the cards are chosen from the first $$k$$ elements so that the $$k$$-th card is not chosen

Let $$f_0 \leftarrow 0, g_0 \leftarrow 0$$, and compute $$f_k \leftarrow \max(f_{k - 1}, g_{k - 1}) + B_k, g_k \leftarrow f_{k - 1}$$ in the increasing order of $$k$$. Thus the predicate can be evaluated in an $$O(N)$$ time.

### Handling precision errors

The average is not necessarily an integer, so it is difficult to find the precise value. In this problem, the output is considered to be a correct solution if the relative or absolute error from the true value is at most $$10^{-3}$$, so we ca use the following ways.

• Multiply each $$A_i$$ by $$10^3$$ and find the maximum integer such that the average may exceed $$K$$. Output $$10^{-3} K$$. Sample code (C++)
• Let $$l$$ be the lower bound, and $$h$$ be the upper bound, of the binary search. Continue binary search while $$\frac{h - l}{h} > 10^{-3}$$. After the search ends, output $$l$$. Sample code (C++)
• Note 1. In this problem, the average is always at least $$1$$, so we can assume that $$l \geq 1$$. Therefore, the relative error is always less than the absolute error.
• Note 2. Generally, in binary search we let $$m = \frac{l + h}{2}$$ and evaluate the predicate for $$K = m$$. However, as in this problem, if the answer is always greater than or equal to $$1$$, and the objective is to reduce the relative error below a threshold, then using $$m = \frac{l + h}{2}$$ requires less worst iterations. This can be understood by considering minimizing $$\max(\frac{x - l}{x}, \frac{h - x}{h})$$.

posted:
last update: