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

×

CHEFHOME - Editorial

4
2

PROBLEM LINK

Practice
Contest

DIFFICULTY

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

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 36%


Can someone prove the claim made for the 1-D version of the problem?

link

answered 19 Feb '13, 21:29

shubh09's gravatar image

4★shubh09
11717
accept rate: 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.

link

answered 26 Nov '14, 20:50

codejagger's gravatar image

2★codejagger
12
accept rate: 0%

edited 26 Nov '14, 20:54

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.

link

answered 12 Jul '15, 16:36

vastolorde95's gravatar image

5★vastolorde95 ♦
324
accept rate: 11%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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