e******x
发帖数: 184 | 1 不知道有没有人做过这道题，题目如下
There is an infinite integer grid at which N people have their houses on.
They decide to unite at a common meeting place, which is someone's house.
From any given cell, all 8 adjacent cells are reachable in 1 unit of time.
eg: (x,y) can be reached from (x-1,y+1) in a single unit of time.
Find a common meeting place which minimises the sum of the travel times of
all the persons.
O(n^2)的解法只能过4个case，不知道怎么优化成O(n)...
我知道Manhattan distance可以转化成|x1-x2|+|y1-y2|的形式，这样如果所求点不需
要在这N点中间选就简单了，但这题还是搞不定啊~ |
p*g
发帖数: 141 | 2 where is the online test?
link please
Thanks. |
p*****2
发帖数: 21240 | |
e******x
发帖数: 184 | |
e******x
发帖数: 184 | 5 恩，蛋疼的。
【在 p*****2 的大作中提到】
: 又在做上边的题呀？
|
p*****2
发帖数: 21240 | 6
牛。
【在 e******x 的大作中提到】
: 恩，蛋疼的。
|
f*****e
发帖数: 2992 | 7 和clustering有点像，heuristic就是先求重心，然后求离重心最近的一点。
【在 e******x 的大作中提到】
: 不知道有没有人做过这道题，题目如下
: There is an infinite integer grid at which N people have their houses on.
: They decide to unite at a common meeting place, which is someone's house.
: From any given cell, all 8 adjacent cells are reachable in 1 unit of time.
: eg: (x,y) can be reached from (x-1,y+1) in a single unit of time.
: Find a common meeting place which minimises the sum of the travel times of
: all the persons.
: O(n^2)的解法只能过4个case，不知道怎么优化成O(n)...
: 我知道Manhattan distance可以转化成|x1-x2|+|y1-y2|的形式，这样如果所求点不需
: 要在这N点中间选就简单了，但这题还是搞不定啊~
|
e******x
发帖数: 184 | 8 恩，可是不一定正确吧，怎样能保证一定找到最优点呢？
【在 f*****e 的大作中提到】
: 和clustering有点像，heuristic就是先求重心，然后求离重心最近的一点。
|
d*s
发帖数: 699 | 9 I cannot see a O(n) method here. Since the distance is evaluated as max(|x_i
-x_j|,|y_i-y_j|)，the distance matrix is symmmetric and only need to
calculate a upper triangle of size N. With an OK computer N can easily be as
large as 10^4, isn't it enough?
Plus if you don't build the matrix explicitly and only keep a working array
and the minimum index, N should be able to reach 10^10-11 without an issue.
Why O(n) is a must? |
p*g
发帖数: 141 | 10 what is your point?
A solution better than O(n^2) is highly desirable, but I thought
about it a bit, seems not that trival
check this
http://en.wikipedia.org/wiki/Geometric_median
_i
as
array
.
【在 d*s 的大作中提到】
: I cannot see a O(n) method here. Since the distance is evaluated as max(|x_i
: -x_j|,|y_i-y_j|)，the distance matrix is symmmetric and only need to
: calculate a upper triangle of size N. With an OK computer N can easily be as
: large as 10^4, isn't it enough?
: Plus if you don't build the matrix explicitly and only keep a working array
: and the minimum index, N should be able to reach 10^10-11 without an issue.
: Why O(n) is a must?
|
e******x
发帖数: 184 | 11 Thanks for the wiki link~ Read it for a while. Thought "procedures that
decrease the sum of distances at each step cannot get trapped in a local
optimum" might help.
I finally made it by sorting the points by decreasing the distance to the
centroid of the points, then computing the sum until the next sum is bigger.
Have no idea if it's definitely correct, but it passed all the test cases...
【在 p*g 的大作中提到】
: what is your point?
: A solution better than O(n^2) is highly desirable, but I thought
: about it a bit, seems not that trival
: check this
: http://en.wikipedia.org/wiki/Geometric_median
:
: _i
: as
: array
: .
|
c*******f
发帖数: 85 | 12 chebyshev distance ->(rotate 45')-> manhhattan distance |
