F家题请教 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

F家题请教

F家题请教# JobHunting - 待字闺中

x*a2014-11-13 08:11

1 楼

网上看的，说是F家的，哪位大侠说说怎么答？
Suppose we are given a set L of n line segments in the plane, where the
endpoints of each segment lie on the unit circle x^2 + y^2 = 1, and all 2n
endpoints are distinct. Describe and analyze an algorithm to compute the
largest subset of L in which no pair of segments intersects

l*82014-11-13 08:11

2 楼

首先把(x,y)坐标转换成极坐标： (1, t), 1是半径，t是角度.
半径都一样，不用关心。每个点用一个角度t来表示就可以了。
每个线段就可以表示成(t1, t2), 让t1 < t2
given两个线段A(a1, a2)和B(b1,b2), a1则A,B相交当且仅当： b1（到了这一步，比较容易判断两条线段是否相交了。但不相交的最大集合，还是没有太
好的算法。。。)
其实，如果把每条线段看成一个node。如果两条线段相交，则两个node之间有边。这样
就得到一个图G。
问题等同于寻找图G的最大独立集(maximum disjoint set), 这是一个np-hard问题。

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

: 网上看的，说是F家的，哪位大侠说说怎么答？
: Suppose we are given a set L of n line segments in the plane, where the
: endpoints of each segment lie on the unit circle x^2 + y^2 = 1, and all 2n
: endpoints are distinct. Describe and analyze an algorithm to compute the
: largest subset of L in which no pair of segments intersects

y*22014-11-13 08:11

3 楼

dp O(n2)或者O(n3)都可以做
注意这道题，线段的2个端点都在单位圆上。我们只要对端点排序。然后，只要x1dp[i][j] = max(1+dp[start+1][end-1] +dp[end+1][j]
for start in range(i+1, j) )

l*82014-11-13 08:11

4 楼

能不能举个例子讲详细点儿。
初始值是什么？计算的顺序是什么？

y1

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

: dp O(n2)或者O(n3)都可以做
: 注意这道题，线段的2个端点都在单位圆上。我们只要对端点排序。然后，只要x1: : dp[i][j] = max(1+dp[start+1][end-1] +dp[end+1][j]
: for start in range(i+1, j) )

T*u2014-11-13 08:11

5 楼

换成角度，就变成一维了。

d*n2014-11-13 08:11

6 楼

可以这样，先算出N条线的斜率，排序找最大重复。Ｏ（ＮｌｏｇＮ)

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

l*82014-11-13 08:11

7 楼

斜率不同也可以不相交

【在 d****n 的大作中提到】

: 可以这样，先算出N条线的斜率，排序找最大重复。Ｏ（ＮｌｏｇＮ)

z*e2014-11-13 08:11

8 楼

LIS 问题，先按照min(p1,p2) 排序，where p1 p2表示线段端点的极坐标的那个角度。
然后就是就是经典的LIS问题了，dp[k] = max(dp[j] + 1) where j < k && seg[k].p2
> seg[j].p2 if seg[k].p1 and seg[j].p1 are selected to sort.复杂度O(n2)

t*l2014-11-13 08:11

9 楼

The direction of your reduction is wrong...

【在 l*********8 的大作中提到】

: 首先把(x,y)坐标转换成极坐标： (1, t), 1是半径，t是角度.
: 半径都一样，不用关心。每个点用一个角度t来表示就可以了。
: 每个线段就可以表示成(t1, t2), 让t1 < t2
: given两个线段A(a1, a2)和B(b1,b2), a1: 则A,B相交当且仅当： b1: （到了这一步，比较容易判断两条线段是否相交了。但不相交的最大集合，还是没有太
: 好的算法。。。)
: 其实，如果把每条线段看成一个node。如果两条线段相交，则两个node之间有边。这样
: 就得到一个图G。
: 问题等同于寻找图G的最大独立集(maximum disjoint set), 这是一个np-hard问题。

d*n2014-11-13 08:11

10 楼

longway2008 was on right track at the beginning:
首先把(x,y)坐标转换成极坐标, 每个点用一个角度t来表示就可以了。每个线段就可
以表示成(t1, t2),
这样一来，　我们可以得到n个区间。将这些区间按t2排序,得到新的数组A。
问题变成从A中找最大的非重叠区间。
设F(i)为第１个区间到第ｉ个区间中的最大不重叠区间个数。
Ｆ（ｉ）＝　Ｍａｘ｛Ｆ（ｉ－１），１＋Ｆ（ｊ）｝，Ａ［ｊ］是１。。。ｉ－１
中结束点ｔ２最接近Ａ［ｉ］的起始点ｔ１并且不要Ａ［ｉ］重叠的区间。　ｊ可以采
用Ｂｉｎａｒｙｓｅａｒｃｈｄｅｄ。
简单ＤＰ，　时间复杂度Ｏ（ｎｌｏｇｎ），空间复杂度Ｏ（ｎ）。

l*82014-11-13 08:11

11 楼

我觉得问题不等同于“从A中找最大的非重叠区间”。
比如线段A是(0.1, 0.5), 线段B是(0.2, 0.3)
看作两个区间的话，是重叠的。但两条线段是不相交的。

【在 d****n 的大作中提到】

