You are not logged in. Please login at www.codechef.com to post your questions!

×

MEDIUM

# EXPLANATION

First try to solve the 1-D version. You have N integer points marked on a number line, the point(s) that minimze the sum of the distances from all the points lie between the median points. In case, N is even, there are two median points. For example,for N = 4, and points {2,3,5,6} , we can easily calculate that {3,4,5} are the integer points that will minimize the sum of distances from all the other points in {2,3,5,6}.

We can extend this to the 2-D version. First thing to realize is that we can treat X and the Y coordinates independently of each other. Let A be the answer to solve the 1-D version on X coordinates. Let B be the answer to solve the 1-D version on Y coordinates. The final answer is simple A*B.

# SETTER'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 09 Nov '12, 15:51 19.8k350498541
accept rate: 36%

 2 Can someone prove the claim made for the 1-D version of the problem? answered 19 Feb '13, 21:29 4★shubh09 117●1●7 accept rate: 0%
 0 median has equal number of numbers on both of its side. so lets say x is your median point for n points. Moving it to left means subtracting n/2 from the sum at x. However you have made the point far from the right side n/2 points. So you add n/2 again. Plus it's possible that now more points exist in the right side. For example rrrxrrr. moving x to left means rrrxrrrr. As you see, now you are adding more to the optimal sum and subtracting less. It is clear why x is the optimal place to choose now. answered 26 Nov '14, 20:50 1●2 accept rate: 0%
 0 Proof for 1-D version. Let us consider an arbitrary point X. Let there be L number of points to the left of point X and R number of points to the right of X. Now, if L > R, let us move our point X one step to the left at X-1. Our new sum of distances will be oldsum + R - L. Note that R-L is < 0 so the new sum of distances < oldsum. So as long as there are more points to the left of our current point than on the right, we can keep moving left and decrease our sum. The same logic can be applied when R > L. This will continue till R == L. The point where the number of points to the left is the same as the number of points to the right is called the median. Hence Proved. answered 12 Jul '15, 16:36 32●4 accept rate: 11%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,655
×20
×4

question asked: 09 Nov '12, 15:51

question was seen: 2,011 times

last updated: 12 Jul '15, 16:36