k***e
发帖数: 556 | 1 上次发了一题，没人理，继续。这两题都是来自职业杯。
1。Given a set of n points, find the line that intersects the most number of
points
想不出有比n^2更好的办法
2。Given n integers, find two of them that has max xor result
如果假定a xor b takes time len(a)+len(b)), then the naive way will take time
n^2 * avglen
my idea: first align all the numbers to same length, say it is x, then
distribute by most significant bit, as 1, 0, to two array one and zero. we
will keep dividing one into oneone, onezero, zero into zerozero, zeroone.
then to ac | H*M
发帖数: 1268 | 2 这第二题，geniusxsy给过一个算法，cnvert成bit的bst的
你找找
of
time
【在 k***e 的大作中提到】
: 上次发了一题，没人理，继续。这两题都是来自职业杯。
: 1。Given a set of n points, find the line that intersects the most number of
: points
: 想不出有比n^2更好的办法
: 2。Given n integers, find two of them that has max xor result
: 如果假定a xor b takes time len(a)+len(b)), then the naive way will take time
: n^2 * avglen
: my idea: first align all the numbers to same length, say it is x, then
: distribute by most significant bit, as 1, 0, to two array one and zero. we
: will keep dividing one into oneone, onezero, zero into zerozero, zeroone.
| k***e
发帖数: 556 | 3 汗啊 geniusxsy成了终极索引
恩 我猜是trie而不是bst 更准确的说 是用 radix tree
用时仅 n * avglenth
it is better than my method.
【在 H*M 的大作中提到】
: 这第二题，geniusxsy给过一个算法，cnvert成bit的bst的
: 你找找
:
: of
: time
| H*M
发帖数: 1268 | 4 是。确切地说不是bst,跟trie比较象吧，每个leaf代表一个数
【在 k***e 的大作中提到】
: 汗啊 geniusxsy成了终极索引
: 恩 我猜是trie而不是bst 更准确的说 是用 radix tree
: 用时仅 n * avglenth
: it is better than my method.
| H*M
发帖数: 1268 | 5 第一题你的n^2用额外空间否
of
time
【在 k***e 的大作中提到】
: 上次发了一题，没人理，继续。这两题都是来自职业杯。
: 1。Given a set of n points, find the line that intersects the most number of
: points
: 想不出有比n^2更好的办法
: 2。Given n integers, find two of them that has max xor result
: 如果假定a xor b takes time len(a)+len(b)), then the naive way will take time
: n^2 * avglen
: my idea: first align all the numbers to same length, say it is x, then
: distribute by most significant bit, as 1, 0, to two array one and zero. we
: will keep dividing one into oneone, onezero, zero into zerozero, zeroone.
| g*******y
发帖数: 1930 | 6 hehe, I just meant binary tree, not really a BST~
【在 k***e 的大作中提到】
: 汗啊 geniusxsy成了终极索引
: 恩 我猜是trie而不是bst 更准确的说 是用 radix tree
: 用时仅 n * avglenth
: it is better than my method.
| g*******y
发帖数: 1930 | 7 the first one I can't get better than O(nn) either
However, even for the O(nn) solution, I find this one is more tricky than it
seems to be, in the way how you handle precission&overflow issue
【在 H*M 的大作中提到】
: 第一题你的n^2用额外空间否
:
: of
: time
| H*M
发帖数: 1268 | 8 你意思是在算斜率的时候，如果垂直的话，需要特殊handle？
不过这个precision是比较不好handle啊。假如两个斜率非常接近，在计算机的precisi
on里是一样的了，但是却又不是一条线的，你怎么弄？
难道要记下分子分母，看最后能不能reduce成相同？
it
【在 g*******y 的大作中提到】
: the first one I can't get better than O(nn) either
: However, even for the O(nn) solution, I find this one is more tricky than it
: seems to be, in the way how you handle precission&overflow issue
| k***e
发帖数: 556 | 9 可以先把这种特殊的挑出来单独做
如果假设所有点都是整点，那么斜率和x axis上的交点都是有理数 用这个来刻画直线
用hash一样可以解决
ps，float好像用hash是会有精度等各种问题，有谁试过？
你意思是在算斜率的时候，如果垂直的话，需要特殊handle？
不过这个precision是比较不好handle啊。假如两个斜率非常接近，在计算机的precisi
on里是一样的了，但是却又不是一条线的，你怎么弄？
it
【在 H*M 的大作中提到】
: 你意思是在算斜率的时候，如果垂直的话，需要特殊handle？
: 不过这个precision是比较不好handle啊。假如两个斜率非常接近，在计算机的precisi
: on里是一样的了，但是却又不是一条线的，你怎么弄？
: 难道要记下分子分母，看最后能不能reduce成相同？
:
: it
| g*******y
发帖数: 1930 | 10 用斜率来定err不好，应该用角度
比如说斜率0.1 和 0.2显然是两条不同的直线，而斜率9999999999.1和斜率9999999999
.2基本上可以算作是同一条直线。
其实就是因为tan函数的非线性性。
假设我们认为角度在某个范围（比如+/-0.05rad）之内算是同一角度的话，这样很容易
能解决掉OF的问题，i.e.，算一个tan89.5degree，然后假设这个就是OF的threshold，
用跟判定OF同样的方法就可以确定是否一条直线能被算做是90度。
还有个问题，
这样简单的划分格子-0.05~0.05rad一格，0.05~0.15rad一格，是不严密的，假设很多数据点在0.049,很多数据点在0.051，它们都应该被算作是同一角度同一直线，但是因为落在了两个不同的相邻格子而被算成是不同的角度。
这个问题也不是很难解决。
那么再看看，这个问题对于90度附近的数据又怎么处理? 这个时候你不能笼统的把89.5跟89.9999看成是一个角度了，这个时候你怎么办？
接下来还有更大的麻烦，如果以A点为轴心，假设B,C点非常非常近，BC垂直AB，还有一个点D，D在大概AB线段一半的
【在 k***e 的大作中提到】
: 可以先把这种特殊的挑出来单独做
: 如果假设所有点都是整点，那么斜率和x axis上的交点都是有理数 用这个来刻画直线
: 用hash一样可以解决
: ps，float好像用hash是会有精度等各种问题，有谁试过？
:
: 你意思是在算斜率的时候，如果垂直的话，需要特殊handle？
: 不过这个precision是比较不好handle啊。假如两个斜率非常接近，在计算机的precisi
: on里是一样的了，但是却又不是一条线的，你怎么弄？
: it
| | | b****j
发帖数: 78 | 11 请教第一题如何O(n^2)？
of
time
【在 k***e 的大作中提到】
: 上次发了一题，没人理，继续。这两题都是来自职业杯。
: 1。Given a set of n points, find the line that intersects the most number of
: points
: 想不出有比n^2更好的办法
: 2。Given n integers, find two of them that has max xor result
: 如果假定a xor b takes time len(a)+len(b)), then the naive way will take time
: n^2 * avglen
: my idea: first align all the numbers to same length, say it is x, then
: distribute by most significant bit, as 1, 0, to two array one and zero. we
: will keep dividing one into oneone, onezero, zero into zerozero, zeroone.
| m*****f
发帖数: 1243 | 12 第一题， 在职业杯自己给出的solution, 是O(n^3)....
怎么做O(n^2)的? | b****j
发帖数: 78 | 13 什么是职业杯啊？
【在 m*****f 的大作中提到】
: 第一题， 在职业杯自己给出的solution, 是O(n^3)....
: 怎么做O(n^2)的?
| g*******y
发帖数: 1930 | 14 职业杯自己的solution只能做参考吧，有不少错误或者非最优答案。。。
【在 m*****f 的大作中提到】
: 第一题， 在职业杯自己给出的solution, 是O(n^3)....
: 怎么做O(n^2)的?
| a******t
发帖数: 34 | 15 if one number goes to 0 path, then the other should go to the 1 path at each
level. but is it easy to implement? recursive? can you post the code?
thanks.
【在 g*******y 的大作中提到】
: hehe, I just meant binary tree, not really a BST~
| B*****t
发帖数: 335 | 16 第一题有很多方法。不过好于O(N^2)的方法还没有想到。谁有兴趣的话可以试试用
HoughTransform来证明它是最优的。
1. O(N^3)的方法比较显然。好一点的方法可以以每个点为起点，求出其它点到这个点
的角度，并进行排序。 复杂度为O(N^2logN)。这个方法优点是可以处理点坐标为有理
数的情况。
2.考虑整数点的情况，对每个点，求出以该点为起点的向量(Vx, Vy)，注意要化简称Vx
，Vy互质且Vx>0的状态。再对(Vx, Vy)用hash或者直接搞个二位数组也可以，剩下的就
是计数了。算法复杂度为O(N^2)，这样就避免了精度问题。
precisi
【在 k***e 的大作中提到】
: 可以先把这种特殊的挑出来单独做
: 如果假设所有点都是整点，那么斜率和x axis上的交点都是有理数 用这个来刻画直线
: 用hash一样可以解决
: ps，float好像用hash是会有精度等各种问题，有谁试过？
:
: 你意思是在算斜率的时候，如果垂直的话，需要特殊handle？
: 不过这个precision是比较不好handle啊。假如两个斜率非常接近，在计算机的precisi
: on里是一样的了，但是却又不是一条线的，你怎么弄？
: it
|
|
