用chase ink付ebay的东西被decline？没超过100刀，有高人解读一下吗？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Money - 海外理财

用chase ink付ebay的东西被decline？没超过100刀，有高人解读一下吗？

用chase ink付ebay的东西被decline？没超过100刀，有高人解读一下吗？# Money - 海外理财

a*x2014-02-06 08:02

1 楼

某人要开party，总共有n个人可以选择邀请。举办者知道m对人的两两认识关系。
他想让每个参加party的人认识的参加party的人数目大于或者等于5；同时每个参加
party的人在party上的陌生人数目也大于或等于5.
问如何选取最大的subset of n 人来参加party。
我能想到O(n^2)的算法。不知道O(n + m)如何解决。

M*82014-02-06 08:02

2 楼

chase又出什么妖蛾子？连在paypal上的一张卡，用了很久了，今天ebay上买东西
paypal余额不够，剩下70多准备用chase ink付，结果被decline了，今天第一次用这个卡
打电话说客服说不能cash advance。。。太不能理解了

g*y2014-02-06 08:02

3 楼

说说你的解法？我的解法是，对于每一个人，如果他认识的人数大于n-5或者小于5，就
把他从list中删除，同时更新他认识的人的list，更新总人数n。然后再重头开始扫，
做相同的操作。直到list没有变化为止。感觉复杂度挺高的。

s*o2014-02-06 08:02

4 楼

偶前几天Home depot买一个9刀多的东东都被decline了。说是卡背面的3位数字没有输
。

a*x2014-02-06 08:02

5 楼

和你的思路差不多吧。我觉得应该有一些update status的trick能降低复杂度

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

: 说说你的解法？我的解法是，对于每一个人，如果他认识的人数大于n-5或者小于5，就
: 把他从list中删除，同时更新他认识的人的list，更新总人数n。然后再重头开始扫，
: 做相同的操作。直到list没有变化为止。感觉复杂度挺高的。

z*w2014-02-06 08:02

6 楼

奇怪.

C*U2014-02-06 08:02

7 楼

不知道题目的意思理解对不对。
是不是有n个人，然后举办的人知道所有相互认识关系。也就是m对人。

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

: 某人要开party，总共有n个人可以选择邀请。举办者知道m对人的两两认识关系。
: 他想让每个参加party的人认识的参加party的人数目大于或者等于5；同时每个参加
: party的人在party上的陌生人数目也大于或等于5.
: 问如何选取最大的subset of n 人来参加party。
: 我能想到O(n^2)的算法。不知道O(n + m)如何解决。

d*r2014-02-06 08:02

8 楼

会不会是ebay的问题？

个卡

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

: chase又出什么妖蛾子？连在paypal上的一张卡，用了很久了，今天ebay上买东西
: paypal余额不够，剩下70多准备用chase ink付，结果被decline了，今天第一次用这个卡
: 打电话说客服说不能cash advance。。。太不能理解了

a*x2014-02-06 08:02

9 楼

en

【在 C***U 的大作中提到】

: 不知道题目的意思理解对不对。
: 是不是有n个人，然后举办的人知道所有相互认识关系。也就是m对人。

M*82014-02-06 08:02

10 楼

实体店刷卡还要验证码。。。他家真不靠谱!

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

: 偶前几天Home depot买一个9刀多的东东都被decline了。说是卡背面的3位数字没有输
: 。

g*y2014-02-06 08:02

11 楼

展开说说？

【在 C***U 的大作中提到】

: 不知道题目的意思理解对不对。
: 是不是有n个人，然后举办的人知道所有相互认识关系。也就是m对人。

M*82014-02-06 08:02

12 楼

不确定，展开说说ebay可能是什么问题呢？

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

: 会不会是ebay的问题？
:
: 个卡

C*U2014-02-06 08:02

13 楼

你这样做不一定最优啊

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

t*u2014-02-06 08:02

14 楼

买的GC？

C*U2014-02-06 08:02

15 楼

我觉得我之前想错了

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

: 展开说说？

M*82014-02-06 08:02

16 楼

yes
刚才爬了几个楼，看来不是chase的问题
ebay买gc用cc好像都有问题。。

【在 t***u 的大作中提到】

: 买的GC？

g*y2014-02-06 08:02

17 楼

我没说最优啊，这只是我能想到的方法。。。。

【在 C***U 的大作中提到】

: 你这样做不一定最优啊

d*y2014-02-06 08:02

18 楼

我觉得可以证明是最优的。

