code_stacker's blog

By code_stacker, history, 6 weeks ago, In English

Try solving for some p q r (sorted order). Think of them as points on the coordinate axis. What's the problem asking you to do? It's about finding a point such that sum of absolute differences between each pair of points is minimized. If you choose q to be that point, the answer is (q — p) + (r — q) + (q — q). If you choose some other point, let's say q + x for any value x, then the answer is ((q + x) — p) + (r — (q + x)) + (q + x — q) == (q — p) + (r — q) + x. Hence, the optimal point must be q.

Try solving for some case p q r s and notice that any value x satisfying q <= x <= r works. After solving these two cases, it's easy to show that median works.

Case 1: if n is odd arr {p,q,r,s,t} smallest summary distance = (s+t)-(p+q) Case 2: if n is even arr {p,q,r,s} smallest summary distance = (s+t)-(p+q) //can take any point from [q,r] all give same and min summary distance

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by code_stacker (previous revision, new revision, compare).

»
6 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

You are trying to minimize $$$f(x) = |x-a_1|+|x-a_2|+...+|x-a_n|$$$

Consider $$$f'(x) = \frac{x-a_1}{|x-a_1|}+\frac{x-a_2}{|x-a_2|}+...+\frac{x-a_n}{|x-a_n|}$$$

Using calculus, $$$f(x)$$$ is minimized at $$$x=x^*$$$, where $$$f'(x^*)=0$$$

Solving for $$$f'(x^*)=0$$$ we get $$$x^*=a_\frac{n}{2}$$$ if $$$n$$$ is ODD and $$$x=\frac{1}{2}(a_\frac{n}{2}+a_{\frac{n}{2}+1})$$$ if $$$n$$$ is EVEN.

This is exactly the definition of median of {$$$a_i$$$}$$$_{i=1}^n$$$

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by code_stacker (previous revision, new revision, compare).