a bit of srm: Minimizing Absolute Values - SRM 629 Div II 550

Problem Statement:

Given $M = \sum^{n}_{i=1} |a_ix - b_i|$, find $x$ that minimizes $M$.

The solution to the problem hinges on the following lemma:

Lemma 1:

If $x$ minimizes M, then $x \in \{ \frac{b_1}{a_1}, \frac{b_2}{a_2}, \ldots , \frac{b_n}{a_n} \}$. 

Proof:

The proof comes from an observation that the curve for M is made up of segments of straight lines with sharp turns on each $x \in \{ \frac{b_1}{a_1}, \frac{b_2}{a_2}, \ldots , \frac{b_n}{a_n} \}$. Why? Let's assume without losing generality that $\{ \frac{b_1}{a_1}, \frac{b_2}{a_2}, \ldots , \frac{b_n}{a_n} \}$ is sorted in increasing order. Each $(\frac{b_k}{a_k}, \frac{b_{k+1}}{a_{k+1}})$ forms a segment on the real number line, and $x$ can only be one of the segment at any point of time. In any segment, each $a_ix - b_i$ will be either positive or negative and the parity will not change as long as $x$ stays in the same segment. This means that in each segment, $M = Ax - B$, which is a straight line. From here it is clear that if $x$ minimizes M, it cannot be in the middle of the line segment, since moving along the downward slope will gives us even smaller M. Hence $x$ must be on the segment ends, and hence leads to Lemma 1.

From here, we can perform a $O(N^2)$ complete search to find $x$.