【在 C***U 的大作中提到】

: 你这样做不一定最优啊

C*U2014-02-06 08:02

19 楼

给你个例子
给10组5个点的complete graph。也就是说每个组5个人。然后这5个人相互认识。这样
10个组。
然后有单独一个人，他和其他所有人认识。

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

: 我觉得可以证明是最优的。

c*t2014-02-06 08:02

20 楼

建一个map, key是认识人数，value是人，就是认识i个人的所有人在一个value
当从list删除这个人的时候，更新他认识的人的list，如果他认识的人变的<5,
recursion 删除这个人，他不认识的人如果是认识总数=n-5的，从map中找到他们
recursion 删除，总人数n--。应该是n+m的复杂度吧

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

C*U2014-02-06 08:02

21 楼

你开始怎么选的人?

【在 c********t 的大作中提到】

: 建一个map, key是认识人数，value是人，就是认识i个人的所有人在一个value
: 当从list删除这个人的时候，更新他认识的人的list，如果他认识的人变的<5,
: recursion 删除这个人，他不认识的人如果是认识总数=n-5的，从map中找到他们
: recursion 删除，总人数n--。应该是n+m的复杂度吧

d*y2014-02-06 08:02

22 楼

OK，初始状态，一共51个人，其中有50个人，每个人和6个人认识，另外一个人，认识
其余50个人。
第一步就是把那个人删掉。
剩下的50个人，没法删除任一个，就是最优解

【在 C***U 的大作中提到】

: 给你个例子
: 给10组5个点的complete graph。也就是说每个组5个人。然后这5个人相互认识。这样
: 10个组。
: 然后有单独一个人，他和其他所有人认识。

f*e2014-02-06 08:02

23 楼

要有数学证明才行，否则只能是猜想。

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

: OK，初始状态，一共51个人，其中有50个人，每个人和6个人认识，另外一个人，认识
: 其余50个人。
: 第一步就是把那个人删掉。
: 剩下的50个人，没法删除任一个，就是最优解

g*y2014-02-06 08:02

24 楼

哦，你说不优的意思是说解答不对？我还以为你说效率不好呢。你这个例子很好解决啊
。第一轮去掉那个认识所有人的。然后剩下的所有人都符合要求了，直接返回了。

【在 C***U 的大作中提到】

: 给你个例子
: 给10组5个点的complete graph。也就是说每个组5个人。然后这5个人相互认识。这样
: 10个组。
: 然后有单独一个人，他和其他所有人认识。

y*e2014-02-06 08:02

25 楼

这里问题的本质是，你如何知道第一轮先去掉这个人而不是其他人？简单来说，当存在
两个人都不合格而且认识人数一样的时候（比如有两个人认识所有人），如何选择该先
删谁？

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

: 哦，你说不优的意思是说解答不对？我还以为你说效率不好呢。你这个例子很好解决啊
: 。第一轮去掉那个认识所有人的。然后剩下的所有人都符合要求了，直接返回了。

g*y2014-02-06 08:02

26 楼

都去掉。。。。。。

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

: 这里问题的本质是，你如何知道第一轮先去掉这个人而不是其他人？简单来说，当存在
: 两个人都不合格而且认识人数一样的时候（比如有两个人认识所有人），如何选择该先
: 删谁？

g*y2014-02-06 08:02

27 楼

去掉的顺序无关。

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

C*U2014-02-06 08:02

28 楼

你不能拿特殊的然后说能解决。那我给个别的例子呢?

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

y*e2014-02-06 08:02

29 楼

当然有关啊，去掉一个点会改变剩下节点的度，比如A，B都不合格，并且度一样（不是
认识所有人），去掉A点会产生一个原本认识5个人而变成只认识4个人点，但去掉B点则
不会出现，这种情况是很好构造的。

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

: 去掉的顺序无关。

g*y2014-02-06 08:02

30 楼

但是A B早晚要去掉，不合格的早晚不合格，跟你去掉那个没关。既然这么好构造，你
构造一个反例来说明removal order matters

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

: 当然有关啊，去掉一个点会改变剩下节点的度，比如A，B都不合格，并且度一样（不是
: 认识所有人），去掉A点会产生一个原本认识5个人而变成只认识4个人点，但去掉B点则
: 不会出现，这种情况是很好构造的。

g*y2014-02-06 08:02

31 楼

我没有用特例，是你自己说给了反例。。。。。

【在 C***U 的大作中提到】

: 你不能拿特殊的然后说能解决。那我给个别的例子呢?

