想申个citi的卡，哪个比较好？# Money - 海外理财
x*p
1 楼
平面上有随机2000个点，其中1000蓝点，1000红点。但任何三点都不同线。
要求寻找一种算法，生成1000条互不相交的连接蓝点和红点的线段。换句话说，让任何
蓝点去连接任何
红点，但各不相交。
要求寻找一种算法，生成1000条互不相交的连接蓝点和红点的线段。换句话说，让任何
蓝点去连接任何
红点，但各不相交。
m*n
2 楼
Dividend Platinum 或者Forward？
或者其他？
或者其他？
x*p
3 楼
没人来做啊。自己顶一下。
T*0
4 楼
第一张申了Dividend，除了容易Pass+CL比较高，感觉一般，Cashback基本上只能
换Check，正在考虑要不要关...
Forward木有用过...
换Check，正在考虑要不要关...
Forward木有用过...
l*n
5 楼
vehicle pickup/deliver,
blue is pickup, red is deliver.
【在 x*****p 的大作中提到】
: 平面上有随机2000个点，其中1000蓝点，1000红点。但任何三点都不同线。
: 要求寻找一种算法，生成1000条互不相交的连接蓝点和红点的线段。换句话说，让任何
: 蓝点去连接任何
: 红点，但各不相交。
blue is pickup, red is deliver.
【在 x*****p 的大作中提到】
: 平面上有随机2000个点，其中1000蓝点，1000红点。但任何三点都不同线。
: 要求寻找一种算法，生成1000条互不相交的连接蓝点和红点的线段。换句话说，让任何
: 蓝点去连接任何
: 红点，但各不相交。
m*n
6 楼
呃，可我听说citi的dividend和forward卡蛮不错的啊～还有其他信用卡推荐呢么？
【在 T*********0 的大作中提到】
: 第一张申了Dividend，除了容易Pass+CL比较高，感觉一般，Cashback基本上只能
: 换Check，正在考虑要不要关...
: Forward木有用过...
【在 T*********0 的大作中提到】
: 第一张申了Dividend，除了容易Pass+CL比较高，感觉一般，Cashback基本上只能
: 换Check，正在考虑要不要关...
: Forward木有用过...
f*4
7 楼
求细节。。。
【在 l******n 的大作中提到】
: vehicle pickup/deliver,
: blue is pickup, red is deliver.
【在 l******n 的大作中提到】
: vehicle pickup/deliver,
: blue is pickup, red is deliver.
c*7
8 楼
forward
d*2
9 楼
How about just sort blue and red points by x-axis value separately and then
connect them by sorting order?
connect them by sorting order?
s*g
10 楼
forward is usually better
l*a
11 楼
blue are all in 2,3 向县
red are all in 1,4 向县
感觉上你这个就不对
then
【在 d****2 的大作中提到】
: How about just sort blue and red points by x-axis value separately and then
: connect them by sorting order?
red are all in 1,4 向县
感觉上你这个就不对
then
【在 d****2 的大作中提到】
: How about just sort blue and red points by x-axis value separately and then
: connect them by sorting order?
T*0
12 楼
如果是第一张信用卡的话那还是Citi吧，Pass概率一般比较大，什么Chase Freedom就
不要考虑了...
具体的Citi卡你认真对比一下看哪个合适咯...
【在 m*****n 的大作中提到】
: 呃，可我听说citi的dividend和forward卡蛮不错的啊～还有其他信用卡推荐呢么？
不要考虑了...
具体的Citi卡你认真对比一下看哪个合适咯...
【在 m*****n 的大作中提到】
: 呃，可我听说citi的dividend和forward卡蛮不错的啊～还有其他信用卡推荐呢么？
m*g
13 楼
Good point! Maybe y-axis sorting is also needed. Either separate or combine.
then
【在 d****2 的大作中提到】
: How about just sort blue and red points by x-axis value separately and then
: connect them by sorting order?
then
【在 d****2 的大作中提到】
: How about just sort blue and red points by x-axis value separately and then
: connect them by sorting order?
t*5
14 楼
我第一张申的citi的dividend，第一次来美国4个多月就申到了。CL有3000.
l*a
15 楼
mark
z*o
16 楼
1. 放弃“不交”这个条件，直接做一个随机初始解。
2. 对任意相交的一对线， B1--R1, B2--R2, 交换， 变成 B1--R2, B2--R1， 消除一
个相交。
3. 反复做2直到没有相交的线了。
Done
2. 对任意相交的一对线， B1--R1, B2--R2, 交换， 变成 B1--R2, B2--R1， 消除一
个相交。
3. 反复做2直到没有相交的线了。
Done
x*p
17 楼
消除一个相交，可能造成更多的相交。
此解错误。
【在 z****o 的大作中提到】
: 1. 放弃“不交”这个条件，直接做一个随机初始解。
: 2. 对任意相交的一对线， B1--R1, B2--R2, 交换， 变成 B1--R2, B2--R1， 消除一
: 个相交。
: 3. 反复做2直到没有相交的线了。
: Done
此解错误。
【在 z****o 的大作中提到】
: 1. 放弃“不交”这个条件，直接做一个随机初始解。
: 2. 对任意相交的一对线， B1--R1, B2--R2, 交换， 变成 B1--R2, B2--R1， 消除一
: 个相交。
: 3. 反复做2直到没有相交的线了。
: Done
z*o
18 楼
的确消除一个相交可能会造成更多的相交，但是“此解错误”的结论太轻率了。
Let me prove it!
程序有穷性：
Lemma 1. 每次交换操作使得被交换的两条线的总长度减小。
交换之前 B1-R1 与 B2-R2 相交， 可以看作是四边形 B1-B2-R1-R2 的两条对角线。
交换之后 B1-R2 与 B2-R1 不交， 是这个四边形的一对边。
易知： 对角线长之和 > 任意两条边长之和。得证。
Lemma 2. 在有限次执行之后算法会终止。
由Lemma 1 可知每次交换操作使得所有边的总长度减小，而所有边的总长度一定大
于0，所以在有限次执行之后算法会终止。
程序正确性：
由 终止条件 知，终止时必不满足“存在一对相交的线”。则正确性可知。
【在 x*****p 的大作中提到】
: 消除一个相交，可能造成更多的相交。
: 此解错误。
Let me prove it!
程序有穷性：
Lemma 1. 每次交换操作使得被交换的两条线的总长度减小。
交换之前 B1-R1 与 B2-R2 相交， 可以看作是四边形 B1-B2-R1-R2 的两条对角线。
交换之后 B1-R2 与 B2-R1 不交， 是这个四边形的一对边。
易知： 对角线长之和 > 任意两条边长之和。得证。
Lemma 2. 在有限次执行之后算法会终止。
由Lemma 1 可知每次交换操作使得所有边的总长度减小，而所有边的总长度一定大
于0，所以在有限次执行之后算法会终止。
程序正确性：
由 终止条件 知，终止时必不满足“存在一对相交的线”。则正确性可知。
【在 x*****p 的大作中提到】
: 消除一个相交，可能造成更多的相交。
: 此解错误。
Z*4
19 楼
那如何证明算法在有限次执行后会终止呢？
线。
【在 z****o 的大作中提到】
: 的确消除一个相交可能会造成更多的相交，但是“此解错误”的结论太轻率了。
: Let me prove it!
: 程序有穷性：
: Lemma 1. 每次交换操作使得被交换的两条线的总长度减小。
: 交换之前 B1-R1 与 B2-R2 相交， 可以看作是四边形 B1-B2-R1-R2 的两条对角线。
: 交换之后 B1-R2 与 B2-R1 不交， 是这个四边形的一对边。
: 易知： 对角线长之和 > 任意两条边长之和。得证。
: Lemma 2. 在有限次执行之后算法会终止。
: 由Lemma 1 可知每次交换操作使得所有边的总长度减小，而所有边的总长度一定大
: 于0，所以在有限次执行之后算法会终止。
线。
【在 z****o 的大作中提到】
: 的确消除一个相交可能会造成更多的相交，但是“此解错误”的结论太轻率了。
: Let me prove it!
: 程序有穷性：
: Lemma 1. 每次交换操作使得被交换的两条线的总长度减小。
: 交换之前 B1-R1 与 B2-R2 相交， 可以看作是四边形 B1-B2-R1-R2 的两条对角线。
: 交换之后 B1-R2 与 B2-R1 不交， 是这个四边形的一对边。
: 易知： 对角线长之和 > 任意两条边长之和。得证。
: Lemma 2. 在有限次执行之后算法会终止。
: 由Lemma 1 可知每次交换操作使得所有边的总长度减小，而所有边的总长度一定大
: 于0，所以在有限次执行之后算法会终止。
z*o
20 楼
追梦很sharp啊~ 的确是这个地方没有说的够清楚。
我写一个证明，正确性可以保证，但是是临时想的有可能绕弯子了。
并且这个证明不能用来估计复杂度。
重新证明可终止：
Let me prove in details:
Lemma 1. 算法在有限次会终止。
Lemma 1.1 每次交换后新生成的两条边长均小于原有的两条边长。（易知）
Lemma 1.2 一个交叉 B1-R1,B2-R2 在交换分离之后仅可能重现有限次。
Lemma 1.2.1 一条边在被删除后只能重构有限次。
Proof. 数学归纳法
注： 总假设 B1-R1 的长度>=B2-R2的长度，对证明无影响。
base case: B1-R1 是初始情况下最长的边，B1-R1 若被删除，
只能重构有限次。因为没有任何的交换操作可以生成
比交换前更长的边，所以B1-R1删除后无法被重构。
归纳假设：若第i长的边在被删除后只能重构有限次， 1<=i<=k，
则有第k+1长的边在被删除只能重构有限次。
证明：
因为重建第k长的那条边必须至少删除一个比k排名小的边，
这种边出现的次数总和是有限的。
所以Lemma 1.2.1 得证。
所以Lemma 1.2得证。
Lemma 1.3 一个2n个点的图中，可能的交叉的个数是有限的（易知起码小于 n^4种）
由：在一个2n个点的图中，可能的交叉个数是有限的，
且: 每个交叉可以重现的次数是有限的，
且：每次交换必然消除一个交叉
得： 算法必然终止。
Lemma 1 得证。
这个太累了。。。。。
如果在消除交叉的时候先对所有交叉排序（按照所包含的最大边），
然后总是先消除那个最“大”的交叉，这样程序的效率会提高，
一个可能很松但是很容易的upper bound是：最多也就是n^4次消除操作
实现的时候对所有的交叉用maxHeap，新生成的交叉丢进heap里面。
期待更好的算法。
【在 Z**********4 的大作中提到】
: 那如何证明算法在有限次执行后会终止呢？
:
: 线。
我写一个证明，正确性可以保证，但是是临时想的有可能绕弯子了。
并且这个证明不能用来估计复杂度。
重新证明可终止：
Let me prove in details:
Lemma 1. 算法在有限次会终止。
Lemma 1.1 每次交换后新生成的两条边长均小于原有的两条边长。（易知）
Lemma 1.2 一个交叉 B1-R1,B2-R2 在交换分离之后仅可能重现有限次。
Lemma 1.2.1 一条边在被删除后只能重构有限次。
Proof. 数学归纳法
注： 总假设 B1-R1 的长度>=B2-R2的长度，对证明无影响。
base case: B1-R1 是初始情况下最长的边，B1-R1 若被删除，
只能重构有限次。因为没有任何的交换操作可以生成
比交换前更长的边，所以B1-R1删除后无法被重构。
归纳假设：若第i长的边在被删除后只能重构有限次， 1<=i<=k，
则有第k+1长的边在被删除只能重构有限次。
证明：
因为重建第k长的那条边必须至少删除一个比k排名小的边，
这种边出现的次数总和是有限的。
所以Lemma 1.2.1 得证。
所以Lemma 1.2得证。
Lemma 1.3 一个2n个点的图中，可能的交叉的个数是有限的（易知起码小于 n^4种）
由：在一个2n个点的图中，可能的交叉个数是有限的，
且: 每个交叉可以重现的次数是有限的，
且：每次交换必然消除一个交叉
得： 算法必然终止。
Lemma 1 得证。
这个太累了。。。。。
如果在消除交叉的时候先对所有交叉排序（按照所包含的最大边），
然后总是先消除那个最“大”的交叉，这样程序的效率会提高，
一个可能很松但是很容易的upper bound是：最多也就是n^4次消除操作
实现的时候对所有的交叉用maxHeap，新生成的交叉丢进heap里面。
期待更好的算法。
【在 Z**********4 的大作中提到】
: 那如何证明算法在有限次执行后会终止呢？
:
: 线。
l*y
21 楼
zan formal!
【在 z****o 的大作中提到】
: 追梦很sharp啊~ 的确是这个地方没有说的够清楚。
: 我写一个证明，正确性可以保证，但是是临时想的有可能绕弯子了。
: 并且这个证明不能用来估计复杂度。
: 重新证明可终止：
: Let me prove in details:
: Lemma 1. 算法在有限次会终止。
: Lemma 1.1 每次交换后新生成的两条边长均小于原有的两条边长。（易知）
: Lemma 1.2 一个交叉 B1-R1,B2-R2 在交换分离之后仅可能重现有限次。
: Lemma 1.2.1 一条边在被删除后只能重构有限次。
: Proof. 数学归纳法
【在 z****o 的大作中提到】
: 追梦很sharp啊~ 的确是这个地方没有说的够清楚。
: 我写一个证明，正确性可以保证，但是是临时想的有可能绕弯子了。
: 并且这个证明不能用来估计复杂度。
: 重新证明可终止：
: Let me prove in details:
: Lemma 1. 算法在有限次会终止。
: Lemma 1.1 每次交换后新生成的两条边长均小于原有的两条边长。（易知）
: Lemma 1.2 一个交叉 B1-R1,B2-R2 在交换分离之后仅可能重现有限次。
: Lemma 1.2.1 一条边在被删除后只能重构有限次。
: Proof. 数学归纳法
x*p
22 楼
zhshao的数学功底不错，是学数学的么？
不过算法功底不好，所用的证明方法，估计完全能看懂的人不多，但这个方法实际上是
证明了解的存在性，而相应算法的复杂度就相当高了。
所以我说此解错误。
不过算法功底不好，所用的证明方法，估计完全能看懂的人不多，但这个方法实际上是
证明了解的存在性，而相应算法的复杂度就相当高了。
所以我说此解错误。
x*p
23 楼
我再说清楚一点吧。
由：在一个2n个点的图中，可能的交叉个数是有限的，
这句话是完全正确的，但这个有限的可能是非常巨大的。换句话说，我把所有的可能性
都验证一遍，从解的存在性可知，必有一解是满足条件的。而所有解的空间是有限的。
对2n个点的图来说，其实是从n个点到n个点的所有一一对应函数的空间，共有n!个。
还有对
Lemma 1.3 一个2n个点的图中，可能的交叉的个数是有限的（易知起码小于 n^4种）
能证明一下为什么小于n^4个么？至少我不觉得“易知”。在消除交叉的过程中，会产
生新的交叉。这样总共的交叉个数不是多项式级别的。
由：在一个2n个点的图中，可能的交叉个数是有限的，
这句话是完全正确的，但这个有限的可能是非常巨大的。换句话说，我把所有的可能性
都验证一遍，从解的存在性可知，必有一解是满足条件的。而所有解的空间是有限的。
对2n个点的图来说，其实是从n个点到n个点的所有一一对应函数的空间，共有n!个。
还有对
Lemma 1.3 一个2n个点的图中，可能的交叉的个数是有限的（易知起码小于 n^4种）
能证明一下为什么小于n^4个么？至少我不觉得“易知”。在消除交叉的过程中，会产
生新的交叉。这样总共的交叉个数不是多项式级别的。
h*c
24 楼
又想了想，凸形上的点应该可以满足条件
【在 x*****p 的大作中提到】
: 平面上有随机2000个点，其中1000蓝点，1000红点。但任何三点都不同线。
: 要求寻找一种算法，生成1000条互不相交的连接蓝点和红点的线段。换句话说，让任何
: 蓝点去连接任何
: 红点，但各不相交。
【在 x*****p 的大作中提到】
: 平面上有随机2000个点，其中1000蓝点，1000红点。但任何三点都不同线。
: 要求寻找一种算法，生成1000条互不相交的连接蓝点和红点的线段。换句话说，让任何
: 蓝点去连接任何
: 红点，但各不相交。
l*a
25 楼
我觉得他的n^4是这么算出来的。
总共2n个点
=>最多C(n,2) = n(n-1)/2条线段
=>最多n(n-1)/2 * (n(n-1)/2 -1) = O(n^4)个交点。
【在 x*****p 的大作中提到】
: 我再说清楚一点吧。
: 由：在一个2n个点的图中，可能的交叉个数是有限的，
: 这句话是完全正确的，但这个有限的可能是非常巨大的。换句话说，我把所有的可能性
: 都验证一遍，从解的存在性可知，必有一解是满足条件的。而所有解的空间是有限的。
: 对2n个点的图来说，其实是从n个点到n个点的所有一一对应函数的空间，共有n!个。
: 还有对
: Lemma 1.3 一个2n个点的图中，可能的交叉的个数是有限的（易知起码小于 n^4种）
: 能证明一下为什么小于n^4个么？至少我不觉得“易知”。在消除交叉的过程中，会产
: 生新的交叉。这样总共的交叉个数不是多项式级别的。
总共2n个点
=>最多C(n,2) = n(n-1)/2条线段
=>最多n(n-1)/2 * (n(n-1)/2 -1) = O(n^4)个交点。
【在 x*****p 的大作中提到】
: 我再说清楚一点吧。
: 由：在一个2n个点的图中，可能的交叉个数是有限的，
: 这句话是完全正确的，但这个有限的可能是非常巨大的。换句话说，我把所有的可能性
: 都验证一遍，从解的存在性可知，必有一解是满足条件的。而所有解的空间是有限的。
: 对2n个点的图来说，其实是从n个点到n个点的所有一一对应函数的空间，共有n!个。
: 还有对
: Lemma 1.3 一个2n个点的图中，可能的交叉的个数是有限的（易知起码小于 n^4种）
: 能证明一下为什么小于n^4个么？至少我不觉得“易知”。在消除交叉的过程中，会产
: 生新的交叉。这样总共的交叉个数不是多项式级别的。
x*p
26 楼
问题是在消除交叉点的过程中，只是总长度变小了，但交叉点的个数可能会增加，这样
算上新的交叉
点，不知道有多少个了。
【在 l*****a 的大作中提到】
: 我觉得他的n^4是这么算出来的。
: 总共2n个点
: =>最多C(n,2) = n(n-1)/2条线段
: =>最多n(n-1)/2 * (n(n-1)/2 -1) = O(n^4)个交点。
算上新的交叉
点，不知道有多少个了。
【在 l*****a 的大作中提到】
: 我觉得他的n^4是这么算出来的。
: 总共2n个点
: =>最多C(n,2) = n(n-1)/2条线段
: =>最多n(n-1)/2 * (n(n-1)/2 -1) = O(n^4)个交点。
z*o
27 楼
在有序的消除的过程中, 一个交叉点消除之后不会重现了.
【在 x*****p 的大作中提到】
: 问题是在消除交叉点的过程中，只是总长度变小了，但交叉点的个数可能会增加，这样
: 算上新的交叉
: 点，不知道有多少个了。
【在 x*****p 的大作中提到】
: 问题是在消除交叉点的过程中，只是总长度变小了，但交叉点的个数可能会增加，这样
: 算上新的交叉
: 点，不知道有多少个了。
g*s
28 楼
其实你的证明也是证明了用最大（小）流算法的正确性，也就是lfbenben 提到的
vehicle
pickup/deliver解法。
二分图的最大（小）匹配问题,算法复杂度其实是O（n＊m）＝O（n＾３）
【在 z****o 的大作中提到】
: 在有序的消除的过程中, 一个交叉点消除之后不会重现了.
vehicle
pickup/deliver解法。
二分图的最大（小）匹配问题,算法复杂度其实是O（n＊m）＝O（n＾３）
【在 z****o 的大作中提到】
: 在有序的消除的过程中, 一个交叉点消除之后不会重现了.
相关阅读
ANA点数问题300左右的礼物什么比较好amex app装不上。citi divident 5% 可以买bestbuy的egiftcard吗请教用VGC去PO买money order大家贡献GCM 买VGC DP吧starwood点 inactive了没有了，怎么reinstate?ebay的gc可以在ebay买其他的gc吗？油卡之类的问个 kmart autodrain问题总算GCM下了一单5b警惕：Amazon买的Starbucks GC直接被USPS偷了Amex 白金卡200现在能撸啥？amazon超过200个order要发1099，那cancel的order 会count在里面吗？大家讨论一下有什么好的store credit cardSallie Mae转新卡之后有个有趣的perkANA订票总是出错，谁知道这是咋回事？收到国内汇款申报的问题cashstar 买的bestbuy promotional gift card过期两天还有解么？请问给加拿大的朋友寄amazon礼品卡，选择美元还是加币？verizon 最新的iphone deal是不是比9月之前的trade in要好很多啊