空中漫步 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

空中漫步

空中漫步# Joke - 肚皮舞运动

e*x2012-05-28 07:05

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点中间选就简单了，但这题还是搞不定啊~

f*e2012-05-28 07:05

2 楼

p*g2012-05-28 07:05

3 楼

where is the online test?
link please
Thanks.

H*g2012-05-28 07:05

4 楼

这个厉害

p*22012-05-28 07:05

5 楼

又在做上边的题呀？

e*x2012-05-28 07:05

6 楼

https://www.interviewstreet.com/challenges/dashboard/#problem/4e14b2cc47f78

【在 p*g 的大作中提到】

: where is the online test?
: link please
: Thanks.

e*x2012-05-28 07:05

7 楼

恩，蛋疼的。

【在 p*****2 的大作中提到】

: 又在做上边的题呀？

p*22012-05-28 07:05

8 楼

牛。

【在 e******x 的大作中提到】

: 恩，蛋疼的。

f*e2012-05-28 07:05

9 楼

和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*x2012-05-28 07:05

10 楼

恩，可是不一定正确吧，怎样能保证一定找到最优点呢？

【在 f*****e 的大作中提到】

: 和clustering有点像，heuristic就是先求重心，然后求离重心最近的一点。

d*s2012-05-28 07:05

11 楼

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*g2012-05-28 07:05

12 楼

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*x2012-05-28 07:05

13 楼

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
: .