## Editorial for SAC '22 Code Challenge 4 P3 - Obligatory Math Problem

**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.**

Authors:

,##### Subtask 1

It suffices to iterate over all possible minimizing values and determine the minimizing one.

**Time Complexity:**

##### Subtask 2

Realize that the sum of convex functions is convex.

Now, binary search for the minimizing point, , by comparing the result from using compared to :

- If 's result is smaller than 's, constrain the search to the left of .
- If 's result is smaller than 's, constrain the search to the right of .

Finally, output the minimizing value.

##### Alternative Solution

Note that the median of the array is always a minimizing value.

Consider what happens to the sum of when we increase by one (i.e., let ). Then, each greater than or equal to contributes to the change in the sum while each less than contributes to the change in the sum, so the change in this sum equals [number of elements less than ] minus [number of elements greater than or equal to ]. As , this change slowly goes from negative to positive; we wish to stop when this change becomes positive, that is, when the number of elements less than is greater than or equal to the number of elements greater than or equal to . This happens at the median.

## Comments