Define the distance between two points i, j max(|xi, xj|, |yi — yj|). Given n points (xi, yi). Find a point (X, Y) so that the sum of distances from this point to n points is minimized.

N <= 1e5

xi, yi <= 1e9

Thanks in advance.

# | User | Rating |
---|---|---|

1 | jiangly | 3678 |

2 | Benq | 3602 |

3 | ecnerwala | 3542 |

4 | maroonrk | 3541 |

5 | cnnfls_csy | 3540 |

6 | orzdevinwang | 3493 |

7 | inaFSTream | 3478 |

8 | Um_nik | 3430 |

9 | Geothermal | 3409 |

9 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 174 |

2 | adamant | 164 |

3 | TheScrasse | 161 |

3 | SecondThread | 161 |

3 | awoo | 161 |

6 | nor | 159 |

7 | maroonrk | 158 |

8 | Um_nik | 156 |

9 | BledDest | 145 |

9 | Geothermal | 145 |

Define the distance between two points i, j max(|xi, xj|, |yi — yj|). Given n points (xi, yi). Find a point (X, Y) so that the sum of distances from this point to n points is minimized.

N <= 1e5

xi, yi <= 1e9

Thanks in advance.

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/22/2024 21:10:21 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by Loserinlife (previous revision, new revision, compare).UPD: I understood the problem incorrectly. Please check the later comments in this thread.

For each point $$$i$$$, let $$$a_i = x_i + y_i$$$ and $$$b_i = x_i - y_i$$$.

Let $$$d(i, j) = max(|x_i - x_j|, |y_i - y_j|)$$$.

Without loss of generality, assume $$$x_i \ge x_j$$$. Now $$$|x_i - x_j| = x_i - x_j$$$. And

$$$d(i, j) = max(|x_i - x_j|, |y_i - y_j|)$$$

$$$d(i, j) = max(x_i - x_j, |y_i - y_j|)$$$.

$$$\displaystyle d(i, j) = \frac{x_i - x_j + |y_i - y_j| + |x_i - x_j - |y_i - y_j||}{2}$$$ (According to this)

$$$2\cdot d(i, j) = x_i - x_j + |y_i - y_j| + |x_i - x_j - |y_i - y_j||$$$

Case 1: $$$y_i \ge y_j$$$

$$$2\cdot d(i, j) = x_i - x_j + y_i - y_j + |x_i - x_j - y_i + y_j|$$$

$$$2\cdot d(i, j) = x_i + y_i - x_j - y_j + |x_i - y_i - x_j + y_j|$$$

$$$2\cdot d(i, j) = a_i - a_j + |b_i - b_j|$$$

Because $$$x_i \ge x_j$$$ and $$$y_i \ge y_j$$$ are assumed,

$$$a_i \ge a_j$$$ must be true.

$$$2\cdot d(i, j) = |a_i - a_j| + |b_i - b_j|$$$

$$$\displaystyle d(i, j) = \frac{|a_i - a_j| + |b_i - b_j|}{2}$$$

Case 2: $$$y_i < y_j$$$

$$$2\cdot d(i, j) = x_i - x_j + (- y_i + y_j) + |x_i - x_j - (- y_i + y_j)|$$$

$$$2\cdot d(i, j) = x_i - x_j - y_i + y_j + |x_i - x_j + y_i - y_j|$$$

$$$2\cdot d(i, j) = x_i - y_i - x_j + y_j + |x_i + y_i - x_j - y_j|$$$

$$$2\cdot d(i, j) = b_i - b_j + |a_i - a_j|$$$

Because $$$x_i \ge x_j$$$ and $$$y_i < y_j \Leftrightarrow -y_i > y_j$$$ are assumed,

$$$x_i - y_i > x_j - y_j$$$

$$$b_i > b_j$$$ must be true.

$$$2\cdot d(i, j) = |b_i - b_j| + |a_i - a_j|$$$

$$$\displaystyle d(i, j) = \frac{|b_i - b_j| + |a_i - a_j|}{2}$$$

We can see that in both cases, $$$\displaystyle d(i, j) = \frac{|a_i - a_j| + |b_i - b_j|}{2}$$$.

This is equal to the manhattan distance of points $$$(a_i, b_i)$$$ and $$$(a_j, b_j)$$$ divided by two. For implementation, we can actually forget about the "divided by two" part, since that just scales everything by a constant and doesn't affect which distances are larger than others.

Now the problem is to find the minimum sum of manhattan distances for each point. Manhattan distances for each coordinate are independent of each other and thus they can be calculated independently.

Let's consider some fixed point $$$i$$$ and the sum of distance differences of the $$$a$$$-coordinates:

$$$\displaystyle\sum_{j = 1}^n |a_i - a_j|$$$

$$$ = \displaystyle\sum_{a_j \le a_j} (a_i - a_j) + \displaystyle\sum_{a_j > a_j} (a_j - a_i)$$$

$$$ = \displaystyle\sum_{a_j \le a_j} a_i - \displaystyle\sum_{a_j \le a_j} a_j + \displaystyle\sum_{a_j > a_j} a_j - \displaystyle\sum_{a_j > a_j} a_i$$$

$$$ = [\text{count of } j \text{: } a_j \le a_i] \cdot a_i - \displaystyle\sum_{a_j \le a_j} a_j + \displaystyle\sum_{a_j > a_j} a_j - [\text{count of } j \text{: } a_j > a_i] \cdot a_i$$$

