## Wednesday, August 13, 2014

### 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$$.