B*Q 发帖数: 25729 | 1 刚才蹲厕所的时候
好好的沿着insider大佬的思路想了想
8次的确是对的
废话少说
撸起袖子努力整:
1. 整5次,排出5个小分队,5个一组
2. 第六次,每队第一名比一下,按第一名的名次把小分队编号, 1,2,3,4,5
1.1>2.1>3.1>4.1>5.1
n.1>n.2>n.3>n.4>n.5 (n = 1 .. 5)
3. 第七次 (尼玛, insider 大佬的沈锦斌之处一展无遗)
比1.2, 2.2, 3.2, 4.2, 5.1
4.a: 如果5.1 是七轮第一名,头五名就有了
4.b: 如果5.1 不是第一名,就是废物几个,宰了
4.b.a: 如果4.2 是七轮第一名, 头五名就是1.1, 2.1, 3.1, 4.1, 4.2
4.b.b:如果4.2 不是第一名,也宰了,剩下 1.2, 2.2, 3.2
4.b.b.a: 1.2, 2.2, 3.2 里的最后一名可以也宰了, 还剩 5匹, 2.1, 3.1, 4.
1 和两个x.2的。 再比一次(第八吃)就好了
4.b.b.a 的证明,就留给将军们做课后作业了 |
n******i 发帖数: 1 | 2 恩
[在 BCQ (不差钱) 的大作中提到:]
:刚才蹲厕所的时候
:好好的沿着insider大佬的思路想了想
:废话少说
:撸起袖子努力整:
:1. 整5次,排出5个小分队,5个一组
: 1.1>2.1>3.1>4.1>5.1
: n.1>n.2>n.3>n.4>n.5 (n = 1 .. 5)
: 比1.2, 2.2, 3.2, 4.2, 5.1 |
S****8 发帖数: 1 | 3 按照我游泳比赛的经历,在现实生活中,这个基本不可能。。。
初赛怎么安排啊。
假如把最强壮的5匹马放在一组。。。
结果就是0次比赛。。。太无聊了。。
【在 B*Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才蹲厕所的时候 : 好好的沿着insider大佬的思路想了想 : 8次的确是对的 : 废话少说 : 撸起袖子努力整: : 1. 整5次,排出5个小分队,5个一组 : 2. 第六次,每队第一名比一下,按第一名的名次把小分队编号, 1,2,3,4,5 : 1.1>2.1>3.1>4.1>5.1 : n.1>n.2>n.3>n.4>n.5 (n = 1 .. 5) : 3. 第七次 (尼玛, insider 大佬的沈锦斌之处一展无遗)
|
B*Q 发帖数: 25729 | 4 嗯
好像还是有纰漏
俺也成沈锦斌了
投五名完全可以是1.1, 1.2, 1.3, 1.4, 1.5
这个答案insider大佬的做法整不出来
麻痹
学文科的底子是薄一些 |
s******2 发帖数: 1 | 5 极端case是第一组5匹马就是top5,你这里没有cover |
z*****i 发帖数: 1 | |
i*****r 发帖数: 105 | 7 第七轮选1.3,2.2,3.2,4.2,5.1就可以了。
: 嗯
: 好像还是有纰漏
: 俺也成沈锦斌了
: 投五名完全可以是1.1, 1.2, 1.3, 1.4, 1.5
: 这个答案insider大佬的做法整不出来
: 麻痹
: 学文科的底子是薄一些
【在 B*Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 嗯 : 好像还是有纰漏 : 俺也成沈锦斌了 : 投五名完全可以是1.1, 1.2, 1.3, 1.4, 1.5 : 这个答案insider大佬的做法整不出来 : 麻痹 : 学文科的底子是薄一些
|
p******g 发帖数: 8316 | 8 洗脚哥这是抄袭我的思路的吧。哈哈哈
赶紧给个包子
【在 s******2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 极端case是第一组5匹马就是top5,你这里没有cover
|
S****8 发帖数: 1 | 9 所以,我觉得最聪明的就是你了。
都不用比赛,把最强壮的5匹马挑出来就可以了。
答案为0.
【在 z*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果前五名不巧都分在第一组里呢?嘿嘿嘿
|
S****8 发帖数: 1 | 10 我突然感觉很好笑,
是不是认真去做题目的都是精神病啊。。。 |
|
|
o****p 发帖数: 9785 | 11 千老?
【在 B*Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才蹲厕所的时候 : 好好的沿着insider大佬的思路想了想 : 8次的确是对的 : 废话少说 : 撸起袖子努力整: : 1. 整5次,排出5个小分队,5个一组 : 2. 第六次,每队第一名比一下,按第一名的名次把小分队编号, 1,2,3,4,5 : 1.1>2.1>3.1>4.1>5.1 : n.1>n.2>n.3>n.4>n.5 (n = 1 .. 5) : 3. 第七次 (尼玛, insider 大佬的沈锦斌之处一展无遗)
|
i*****r 发帖数: 105 | 12 这样,你的4.a和4.b,就需要第八轮。这个比较树就更加平衡一些。当1.3是第一,2.2
是第二的时候,第八轮,1.4,1.5,2.2,3.1就可以了。
: 第七轮选1.3,2.2,3.2,4.2,5.1就可以了。
【在 i*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第七轮选1.3,2.2,3.2,4.2,5.1就可以了。 : : : 嗯 : : 好像还是有纰漏 : : 俺也成沈锦斌了 : : 投五名完全可以是1.1, 1.2, 1.3, 1.4, 1.5 : : 这个答案insider大佬的做法整不出来 : : 麻痹 : : 学文科的底子是薄一些 :
|
B*Q 发帖数: 25729 | 13 不是
俺是文科转码的
不容易吧
【在 o****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 千老?
|
d********8 发帖数: 691 | 14 大哥,你说8次我还真信了,差评
【在 B*Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 嗯 : 好像还是有纰漏 : 俺也成沈锦斌了 : 投五名完全可以是1.1, 1.2, 1.3, 1.4, 1.5 : 这个答案insider大佬的做法整不出来 : 麻痹 : 学文科的底子是薄一些
|
B*Q 发帖数: 25729 | 15 做题有快感
可以替代鹿
【在 S****8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我突然感觉很好笑, : 是不是认真去做题目的都是精神病啊。。。
|
p******g 发帖数: 8316 | 16 这种题目属于open talk,可以有好几个答案
有一种极端情况下,一次就行,random walk theory,这是经济学很常见的case,闭着
眼睛炒股的盈利都比你用一堆TA/FA/波动方程做出来的预期效果好。
有一种极端情况下,要穷举到最后一匹马才算为止。
所以算法都要讲究best case, worst case,average case.
列出来的average case可以用O来表达。所以具体最终数字结果已经不重要了。
insertion sort的复杂度在worst case就是O(n^2),而且还有另外一个实际情况就是一
部分马在每次比赛的速度不一样,这次快了,下次又慢了,所以你真正在操作上要多次
比赛,计算每匹马的平均值才更趋近于精确值,就像奥运会比赛选手一样,在家里跑的
速度和在场上预赛/半决赛/决赛的效果都有很大差别,甚至还有违规现象和爆发性的临
场发挥。
真实的工程项目,就这样的会有各种variation,你要提前预估出error analysis。
【在 B*Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才蹲厕所的时候 : 好好的沿着insider大佬的思路想了想 : 8次的确是对的 : 废话少说 : 撸起袖子努力整: : 1. 整5次,排出5个小分队,5个一组 : 2. 第六次,每队第一名比一下,按第一名的名次把小分队编号, 1,2,3,4,5 : 1.1>2.1>3.1>4.1>5.1 : n.1>n.2>n.3>n.4>n.5 (n = 1 .. 5) : 3. 第七次 (尼玛, insider 大佬的沈锦斌之处一展无遗)
|
s******2 发帖数: 1 | 17 淡啊,俺们码code必须要考虑极端case,比如fail了怎么办
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 洗脚哥这是抄袭我的思路的吧。哈哈哈 : 赶紧给个包子
|
B*Q 发帖数: 25729 | 18 车这么多没用的
你给出个八次的正解把
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这种题目属于open talk,可以有好几个答案 : 有一种极端情况下,一次就行,random walk theory,这是经济学很常见的case,闭着 : 眼睛炒股的盈利都比你用一堆TA/FA/波动方程做出来的预期效果好。 : 有一种极端情况下,要穷举到最后一匹马才算为止。 : 所以算法都要讲究best case, worst case,average case. : 列出来的average case可以用O来表达。所以具体最终数字结果已经不重要了。 : insertion sort的复杂度在worst case就是O(n^2),而且还有另外一个实际情况就是一 : 部分马在每次比赛的速度不一样,这次快了,下次又慢了,所以你真正在操作上要多次 : 比赛,计算每匹马的平均值才更趋近于精确值,就像奥运会比赛选手一样,在家里跑的 : 速度和在场上预赛/半决赛/决赛的效果都有很大差别,甚至还有违规现象和爆发性的临
|
B*Q 发帖数: 25729 | 19 俺是跟着内线大佬的
【在 d********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大哥,你说8次我还真信了,差评
|
B*Q 发帖数: 25729 | 20 好
俺再按新思路整整看
.2
【在 i*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这样,你的4.a和4.b,就需要第八轮。这个比较树就更加平衡一些。当1.3是第一,2.2 : 是第二的时候,第八轮,1.4,1.5,2.2,3.1就可以了。 : : : 第七轮选1.3,2.2,3.2,4.2,5.1就可以了。 :
|
|
|
p******g 发帖数: 8316 | 21 都说了,运气好的时候,一次就够了,题目上并没有限制是最优解还是平均解吧,你怎
么确定你每次挑选的时候都需要8次呢? 实际工程中,你有10万匹马,每次都一波5个
的去比,怎么能证明你次次都要8次来搞定呢?
所以最优解也是答案的一种,这是思考问题的skill set
【在 B*Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 车这么多没用的 : 你给出个八次的正解把
|
d***u 发帖数: 943 | 22 说实话,我真心认为你和洗脚哥都解不出这个题,哈哈
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 洗脚哥这是抄袭我的思路的吧。哈哈哈 : 赶紧给个包子
|
s*****V 发帖数: 21731 | 23 3.3 呢?
【在 i*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第七轮选1.3,2.2,3.2,4.2,5.1就可以了。 : : : 嗯 : : 好像还是有纰漏 : : 俺也成沈锦斌了 : : 投五名完全可以是1.1, 1.2, 1.3, 1.4, 1.5 : : 这个答案insider大佬的做法整不出来 : : 麻痹 : : 学文科的底子是薄一些 :
|
p******g 发帖数: 8316 | 24 要看你的最终目的是什么:
如果是考试,必须有唯一解,会有一套标准的出题标准(包括各种限制条件都要摆出来)
如果是发paper,必须要有证明和推导,来证明8次是你每次都至少用得到的,这个证明
在这道题里显然是证不出来的。
如果是面试,解不出来不等于拿不到offer,解出来不等于拿得到offer
【在 d***u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 说实话,我真心认为你和洗脚哥都解不出这个题,哈哈
|
d***u 发帖数: 943 | 25 月光姐,你又来了。对了,你的小鲜肉可好。菌斑上哥最关心的就是你。
来)
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 要看你的最终目的是什么: : 如果是考试,必须有唯一解,会有一套标准的出题标准(包括各种限制条件都要摆出来) : 如果是发paper,必须要有证明和推导,来证明8次是你每次都至少用得到的,这个证明 : 在这道题里显然是证不出来的。 : 如果是面试,解不出来不等于拿不到offer,解出来不等于拿得到offer
|
e*g 发帖数: 4981 | 26 你不认识英文吗,in all cases
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 都说了,运气好的时候,一次就够了,题目上并没有限制是最优解还是平均解吧,你怎 : 么确定你每次挑选的时候都需要8次呢? 实际工程中,你有10万匹马,每次都一波5个 : 的去比,怎么能证明你次次都要8次来搞定呢? : 所以最优解也是答案的一种,这是思考问题的skill set
|
p******g 发帖数: 8316 | 27 是啊,所以每个case都需要》=8次才能下结论吗?你得证明对于各种layout回回都需要
》=8次啊。
【在 e*g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你不认识英文吗,in all cases
|
t******0 发帖数: 153 | 28 讲一下第七次,
1.1 -> 1.2 -> 1.3 -> 1.4 -> 1.5 为第一线
1.1 -> 2.1 -> 2.2 -> 2.3 -> 2.4 为第二线
1.1 -> 2.1 -> 3.1 -> 3.2 -> 3.3 为第三线
1.1 -> 2.1 -> 3.1 -> 4.1 -> 4.2 为第四线
1.1 -> 2.1 -> 3.1 -> 4.1 -> 5.1 为第五线
本来应该取各线的中间值进行第七次比赛。但第一线,第五线已经比过,所以应该是
3.1 2.2 1.3 4.1 5.1
但也可能更优化的。
这样下来,可能只要8次 |
e*g 发帖数: 4981 | 29 正常的解释是,只要有一个case需要8次,就是8次。与本题无关。
但就算按你这个逻辑,本题也是一样的。因为8次才能确保拿到确定的结果,你少于8次
,无法确定。
如果是称坏球那种的,是可以蒙的,比如我已知有一个坏球,运气好我拿三个球,两好
一坏,就蒙出来正确答案了。
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是啊,所以每个case都需要》=8次才能下结论吗?你得证明对于各种layout回回都需要 : 》=8次啊。
|
p******g 发帖数: 8316 | 30 你要specify不同cases的不同outcome啊,既不是每回都需要8次,也不是每回都1次,
更不是每回都n^2。而且还要算出概率,需要8次的占多少比例,需要1次的占多少,需
要粗暴穷举的占多少。
这才能衡量出你算法的精确度啊,如果碰巧赶上已经sorted的(given ascending或者
descending)题目中也没这个限制性条件,那就更好办了,都是一次性,有手指头巴拉
巴拉就行了。
这是原题,上面没做任何限制,所以才是open talk,也就是sorted和unsorted的解法
你都得考虑到。
发信人: centralla (central LA), 信区: Military
标 题: 狗家面试题目
发信站: BBS 未名空间站 (Tue Apr 24 20:20:10 2018, 美东)
There are 25 horses. At a time only 5 horses can run in the single race. How
many minimum races are required in all cases to find the top 5 fastest
horses? (No timer
)
【在 e*g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 正常的解释是,只要有一个case需要8次,就是8次。与本题无关。 : 但就算按你这个逻辑,本题也是一样的。因为8次才能确保拿到确定的结果,你少于8次 : ,无法确定。 : 如果是称坏球那种的,是可以蒙的,比如我已知有一个坏球,运气好我拿三个球,两好 : 一坏,就蒙出来正确答案了。
|
|
|
t******0 发帖数: 153 | |
z****l 发帖数: 240 | 32 轮数输错了,我这个实际上也是8次-_-b。重新整理一下:
随机分五组分别比赛,组内排好名次。
第六轮取每组第二名比赛,并按第二名比赛名次将各组横向排序。以下ABCDE分别为各
组头名,F为第六轮比赛最快,J为第六轮比赛最慢。
A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
第六轮比赛结束后所有已知慢于超过5匹马的全部可以淘汰(例如已知Q比AFBGL都慢)
。只剩下:
A B C D E
F G H
K L
P
U
并且可知A为最快,只需要从剩下10个里选前4。把这10个重新分组成5组,组内按已知
顺序排好:
F K B C G
P U D E L
取较快的5匹进行第七轮比赛,取前4名。因为已知F和B都比G快,因此比赛结果只可能
两类:
第一类,前四包含G。要么是FKBG,要么是FBCG,两种情况均可以淘汰3匹。以FKBG为例
,CDE均慢于FKBG,淘汰。那么第八轮只需要用G和KPU比赛取前两名即可。
第二类,前四不包含G,即前四为FKBC,淘汰GL,剩下8匹:
F K B C
P U D E
这时第四名要么是K要么是C,无论哪种情况均可再淘汰两匹。例如C为第四的情况可推
出DE慢于
FKBC,淘汰DE。如K为第四则淘汰PU。
以下以C为第四为例:
F K B C
P U
第七轮的第一排在总排名的第二。第八轮由剩下的五个比赛取前三名。
【在 t******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的每组第二名不要比赛就能得到? : : 慢。
|
t******0 发帖数: 153 | 33 第八次,
依据每条线上的中间值在第七次的比赛结果选择参加第八次比赛的成员
比如:第一线的 1.3 胜了, 那么就让 ·1.5参加 反之 ·让 1.2 参加
这样下来,极端情况下需要第九次。100%可以。
【在 t******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 讲一下第七次, : 1.1 -> 1.2 -> 1.3 -> 1.4 -> 1.5 为第一线 : 1.1 -> 2.1 -> 2.2 -> 2.3 -> 2.4 为第二线 : 1.1 -> 2.1 -> 3.1 -> 3.2 -> 3.3 为第三线 : 1.1 -> 2.1 -> 3.1 -> 4.1 -> 4.2 为第四线 : 1.1 -> 2.1 -> 3.1 -> 4.1 -> 5.1 为第五线 : 本来应该取各线的中间值进行第七次比赛。但第一线,第五线已经比过,所以应该是 : 3.1 2.2 1.3 4.1 5.1 : 但也可能更优化的。 : 这样下来,可能只要8次
|
B*Q 发帖数: 25729 | 34 九次就不用说了
大家已经知道了
能整出个最坏八次的
就是牛逼大佬 |
B*Q 发帖数: 25729 | 35 姐姐
这是马公考试
不是去做PPT
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你要specify不同cases的不同outcome啊,既不是每回都需要8次,也不是每回都1次, : 更不是每回都n^2。而且还要算出概率,需要8次的占多少比例,需要1次的占多少,需 : 要粗暴穷举的占多少。 : 这才能衡量出你算法的精确度啊,如果碰巧赶上已经sorted的(given ascending或者 : descending)题目中也没这个限制性条件,那就更好办了,都是一次性,有手指头巴拉 : 巴拉就行了。 : 这是原题,上面没做任何限制,所以才是open talk,也就是sorted和unsorted的解法 : 你都得考虑到。 : 发信人: centralla (central LA), 信区: Military : 标 题: 狗家面试题目
|
e*g 发帖数: 4981 | 36 已知最优答案不是八次?
【在 B*Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 九次就不用说了 : 大家已经知道了 : 能整出个最坏八次的 : 就是牛逼大佬
|
p******g 发帖数: 8316 | 37 如图,看看面试官真正想看的是啥
【在 B*Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 姐姐 : 这是马公考试 : 不是去做PPT
|
B*Q 发帖数: 25729 | 38 那是撒比
俺手刃过好几个能说会道不能做题的了
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如图,看看面试官真正想看的是啥
|
B*Q 发帖数: 25729 | |
i*****9 发帖数: 3157 | 40 8次是对的,但你的思路是错的。
重点是第6轮应该是各组的第二名比,而不是第一名。按照第六轮结果给组排序之后,
第七轮是 1.4 2.2 3.1 4.1 5.1 比。然后再慢慢分情况讨论。但最终8次是对的。
:刚才蹲厕所的时候
:好好的沿着insider大佬的思路想了想 |
|
|
B*Q 发帖数: 25729 | 41 九虫大佬这个玄乎
俺再想想
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 8次是对的,但你的思路是错的。 : 重点是第6轮应该是各组的第二名比,而不是第一名。按照第六轮结果给组排序之后, : 第七轮是 1.4 2.2 3.1 4.1 5.1 比。然后再慢慢分情况讨论。但最终8次是对的。 : : :刚才蹲厕所的时候 : :好好的沿着insider大佬的思路想了想
|
p******g 发帖数: 8316 | 42 你遇到的这类人本身就傻,不是因为他们不刷题就是傻,他们没拿到offer也不是因为
没把题目刷好。
给你看一看我的biweekly 税后paycheck,我从不刷题,都是靠平时基本功取胜。
【在 B*Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那是撒比 : 俺手刃过好几个能说会道不能做题的了
|
B*Q 发帖数: 25729 | 43 不算多
但是也不重要
俺们这里是讨论茴字有几种写法
你可以另起一楼讨论为什么要写茴字
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你遇到的这类人本身就傻,不是因为他们不刷题就是傻,他们没拿到offer也不是因为 : 没把题目刷好。 : 给你看一看我的biweekly 税后paycheck,我从不刷题,都是靠平时基本功取胜。
|
p******g 发帖数: 8316 | 44 多少算多?
【在 B*Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不算多 : 但是也不重要 : 俺们这里是讨论茴字有几种写法 : 你可以另起一楼讨论为什么要写茴字
|
s******2 发帖数: 1 | 45 不扣税吗
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你遇到的这类人本身就傻,不是因为他们不刷题就是傻,他们没拿到offer也不是因为 : 没把题目刷好。 : 给你看一看我的biweekly 税后paycheck,我从不刷题,都是靠平时基本功取胜。
|
p******g 发帖数: 8316 | 46 当然扣过了。。。,上面不是写了Fe-6/CA-6了吗?那就是withdraw的意思
【在 s******2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不扣税吗
|
B*Q 发帖数: 25729 | 47 重要么?
俺在练习写茴字
你跑来让俺看你的工资单
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 多少算多?
|
i*****9 发帖数: 3157 | 48 这题本质上是那个5分法最坏O(n) 时间找中位数算法的变形,第6轮取各组第一比的话
扔掉的候选矩阵不够大。取第二名比,从3.2到5.5可以全扔掉。
:九虫大佬这个玄乎
:俺再想想 |
d***u 发帖数: 943 | 49 哈哈,姐你真能搞笑。
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你遇到的这类人本身就傻,不是因为他们不刷题就是傻,他们没拿到offer也不是因为 : 没把题目刷好。 : 给你看一看我的biweekly 税后paycheck,我从不刷题,都是靠平时基本功取胜。
|
i*****r 发帖数: 105 | 50 这个就很有意思了。如果这样做的话,这棵决策树就会更加平衡。当然,我还没有自己
试验过。
: 这题本质上是那个5分法最坏O(n) 时间找中位数算法的变形,第6轮取各
组第一
比的话
: 扔掉的候选矩阵不够大。取第二名比,从3.2到5.5可以全扔掉。
: :九虫大佬这个玄乎
: :俺再想想
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题本质上是那个5分法最坏O(n) 时间找中位数算法的变形,第6轮取各组第一比的话 : 扔掉的候选矩阵不够大。取第二名比,从3.2到5.5可以全扔掉。 : : :九虫大佬这个玄乎 : :俺再想想
|
|
|
d***u 发帖数: 943 | 51 他的这个是有序列的标准解法呀
【在 i*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个就很有意思了。如果这样做的话,这棵决策树就会更加平衡。当然,我还没有自己 : 试验过。 : : : 这题本质上是那个5分法最坏O(n) 时间找中位数算法的变形,第6轮取各 : 组第一 : 比的话 : : 扔掉的候选矩阵不够大。取第二名比,从3.2到5.5可以全扔掉。 : : :九虫大佬这个玄乎 : : :俺再想想 :
|
i*****9 发帖数: 3157 | 52 鉴于我这个思路下第七轮取1.3 2.2 3.1 4.1 5.1 都有一种情况8轮搞不定,我谨慎怀
疑最坏情况下小于等于8轮的策略是唯一的。
:这个就很有意思了。如果这样做的话,这棵决策树就会更加平衡。当然,我还没有自
己试验过。
: |
p******g 发帖数: 8316 | 53 有序还解个鸟啊?直接领回家得了
【在 d***u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 他的这个是有序列的标准解法呀
|
d***u 发帖数: 943 | 54 那个大三角的解释也不错,但不如这个规范
【在 i*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个就很有意思了。如果这样做的话,这棵决策树就会更加平衡。当然,我还没有自己 : 试验过。 : : : 这题本质上是那个5分法最坏O(n) 时间找中位数算法的变形,第6轮取各 : 组第一 : 比的话 : : 扔掉的候选矩阵不够大。取第二名比,从3.2到5.5可以全扔掉。 : : :九虫大佬这个玄乎 : : :俺再想想 :
|
d********8 发帖数: 691 | 55 这个看着像正解orz
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题本质上是那个5分法最坏O(n) 时间找中位数算法的变形,第6轮取各组第一比的话 : 扔掉的候选矩阵不够大。取第二名比,从3.2到5.5可以全扔掉。 : : :九虫大佬这个玄乎 : :俺再想想
|
t******0 发帖数: 153 | 56 到第六次为止,是个大三角,
之后取各线的5分法,算法量O(n), 结果应该是9次。
第六次就取每队的第二名参加的思路是不对的。
【在 d***u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那个大三角的解释也不错,但不如这个规范
|
p******g 发帖数: 8316 | 57 哈哈哈
【在 t******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 到第六次为止,是个大三角, : 之后取各线的5分法,算法量O(n), 结果应该是9次。 : 第六次就取每队的第二名参加的思路是不对的。
|
p******g 发帖数: 8316 | 58 我没有嘲笑你的任何意思,是说将军们越算越多了。
【在 t******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 到第六次为止,是个大三角, : 之后取各线的5分法,算法量O(n), 结果应该是9次。 : 第六次就取每队的第二名参加的思路是不对的。
|
d***u 发帖数: 943 | 59 第六轮仍然要取各组第一,成为5个序列半有序
【在 i*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个就很有意思了。如果这样做的话,这棵决策树就会更加平衡。当然,我还没有自己 : 试验过。 : : : 这题本质上是那个5分法最坏O(n) 时间找中位数算法的变形,第6轮取各 : 组第一 : 比的话 : : 扔掉的候选矩阵不够大。取第二名比,从3.2到5.5可以全扔掉。 : : :九虫大佬这个玄乎 : : :俺再想想 :
|
i*****9 发帖数: 3157 | 60 这个问题的标准讨论思路是分4个象限讨论。
简化成三角相当于讨论了第二,第四象限。然后多数人就只展开分析第一象限,把第三
象限也就是 top 5全在第一组的情况给漏了。
:那个大三角的解释也不错,但不如这个规范
: |
|
|
p******g 发帖数: 8316 | 61 恭喜恭喜
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个问题的标准讨论思路是分4个象限讨论。 : 简化成三角相当于讨论了第二,第四象限。然后多数人就只展开分析第一象限,把第三 : 象限也就是 top 5全在第一组的情况给漏了。 : : :那个大三角的解释也不错,但不如这个规范 : :
|
B*Q 发帖数: 25729 | |
i*****9 发帖数: 3157 | 63 你这么闲不如给个把下界也提到8的证明,或者给出最坏情况下是7的解。信息论给出的
最坏下界貌似是7。
:恭喜恭喜
:【 在 insect9 (insect9) 的大作中提到: 】 |
d***u 发帖数: 943 | 64 你妈,你真看懂了吗
第六轮是必须的,删一半的节点
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 恭喜恭喜
|
n********g 发帖数: 6504 | 65 你这个可以做成8次。第六轮是每组第三一起比。第六轮排名第二及以后的就可以排除
了。冒号前为比赛结果。对称的怎么写都不失一般性。冒号后为可能组合:
1.ABCDE
2.FGHIJ
3.KLMNO
4.PQRST
5.UVWXY
6.CHMRW: (AB|FG|KL|PQ|UV)C(DE|FG|KL|PQ|UV); H is impossible, otherwise ABC
and FG already 5
7.1.DFKPU: ABCD(E|F)
7.2.FDKPU: AB(F)C(F(G|D))
8.1. E vs F
8.2. F vs C vs G cs D
你这个比赛安排的问题是如何证明最优没有最差7个的可能比赛方法。
【在 B*Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才蹲厕所的时候 : 好好的沿着insider大佬的思路想了想 : 8次的确是对的 : 废话少说 : 撸起袖子努力整: : 1. 整5次,排出5个小分队,5个一组 : 2. 第六次,每队第一名比一下,按第一名的名次把小分队编号, 1,2,3,4,5 : 1.1>2.1>3.1>4.1>5.1 : n.1>n.2>n.3>n.4>n.5 (n = 1 .. 5) : 3. 第七次 (尼玛, insider 大佬的沈锦斌之处一展无遗)
|
p******g 发帖数: 8316 | 66 我倒真不是解不出来,懒得解了,一般说来,面试的时候,我答出这种程度的,面试官
就算过了,能这么去思考问题的水平,不会解不出来的,这是面试官的主观判断和意识
形态,你要搞清楚,人家不是跟你拼高考,而是拼一种对你这个人够不够聪明的用户体
验,要给你的智商打分,你们都整偏了。
这种类型的题目(不是这道题),之前在斯坦福选课的时候,遇到过,里面分析过程挺
复杂的,不是你们这种纸上谈兵的模式,记得是手写的一整页到两页之间的纸面长度。
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这么闲不如给个把下界也提到8的证明,或者给出最坏情况下是7的解。信息论给出的 : 最坏下界貌似是7。 : : :恭喜恭喜 : :【 在 insect9 (insect9) 的大作中提到: 】
|
B*Q 发帖数: 25729 | 67 第二名一起比
排除的更多
只剩下十个
assuming 1.2 > 2.2 > 3.2 > 4.2 > 5.2
1.1, 1.2, 1.3, 1.4, 1.5
2.1, 2.2
3.1
4.1
5.1
但是还是不能八次搞定
【在 n********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个可以做成8次。第六轮是每组第三一起比。第六轮排名第二及以后的就可以排除 : 了。冒号前为比赛结果。对称的怎么写都不失一般性。冒号后为可能组合: : 1.ABCDE : 2.FGHIJ : 3.KLMNO : 4.PQRST : 5.UVWXY : 6.CHMRW: (AB|FG|KL|PQ|UV)C(DE|FG|KL|PQ|UV); H is impossible, otherwise ABC : and FG already 5 : 7.1.DFKPU: ABCD(E|F)
|
d***u 发帖数: 943 | 68 最少7次还要是特殊结构,应没有通用算法对所有结构有效
【在 n********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个可以做成8次。第六轮是每组第三一起比。第六轮排名第二及以后的就可以排除 : 了。冒号前为比赛结果。对称的怎么写都不失一般性。冒号后为可能组合: : 1.ABCDE : 2.FGHIJ : 3.KLMNO : 4.PQRST : 5.UVWXY : 6.CHMRW: (AB|FG|KL|PQ|UV)C(DE|FG|KL|PQ|UV); H is impossible, otherwise ABC : and FG already 5 : 7.1.DFKPU: ABCD(E|F)
|
i*****9 发帖数: 3157 | 69 马工面试出这种题纯粹吃饱了撑的。。。。20年前的微软才喜欢考这种数学智力题。
:我倒真不是解不出来,懒得解了,一般说来,面试的时候,我答出这种程度的,面试
官就算过了,能这么去思考问题的水平,不会解不出来的,这是面试官的主观判断和意
识形态,你要搞清楚,人家不是跟你拼高考,而是拼一种对你这个人够不够聪明的用户
体验,要给你的智商打分,你们都整偏了。
: |
p******g 发帖数: 8316 | 70 这个结论不就是我最早给出来的思路吗?
所以说面试不是真让你做题算出最后一个数字结果出来,你们自己反复验证过了,任何
数字(5,6,7,8,9)都无法涵盖所有其他cases
就是考核你思考这类问题的思路和对不同算法不同cases的理解深度,都是基本功。
靠刷题,装不出来的,很快露馅
【在 d***u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最少7次还要是特殊结构,应没有通用算法对所有结构有效
|
|
|
i*****9 发帖数: 3157 | 71 给一种8次搞不定的吧,我验算一下。
有几种情况确实比较 tricky但8次都能搞定。
:第二名一起比
:排除的更多 |
d********8 发帖数: 691 | 72 3.2不能拿掉吧
【在 B*Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二名一起比 : 排除的更多 : 只剩下十个 : assuming 1.2 > 2.2 > 3.2 > 4.2 > 5.2 : 1.1, 1.2, 1.3, 1.4, 1.5 : 2.1, 2.2 : 3.1 : 4.1 : 5.1 : 但是还是不能八次搞定
|
t******0 发帖数: 153 | 73 你要注意 assuming 1.2 > 2.2 > 3.2 > 4.2 > 5.2
并不能推出 1.1 >2.1 > 3.1 > 4.1 > 5.1
所以第6轮第二名比,或者第三名比的思路都不可取。
【在 B*Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二名一起比 : 排除的更多 : 只剩下十个 : assuming 1.2 > 2.2 > 3.2 > 4.2 > 5.2 : 1.1, 1.2, 1.3, 1.4, 1.5 : 2.1, 2.2 : 3.1 : 4.1 : 5.1 : 但是还是不能八次搞定
|
i*****9 发帖数: 3157 | 74 你是觉得最坏情况下需要的步数超过9?
:这个结论不就是我最早给出来的思路吗?
:所以说面试不是真让你做题算出最后一个数字结果出来,你们自己反复验证过了,任
何数字(5,6,7,8,9)都无法涵盖所有其他cases |
p******g 发帖数: 8316 | 75 这种题目需要证明各种layout下的结论都是minimum,还有推论,绝不是这里算8次还是
9次的这么点含金量。当时是一堆数学公式做推导来支撑每一个case的结论的,可复杂
了。
面试就是考察你思考这种无解或多解题目的视角而已,哪儿能真让你算半天
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 马工面试出这种题纯粹吃饱了撑的。。。。20年前的微软才喜欢考这种数学智力题。 : : :我倒真不是解不出来,懒得解了,一般说来,面试的时候,我答出这种程度的,面试 : 官就算过了,能这么去思考问题的水平,不会解不出来的,这是面试官的主观判断和意 : 识形态,你要搞清楚,人家不是跟你拼高考,而是拼一种对你这个人够不够聪明的用户 : 体验,要给你的智商打分,你们都整偏了。 : :
|
d***u 发帖数: 943 | 76 第六次很关键,要能看出来实际上是个二分法
【在 t******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 到第六次为止,是个大三角, : 之后取各线的5分法,算法量O(n), 结果应该是9次。 : 第六次就取每队的第二名参加的思路是不对的。
|
d********8 发帖数: 691 | 77 是2.3
【在 d********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 3.2不能拿掉吧
|
i*****9 发帖数: 3157 | 78 1.1 1.2 2.1 2.2 3.1 都大于3.2 已经5个了
:3.2不能拿掉吧
:【 在 BCQ (不差钱) 的大作中提到: 】 |
i*****r 发帖数: 105 | 79 7.3 FKPUD, how to do 8?
【在 n********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个可以做成8次。第六轮是每组第三一起比。第六轮排名第二及以后的就可以排除 : 了。冒号前为比赛结果。对称的怎么写都不失一般性。冒号后为可能组合: : 1.ABCDE : 2.FGHIJ : 3.KLMNO : 4.PQRST : 5.UVWXY : 6.CHMRW: (AB|FG|KL|PQ|UV)C(DE|FG|KL|PQ|UV); H is impossible, otherwise ABC : and FG already 5 : 7.1.DFKPU: ABCD(E|F)
|
d********8 发帖数: 691 | 80 转一下,我想说2.3
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1.1 1.2 2.1 2.2 3.1 都大于3.2 已经5个了 : : :3.2不能拿掉吧 : :【 在 BCQ (不差钱) 的大作中提到: 】
|
|
|
i*****9 发帖数: 3157 | 81 你的逻辑是错的。这类问题都是说下一步的策略是根据之前的结果来确定,然后设计每
一步的策略函数,要求最坏情况下的步数最少。
对于这道题来说,可以构造出一个策略函数,使得最坏情况下需要的步数是8。
:这种题目需要证明各种layout下的结论都是minimum,还有推论,绝不是这里算8次还
是9次的这么点含金量。当时是一堆数学公式做推导来支撑每一个case的结论的,可复杂
:了。 |
t******0 发帖数: 153 | 82 到第六步大三角成形后,如果要得到8步完成
就得找比5分法更有效的。
排序当中,比5分法更好的方法可以survey一下。 |
p******g 发帖数: 8316 | 83 记得有一个公式,里面有各种参数,往里套,就能直接得出“某种case下”的结果。你
们这种算了半天的本质就是在推导那个公式的过程,只不过是外行瞎推而已。
知道这个公式的人,肯定是在校生了。毕业那么久的谁记得住,都是教授在黑板上给的
,笔记上的,教材里推导出来的。面试官一眼就看出来是刚从学校里学来的,这是面试
官的经验。
这种题目的结果最好是上机才知道最后的准确数字,因为里面有几个inner iteration
和outer iteration,然后你要做一个total count的跟踪,手算不准的。当时交作业的
时候,纸面上写出理论分析过程,然后上机操作出结果,根据结果来反推公式的合理性
.
这题目根本就不是一道算术题,涉及到你对好几个算法的理解和使用,还有你对
iteration的操作,正儿八经属于一个project。
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你是觉得最坏情况下需要的步数超过9? : : :这个结论不就是我最早给出来的思路吗? : :所以说面试不是真让你做题算出最后一个数字结果出来,你们自己反复验证过了,任 : 何数字(5,6,7,8,9)都无法涵盖所有其他cases
|
d***u 发帖数: 943 | 84 8次是通用算法,没有结构例外,可以证明
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给一种8次搞不定的吧,我验算一下。 : 有几种情况确实比较 tricky但8次都能搞定。 : : :第二名一起比 : :排除的更多
|
p******g 发帖数: 8316 | 85 你说的是hidden markov model吗?
复杂
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的逻辑是错的。这类问题都是说下一步的策略是根据之前的结果来确定,然后设计每 : 一步的策略函数,要求最坏情况下的步数最少。 : 对于这道题来说,可以构造出一个策略函数,使得最坏情况下需要的步数是8。 : : :这种题目需要证明各种layout下的结论都是minimum,还有推论,绝不是这里算8次还 : 是9次的这么点含金量。当时是一堆数学公式做推导来支撑每一个case的结论的,可复杂 : :了。
|
i*****9 发帖数: 3157 | 86 第7步必须是 1.4 2.2 3.1 4.1 5.1
然后需要讨论第七步结果的前三名的排列,3.1 4.1 5.1 可以看作一类, 一共6+3+3+1
=13种情况,差不多要分8种左右不同策略来设计第八轮。
:第二名一起比
:排除的更多 |
d***u 发帖数: 943 | 87 你丫要承认一回智商低会死吗,我们都承认你是斯坦福高管红二代了,你就让我们玩茴
香豆吧
iteration
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 记得有一个公式,里面有各种参数,往里套,就能直接得出“某种case下”的结果。你 : 们这种算了半天的本质就是在推导那个公式的过程,只不过是外行瞎推而已。 : 知道这个公式的人,肯定是在校生了。毕业那么久的谁记得住,都是教授在黑板上给的 : ,笔记上的,教材里推导出来的。面试官一眼就看出来是刚从学校里学来的,这是面试 : 官的经验。 : 这种题目的结果最好是上机才知道最后的准确数字,因为里面有几个inner iteration : 和outer iteration,然后你要做一个total count的跟踪,手算不准的。当时交作业的 : 时候,纸面上写出理论分析过程,然后上机操作出结果,根据结果来反推公式的合理性 : . : 这题目根本就不是一道算术题,涉及到你对好几个算法的理解和使用,还有你对
|
i*****9 发帖数: 3157 | 88 我只能给出8次的构造,但给不出最坏下界是8的证明。
:8次是通用算法,没有结构例外,可以证明
: |
d***u 发帖数: 943 | 89 第七步是1.2, 1.3, 2.1, 2.2, 3.1
+1
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第7步必须是 1.4 2.2 3.1 4.1 5.1 : 然后需要讨论第七步结果的前三名的排列,3.1 4.1 5.1 可以看作一类, 一共6+3+3+1 : =13种情况,差不多要分8种左右不同策略来设计第八轮。 : : :第二名一起比 : :排除的更多
|
i*****9 发帖数: 3157 | 90 这个分法如果能做出来的话,第八步的分析应该比我的思路简单。
:第七步是1.2, 1.3, 2.1, 2.2, 3.1
: |
|
|
B*Q 发帖数: 25729 | 91 你说得对
2.3 不能拿掉
[在 daydream08 (daydream08) 的大作中提到:]
:转一下,我想说2.3 |
d********8 发帖数: 691 | 92 这位大佬还是先说下第六步到底是比第二还是第一吧
【在 d***u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第七步是1.2, 1.3, 2.1, 2.2, 3.1 : : +1
|
i*****9 发帖数: 3157 | 93 不对,你这个解中,第六步是比较第二名还是第一名?第二名的话,4.1 5.1和3.1的关
系是不确定的,必须在第七轮参与排序。
:第七步是1.2, 1.3, 2.1, 2.2, 3.1
: |
d***u 发帖数: 943 | 94 第六步必须是比第一名,没别的通用算法
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不对,你这个解中,第六步是比较第二名还是第一名?第二名的话,4.1 5.1和3.1的关 : 系是不确定的,必须在第七轮参与排序。 : : :第七步是1.2, 1.3, 2.1, 2.2, 3.1 : :
|
t******0 发帖数: 153 | 95 可以把问题简单化一下,比如先看一下 3X3 的情况,或者4X4 |
d********8 发帖数: 691 | 96 这么想是最自然的,但第八步能搞定?1.1 2.1 3.1最大怎么搞?
【在 d***u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第六步必须是比第一名,没别的通用算法
|
d***u 发帖数: 943 | 97 看错了,改一下
去2.1,3.1,1.3,加4.1,5.1,4.2,假设1.3 最小,第八轮要去第七轮的最小
不太好解释,自己画吧
【在 d********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这么想是最自然的,但第八步能搞定?1.1 2.1 3.1最大怎么搞?
|
i*****r 发帖数: 105 | 98 Enumerate all cases after 7th race of 14, 22, 31, 41, 51. It should work.
11 12 13 14 15
21 22 23
31
41
51
7th result 14 22
8th race 15 21
7th result 14 31
8th race 15 21 31
7th result 22 14
8th race 13 23
7th result 22 31
8th race 13 23 31
7th result 31 14
8th race 14 21
7th result 31 22
8th race 13 22
7th result 31 41 !51
8th race 13 21 41
7th result 31 41 51
8th race 12 13 21 41 51
+1
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第7步必须是 1.4 2.2 3.1 4.1 5.1 : 然后需要讨论第七步结果的前三名的排列,3.1 4.1 5.1 可以看作一类, 一共6+3+3+1 : =13种情况,差不多要分8种左右不同策略来设计第八轮。 : : :第二名一起比 : :排除的更多
|
t******0 发帖数: 153 | 99 搜了一下,你妈一大堆一样的问题。
当中说的比较详细的是这儿
http://hxraid.iteye.com/blog/662643
不过,最坏也是9次。
而且我认为不是最优方法。 |
d***u 发帖数: 943 | 100 你妈,不会吧? 我的方法不难呀?哪位看出漏洞来了?
【在 t******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 搜了一下,你妈一大堆一样的问题。 : 当中说的比较详细的是这儿 : http://hxraid.iteye.com/blog/662643 : 不过,最坏也是9次。 : 而且我认为不是最优方法。
|
|
|
p******g 发帖数: 8316 | 101 公式找到了, n=5, k=3, r=2,
k=5的情况另算。
anyway,就是告诉你们,这是正儿八经的公式推导。
iteration
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 记得有一个公式,里面有各种参数,往里套,就能直接得出“某种case下”的结果。你 : 们这种算了半天的本质就是在推导那个公式的过程,只不过是外行瞎推而已。 : 知道这个公式的人,肯定是在校生了。毕业那么久的谁记得住,都是教授在黑板上给的 : ,笔记上的,教材里推导出来的。面试官一眼就看出来是刚从学校里学来的,这是面试 : 官的经验。 : 这种题目的结果最好是上机才知道最后的准确数字,因为里面有几个inner iteration : 和outer iteration,然后你要做一个total count的跟踪,手算不准的。当时交作业的 : 时候,纸面上写出理论分析过程,然后上机操作出结果,根据结果来反推公式的合理性 : . : 这题目根本就不是一道算术题,涉及到你对好几个算法的理解和使用,还有你对
|
p******g 发帖数: 8316 | 102 公式计算如下:
Given n=5, n^2=25 horses, n horses each group, k fastest horses
Ask: minimum number of races
k=3,n+2=7 races
k=4, <= n+2+1(or) races
k=5, <= n+2+1+1(or) races
答案是8 or 9 races, 针对given unsorted list 和 top 5 horses 的case |
t******0 发帖数: 153 | 103 你这种公式很好理解,但不适合这道题,这儿K=5 ,
按公式n = 14 马的数量要196才行。
这个地方有个8轮的解答。
https://blog.csdn.net/flyinghearts/article/details/6053876
但我认为他第7轮没有全部分析,有漏的。所以答案不一定对。
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 公式找到了, n=5, k=3, r=2, : k=5的情况另算。 : anyway,就是告诉你们,这是正儿八经的公式推导。 : : iteration
|
p******g 发帖数: 8316 | 104 7是肯定不对了,k=4的时候,就是7-8了,哈哈哈
应该是8-9
另外,那个公式只是针对k=3的,k=5就不适用了。
【在 t******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这种公式很好理解,但不适合这道题,这儿K=5 , : 按公式n = 14 马的数量要196才行。 : 这个地方有个8轮的解答。 : https://blog.csdn.net/flyinghearts/article/details/6053876 : 但我认为他第7轮没有全部分析,有漏的。所以答案不一定对。
|
t******0 发帖数: 153 | |
p******g 发帖数: 8316 | 106 对,9是at most,有些用不到9次,有8次也能搞定的cases,但7次肯定不行。
【在 t******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 结论: MAX 9次 结束!
|
L******8 发帖数: 1211 | 107 我算的是九
说说我的算法:
25这个数,
居中为13
两边各12个数
如果把上次的中位马,放到下一次中,迭代六次
就能把25马都试了
注意,
这么做我们多利用了一个信息,
就是把组之间的快慢关系也使用了
这样,六组后的最坏情况,
就是中位马两边各12匹
但是这12匹呈六对,每对有大小关系
而这种组合通常需要三次比赛确定
最后一共是九次比赛
完毕。
我认为建立组别间快慢关系是节省一次比赛的关键。
这是信息论。完全可以写成通解形式。 |
d***u 发帖数: 943 | 108 你妈,书读成你这样也算是不容易了,斯坦福也不能治智商低
个别结构7次可解,通用结构8次可解。对你这种智商的可能要9次。
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对,9是at most,有些用不到9次,有8次也能搞定的cases,但7次肯定不行。
|
p******g 发帖数: 8316 | 109 明天早晨起来再投诉你,跪安吧
【在 d***u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你妈,书读成你这样也算是不容易了,斯坦福也不能治智商低 : 个别结构7次可解,通用结构8次可解。对你这种智商的可能要9次。
|
d***u 发帖数: 943 | 110 你妈,这个也投诉。我只不过陈述下事实。要不你证明给哥看你不智商低,把你的8次
不能给大家说说看,或者把我的证明推翻
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 明天早晨起来再投诉你,跪安吧
|
|
|
p******g 发帖数: 8316 | 111 我投诉的是你跟在我后面发大量的无关主题贴进行恶意挑衅,包括其他主题下的。
不要以为网络是虚拟社区,就可以为所欲为了
【在 d***u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你妈,这个也投诉。我只不过陈述下事实。要不你证明给哥看你不智商低,把你的8次 : 不能给大家说说看,或者把我的证明推翻
|
d***u 发帖数: 943 | 112 好,只要不是投诉我说你低智商就可以,其他的我都接受。
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我投诉的是你跟在我后面发大量的无关主题贴进行恶意挑衅,包括其他主题下的。 : 不要以为网络是虚拟社区,就可以为所欲为了
|
d***u 发帖数: 943 | 113 好,只要不是投诉我说你低智商就可以,其他的我都接受。我就喜欢看你得帖子。有趣。
好了,我睡觉去了。
【在 p******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我投诉的是你跟在我后面发大量的无关主题贴进行恶意挑衅,包括其他主题下的。 : 不要以为网络是虚拟社区,就可以为所欲为了
|
t******0 发帖数: 153 | 114 追加一下,
8次出来的前5,不能全部明确分清谁快谁慢。只能概括说这5匹是最快的。
9次出来的,能全部分清。 |
d***u 发帖数: 943 | 115 都能。举个不能的例子。
【在 t******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 追加一下, : 8次出来的前5,不能全部明确分清谁快谁慢。只能概括说这5匹是最快的。 : 9次出来的,能全部分清。
|
g******e 发帖数: 3760 | 116 拉出来没有?不要耽误正事。
:刚才蹲厕所的时候
:好好的沿着insider大佬的思路想了想 |
t****n 发帖数: 10724 | 117 8次是对的!
【在 B*Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才蹲厕所的时候 : 好好的沿着insider大佬的思路想了想 : 8次的确是对的 : 废话少说 : 撸起袖子努力整: : 1. 整5次,排出5个小分队,5个一组 : 2. 第六次,每队第一名比一下,按第一名的名次把小分队编号, 1,2,3,4,5 : 1.1>2.1>3.1>4.1>5.1 : n.1>n.2>n.3>n.4>n.5 (n = 1 .. 5) : 3. 第七次 (尼玛, insider 大佬的沈锦斌之处一展无遗)
|
i*****9 发帖数: 3157 | 118 差不多就是这样,最 tricky 的应该是最后一个 case, 结果没错。其他的我没细看。
辛苦您单发一贴让这帮人找 bug 吧。
:Enumerate all cases after 7th race of 14, 22, 31, 41, 51. It should work.
: |
i*****9 发帖数: 3157 | 119 8次只能知道top 5是哪些,1到5的顺序不一定知道。要给出1到5的排序需要9次
:都能。举个不能的例子。
: |
L******8 发帖数: 1211 | 120 8次是怎么知道前五的
虚心求解释
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 8次只能知道top 5是哪些,1到5的顺序不一定知道。要给出1到5的排序需要9次 : : :都能。举个不能的例子。 : :
|
|
|
i*****9 发帖数: 3157 | 121 97楼 insider 给出的解。
第六步是各组第二比赛
:8次是怎么知道前五的
: |
L******8 发帖数: 1211 | 122 那我给你第七步
31 41 51 14 22
接下来第八步比哪些?
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 97楼 insider 给出的解。 : 第六步是各组第二比赛 : : :8次是怎么知道前五的 : :
|
i*****9 发帖数: 3157 | 123 第八轮 12 13 21 41 51
:那我给你第七步
: |
L******8 发帖数: 1211 | 124 那么如果现在大小是
21 12 13 41 51
前五是哪些?
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第八轮 12 13 21 41 51 : : :那我给你第七步 : :
|
L******8 发帖数: 1211 | 125 这时候11和21大小还没有比呢
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第八轮 12 13 21 41 51 : : :那我给你第七步 : :
|
O*******n 发帖数: 22 | 126 妈的千老我都看不下去了…
【在 B*Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才蹲厕所的时候 : 好好的沿着insider大佬的思路想了想 : 8次的确是对的 : 废话少说 : 撸起袖子努力整: : 1. 整5次,排出5个小分队,5个一组 : 2. 第六次,每队第一名比一下,按第一名的名次把小分队编号, 1,2,3,4,5 : 1.1>2.1>3.1>4.1>5.1 : n.1>n.2>n.3>n.4>n.5 (n = 1 .. 5) : 3. 第七次 (尼玛, insider 大佬的沈锦斌之处一展无遗)
|
i*****9 发帖数: 3157 | 127 不需要比呀,不需要给出前5之内的排名
:这时候11和21大小还没有比呢
:【 在 insect9 (insect9) 的大作中提到: 】 |
i*****9 发帖数: 3157 | 128 前五 11 12 13 21 31 前五内的顺序未知
:那么如果现在大小是
: |
d***u 发帖数: 943 | 129 操,还在磨叽这个问题呀,仔细看看我的第七步
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 前五 11 12 13 21 31 前五内的顺序未知 : : :那么如果现在大小是 : :
|
O*******n 发帖数: 22 | 130 不碰运气的话,前六次必须,五次组内排序,一次组排序1>5。之后就从结果由简到繁
排除。最好情况是前五在同一组,所以用1.5跟2-4的第一名比,整堆排除。最少当然是
七次。
【在 B*Q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才蹲厕所的时候 : 好好的沿着insider大佬的思路想了想 : 8次的确是对的 : 废话少说 : 撸起袖子努力整: : 1. 整5次,排出5个小分队,5个一组 : 2. 第六次,每队第一名比一下,按第一名的名次把小分队编号, 1,2,3,4,5 : 1.1>2.1>3.1>4.1>5.1 : n.1>n.2>n.3>n.4>n.5 (n = 1 .. 5) : 3. 第七次 (尼玛, insider 大佬的沈锦斌之处一展无遗)
|
|
|
L******8 发帖数: 1211 | 131 ……我太实诚了
以为top5必须是有顺序啊
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不需要比呀,不需要给出前5之内的排名 : : :这时候11和21大小还没有比呢 : :【 在 insect9 (insect9) 的大作中提到: 】
|
s*****V 发帖数: 21731 | 132 其实用小组第三比赛更精明
第6轮,小组第三,假设1.3, 2.3, 3.3, 4.3, 5.3的顺序,这样除了第一组,其它
4组的后3名都淘汰了。第一组依然保有5名。
第7轮,1.3,2.1,3.1,4.1,5.1 这轮赛完,再根据情况决定第8轮。前三名直接竞技
,后两名直接淘汰
1. 如果1.3 不在前三,则加入1.1, 1.2 和其它竞技组的第二
2.如果1.3在前三,则加入1.3,1.4和其它竞技组的第二
第八轮再选前两名。
【在 i*****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 97楼 insider 给出的解。 : 第六步是各组第二比赛 : : :8次是怎么知道前五的 : :
|