$$$ = \displaystyle\sum_{a_j > a_j} a_j - \displaystyle\sum_{a_j \le a_j} a_j + [\text{count of } j \text{: } a_j \le a_i] \cdot a_i - [\text{count of } j \text{: } a_j > a_i] \cdot a_i$$$

The first and second terms are just prefix/suffix sums on the sorted array of all $$$a$$$-coordinates which can either be precalculated or calculated during iteration of the array. The last two terms can be calculated in $$$O(1)$$$ based the position of point $$$i$$$ in the sorted array of all $$$a$$$-coordinates. Thus, these values can be calculated for all points $$$i$$$ in $$$O(n \log n)$$$ (due to sorting the points). Now, we can do the same for all $$$b$$$-coordinates and calculate the sum of differences of those. The total manhattan distance, which is equal to twice the original distance, is now the sum of these two sums of differences. Now we can find the minimum total distance in $$$O(n)$$$.

Woah, the transformation is really cool! Tysm.

But for the original problem, point (X, Y) can be any point. So the point would be the median of array A and B respectively, right?

If we were only considering array $$$a$$$, the optimal one would be the median. Same for array $$$b$$$. But the distance function is the sum of the differences to all values in both arrays. The optimal point is not nescessarily the median of array $$$a$$$ or $$$b$$$, it's the one with the smallest sum of the sums of differences in array $$$a$$$ and $$$b$$$. I can give you an example in a moment.

UPD: Example

Consider three points given in input: $$$(x_1, y_1) = (1, 4)$$$, $$$(x_2, y_2) = (6, 8)$$$ and $$$(x_3, y_3) = (6, 0)$$$.

These points get transformed into $$$(a_1, b_1) = (5, -3)$$$, $$$(a_2, b_2) = (14, -2)$$$ and $$$(a_3, b_3) = (6, 6)$$$.

Sorting these points according to their $$$a$$$-coordinate will lead to the following:

Sorting these points according to their $$$b$$$-coordinate will lead to the following:

Sum of distances for both coordinates:

We can see that while point $$$2$$$ was the median when sorting $$$a$$$-distances and point $$$3$$$ was the median when sorting $$$b$$$-distances, point $$$1$$$ still has the lowest total sum of distances. This shows that we need to calculate the sum of $$$a$$$-distances and the sum of $$$b$$$-distances for every point and take the one with the smallest sum.

And if you want to confirm that this method works, we can check the distances using the metric mentioned in the problem statement.

Distance between $$$1$$$ and $$$2$$$: $$$\max(|1 - 6|, |4 - 8|) = \max(5, 4) = 5$$$

Distance between $$$1$$$ and $$$3$$$: $$$\max(|1 - 6|, |4 - 0|) = \max(5, 4) = 5$$$

Distance between $$$2$$$ and $$$3$$$: $$$\max(|6 - 6|, |8 - 0|) = \max(0, 8) = 8$$$

Thus, the distance from $$$1$$$ to everywhere is $$$5 + 5 = 10$$$

The distance from $$$2$$$ to everywhere is $$$5 + 8 = 13$$$

The distance from $$$3$$$ to everywhere is $$$5 + 8 = 13$$$

All of these values are exactly $$$\frac{1}{2}$$$ of the manhattan distances on the transformed points as expected.

I think for your example, Point (6, -2) should be optimal.

Sorry for not making it clear but the point chosen doesn't have to be in the N initial point.

The original problem is here: https://oj.vnoi.info/problem/icpc21_beta_k

Oh, I see. And I think what you said previously —

"So the point would be the median of array A and B respectively"— should be correct.Well a weird thing is that is isn't :((.

Can you take a quick look at this code.

https://ideone.com/e0m9Bh

I may have misunderstood the problem so I will try your approach when I get home.

Ah, I think I found something. It's not a bug in your code, it's a mistake in the method.

Since the people always move from integer coodrinates to integer coordinates, it is implied that the vaccination station must have integer coordinates. Consider the case

Your code outputs $$$2$$$, but that is only possible with the point $$$(0.5, 0.5)$$$. This is not allowed and thus, the answer would be $$$3$$$.

UPD: I guess the solution would be something like this (but I'm not at all sure if this is correct, this is just by intuition):

Start by choosing the median point as the answer. Let the point be called $$$(x, y)$$$ (note that we are in the transformed coordinate system). This point can be directly translated back with integer coordinates iff $$$x \equiv y \pmod 2$$$. If this is true, we are done.

If $$$x \neq y \pmod 2$$$, we can try points $$$(x+1, y)$$$, $$$(x-1, y)$$$, $$$(x, y+1)$$$ and $$$(x, y-1)$$$. The best one of these should(?) be the answer.

https://ideone.com/8h3IJ1

I just try neighboring points to the median and that AC! :) Thanks so much for the help.

Oh wait, I just realize you already mentioned it. Oops :)

Nice. I just updated my previous comment since I got the same idea but it seems like you were faster.

I get really confused about when to take the median and when to take the average when we have to minimize distance. Can you please clarify?

Suppose you have a set of points on a 1-dimensional line. They don't have to be at integer coordinates.

If you need to choose a point that minimizes the

maximum distanceto any other point, the answer is theaverage of the smallest and largest points. This should be intuitively true and not too hard to prove.If you need to choose a point that minimizes the

sum of distancesto all other point, the answer is themedian of all points. This is not nescessarily intuitive and it is harder to prove, but not too difficult.Note that both of these are always true if the distance function is the standard, i.e. $$$d(i, j) = |i - j|$$$. If the distance function is something else, these do not nescessarily apply.

Thank you. FInally got it.