Guide to Competitive Programming

Suppose that there is a function f (x) that first only decreases, then attains its minimum value, and then only increases. For example, Such a function whose minimum value is marked with an arrow. If we know that our function has this property, we can efficiently find its minimum value.

Ternary Search:

Ternary search provides an efficient way to find the minimum value of a function that first decreases and then increases. Assume that we know that the value of x that minimizes f (x) is in a range [xL , xR]. The idea is to divide the range into three equal-size parts [xL , a], [a, b], and [b, xR] by choosing

Ternary search

Then, if f (a) < f (b), we conclude that the minimum must be in range [xL , b], and otherwise it must be in range [a, xR]. After this, we recursively continue the search, until the size of the active range is small enough.
As an example, The first step of ternary search in our example scenario. Since f (a) > f (b), the new range becomes [a, xR].

Searching for the minimum using ternary search

In practice, we often consider functions whose parameters are integers, and the search is terminated when the range only contains one element. Since the size of the new range is always 2/3 of the previous range, the algorithm works in O(log n) time, where n is the number of elements in the original range.

Note that when working with integer parameters, we can also use binary search instead of ternary search, because it suffices to find the first position x for which f (x) ≤ f (x + 1).

Convex Functions:

A function is convex if a line segment between any two points on the graph of the function always lies above or on the graph. For example, the graph of f (x) = x2, which is a convex function. Indeed, the line segment between points a
and b lies above the graph.
If we know that the minimum value of a convex function is in range [xL , xR], we can use ternary search to find it.

However, note that several points of a convex function may have the minimum value. For example, f (x) = 0 is convex and its minimum value is 0.
Convex functions have some useful properties: if f (x) and g(x) are convex functions, then also f (x)+g(x) and max( f (x), g(x)) are convex functions. For example, if we have n convex functions f1, f2, . . . , fn, we immediately know that also the function f1 + f2 + . . . + fn has to be convex and we can use ternary search to find
its minimum value.

Minimizing Sums:

Given n numbers a1, a2, . . . , an, consider the problem of finding a value of x that minimizes the sum |a1 − x| + |a2 − x|+· · ·+|an − x|.
For example, if the numbers are [1, 2, 9, 2, 6], the optimal solution is to choose x = 2, which produces the sum
|1 − 2| + |2 − 2| + |9 − 2| + |2 − 2| + |6 − 2| = 12.

Since each function |ak − x| is convex, the sum is also convex, so we could use ternary search to find the optimal value of x. However, there is also an easier solution. It turns out that the optimal choice for x is always the median of the numbers, i.e., the middle element after sorting. For example, the list [1, 2, 9, 2, 6] becomes [1, 2, 2, 6, 9] after sorting, so the median is 2.

The median is always optimal, because if x is smaller than the median, the sum becomes smaller by increasing x, and if x is larger then the median, the sum becomes smaller by decreasing x. If n is even and there are two medians, both medians and all values between them are optimal choices.

Then, consider the problem of minimizing the function (a1 − x)2 + (a2 − x)2 +· · ·+(an − x)2.
For example, if the numbers are [1, 2, 9, 2, 6], the best solution is to choose x = 4, which produces the sum (1 − 4)2 + (2 − 4)2 + (9 − 4)2 + (2 − 4)2 + (6 − 4)2 = 46. Again, this function is convex and we could use ternary search to solve the problem, but there is also a simple solution: the optimal choice for x is the average of the numbers. In the example the average is (1 + 2 + 9 + 2 + 6)/5 = 4. This can be proved by presenting the sum as follows:

nx2 − 2x(a1 + a2 + ·· ·+an) + (a2
1
+ a2
2
+· · ·+a2
n )

The last part does not depend on x, so we can ignore it. The remaining parts form a function nx2 − 2xs where s = a1 + a2 + ·· · + an. This is a parabola opening upwards with roots x = 0 and x = 2s/n, and the minimum value is the average of the roots x = s/n, i.e., the average of the numbers a1, a2, . . . , an.