C*U2014-02-06 08:02

32 楼

而且我的例子你的解答不对。。。
应该是去掉一个组
然后把剩下9个组和那个人加进来
因为如果把那个所有人都认识的人去掉
别的人只认识4个人那就是所有人都不能参加了！

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

C*U2014-02-06 08:02

33 楼

你的解答是不对的
我的那个例子应该是46个人是最佳的
而不是50个人。

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

: 我没有用特例，是你自己说给了反例。。。。。

g*y2014-02-06 08:02

34 楼

不知道你在说什么，为什么要去掉一个组?你不是说一个组五个人，然后相互认识吗？

【在 C***U 的大作中提到】

: 你的解答是不对的
: 我的那个例子应该是46个人是最佳的
: 而不是50个人。

C*U2014-02-06 08:02

35 楼

对啊
每个人必须认识5个人才能去聚会
一个组5个人，那么一个人只认识4个人！

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

: 不知道你在说什么，为什么要去掉一个组?你不是说一个组五个人，然后相互认识吗？

C*U2014-02-06 08:02

36 楼

原题要求：
他想让每个参加party的人认识的参加party的人数目大于或者等于5；同时每个参加
party的人在party上的陌生人数目也大于或等于5.

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

: 不知道你在说什么，为什么要去掉一个组?你不是说一个组五个人，然后相互认识吗？

g*y2014-02-06 08:02

37 楼

你想说明什么？我投降了…

【在 C***U 的大作中提到】

: 原题要求：
: 他想让每个参加party的人认识的参加party的人数目大于或者等于5；同时每个参加
: party的人在party上的陌生人数目也大于或等于5.

C*U2014-02-06 08:02

38 楼

晕
我想说明你给的解答不对啊
那个所有人都认识的人应该参加。。。。
就这么简单啊。。。。
你说的是让所有人都认识的不参加其余的人都参加
这个解答不符合原题要求因为剩余的人只认识4个人了
我说的答案是应该让所有人都认识的那个人参加然后10组里面选9组参加
总共46个人才是正确答案

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

: 你想说明什么？我投降了…

C*U2014-02-06 08:02

39 楼

大牛
这个是你给的解答
发信人: gnahzy (hello), 信区: JobHunting
标题: Re: 问一道算法题
发信站: BBS 未名空间站 (Thu Oct 4 16:30:52 2012, 美东)
哦，你说不优的意思是说解答不对？我还以为你说效率不好呢。你这个例子很好解决啊
。第一轮去掉那个认识所有人的。然后剩下的所有人都符合要求了，直接返回了。
如果不是我理解错你的意思了的话你给的解答是错误的。。。。。

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

: 你想说明什么？我投降了…

g*y2014-02-06 08:02

40 楼

靠，是我不好。我以为一个小组5个人，每个人就认识5个人呢。但是我的算法没问题。
正确答案是没有人符合要求。你那个46个人不对。因为有一个人认识晚会上的所有人。

【在 C***U 的大作中提到】

: 晕
: 我想说明你给的解答不对啊
: 那个所有人都认识的人应该参加。。。。
: 就这么简单啊。。。。
: 你说的是让所有人都认识的不参加其余的人都参加
: 这个解答不符合原题要求因为剩余的人只认识4个人了
: 我说的答案是应该让所有人都认识的那个人参加然后10组里面选9组参加
: 总共46个人才是正确答案

C*U2014-02-06 08:02

41 楼

好吧。。。我也理解错题意了。。。
我以为是认识的人要少于n-5
不是n-5
是party上的人数-5
才看清楚

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

: 靠，是我不好。我以为一个小组5个人，每个人就认识5个人呢。但是我的算法没问题。
: 正确答案是没有人符合要求。你那个46个人不对。因为有一个人认识晚会上的所有人。

D*f2014-02-06 08:02

42 楼

我的想法是这样的：
先扫描全部人，排除所有认识人数小于5的（可以证明包括他们的解是错误的）
再扫描剩下的人，（其实可以合并到第一趟扫描里面）
每扫描一个人，记录当前扫描到的人数，记为X，当前认识人最多的那个人认识Y个人，
只要扫描到符合如下condition的节点就可以返回了：
X>Y+5，如果扫描完了还不符合，就是没有。
可以证明有返回结果肯定是对的，但是没找到是不是就一定没有，还得证明一下。

C*U2014-02-06 08:02

43 楼

题目再看一下。我相信删除节点的办法是对的。