: longway2008 was on right track at the beginning:
: 首先把(x,y)坐标转换成极坐标, 每个点用一个角度t来表示就可以了。每个线段就可
: 以表示成(t1, t2),
: 这样一来，　我们可以得到n个区间。将这些区间按t2排序,得到新的数组A。
: 问题变成从A中找最大的非重叠区间。
: 设F(i)为第１个区间到第ｉ个区间中的最大不重叠区间个数。
: Ｆ（ｉ）＝　Ｍａｘ｛Ｆ（ｉ－１），１＋Ｆ（ｊ）｝，Ａ［ｊ］是１。。。ｉ－１
: 中结束点ｔ２最接近Ａ［ｉ］的起始点ｔ１并且不要Ａ［ｉ］重叠的区间。　ｊ可以采
: 用Ｂｉｎａｒｙｓｅａｒｃｈｄｅｄ。
: 简单ＤＰ，　时间复杂度Ｏ（ｎｌｏｇｎ），空间复杂度Ｏ（ｎ）。

l*82014-11-13 08:11

12 楼

如果线段A是(0.1, 0.5), 线段B是(0.2, 0.3)
你的方法的答案包括几条线段？

p2

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

: LIS 问题，先按照min(p1,p2) 排序，where p1 p2表示线段端点的极坐标的那个角度。
: 然后就是就是经典的LIS问题了，dp[k] = max(dp[j] + 1) where j < k && seg[k].p2
: > seg[j].p2 if seg[k].p1 and seg[j].p1 are selected to sort.复杂度O(n2)

d*n2014-11-13 08:11

13 楼

注意这里区间是线段上两点的向心角，如果向心角相交，线段咋可能不相交？

【在 l*********8 的大作中提到】

: 我觉得问题不等同于“从A中找最大的非重叠区间”。
: 比如线段A是(0.1, 0.5), 线段B是(0.2, 0.3)
: 看作两个区间的话，是重叠的。但两条线段是不相交的。

h*s2014-11-13 08:11

14 楼

我理解题意是："n条线段，所有线段的端点都在圆上，找出包含最多不相交线段的集合
。"
计算出所有线段的slope，有n个。
因为2n个点都是distinct的,所以n个线段不会有重叠的，找出不相交的线段最多的集合
，也就是找出同样斜率最多(平行线最多)的集合。如果将n个斜率排序，问题就转化成"
find the most duplicates in a sorted list"
Time: O(nlog(n) + n) --> TO(nlog(n))
Space: O(n) 需要一个array来存slopes，排序也会需要额外的空间，不会超过O(n)
不知道我理解的对不对，大家指正一下。

b*g2014-11-13 08:11

15 楼

是否可以转化成计算最长递增子序列。两个线段A和B不相交的条件是A的左右端点都分
别在B的上方，将所有线段按左端点排序。

成"

【在 h***s 的大作中提到】

: 我理解题意是："n条线段，所有线段的端点都在圆上，找出包含最多不相交线段的集合
: 。"
: 计算出所有线段的slope，有n个。
: 因为2n个点都是distinct的,所以n个线段不会有重叠的，找出不相交的线段最多的集合
: ，也就是找出同样斜率最多(平行线最多)的集合。如果将n个斜率排序，问题就转化成"
: find the most duplicates in a sorted list"
: Time: O(nlog(n) + n) --> TO(nlog(n))
: Space: O(n) 需要一个array来存slopes，排序也会需要额外的空间，不会超过O(n)
: 不知道我理解的对不对，大家指正一下。

g*g2014-11-13 08:11

16 楼

(0, 180) 和(45，135)当然不相交啊

【在 d****n 的大作中提到】

: 注意这里区间是线段上两点的向心角，如果向心角相交，线段咋可能不相交？

z*e2014-11-13 08:11

17 楼

Answer:
0
after sorting
(0.1,0.5) (0.2,0.3)
dp[0] = 0
dp[1] = 0 since endpoint 0: 0.5 larger than endpoint1 : 0.3
So it won't add 1.

【在 l*********8 的大作中提到】

: 如果线段A是(0.1, 0.5), 线段B是(0.2, 0.3)
: 你的方法的答案包括几条线段？
:
: p2

l*82014-11-13 08:11

18 楼

这两条线段是不相交的。所以答案应该是两条线段，不是0条。

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

:
: Answer:
: 0
: after sorting
: (0.1,0.5) (0.2,0.3)
: dp[0] = 0
: dp[1] = 0 since endpoint 0: 0.5 larger than endpoint1 : 0.3
: So it won't add 1.

d*n2014-11-13 08:11

19 楼

这样看来相交可以定义为线段在X轴上的投影相交，并且在Ｙ轴上的投影也相交。

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

: (0, 180) 和(45，135)当然不相交啊

d*n2014-11-13 08:11

20 楼

scratch, it's not right.

【在 d****n 的大作中提到】

: 这样看来相交可以定义为线段在X轴上的投影相交，并且在Ｙ轴上的投影也相交。

e*22014-11-13 08:11

21 楼

我们学校的DP练习题：对所有线段的2个端点分别排序，然后找两个排好续的最大公共
子序列LCS. O(N^2)

e*22014-11-13 08:11

22 楼

这个是对的。LIS， LCS都行，LIS比LCS快。

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

:
: Answer:
: 0
: after sorting
: (0.1,0.5) (0.2,0.3)
: dp[0] = 0
: dp[1] = 0 since endpoint 0: 0.5 larger than endpoint1 : 0.3
: So it won't add 1.

w*t2014-11-13 08:11

23 楼

这里有解答：
http://www.cs.toronto.edu/~robere/csc373h/files/A2-sol.pdf
search "3. Line Intersections (Redux)"