b****y
发帖数: 169 | 1 这round2的题很有意思啊。
可惜我一道也没做出来。
第一题居然要用FFT。
后两道都是DP，我连高手们的源代码都看不懂。
有高人能解释下吗？ |
t****t
发帖数: 6806 | 2 我今天中午吃饭的时候听同事说了----你不是我同事吧?
【在 b****y 的大作中提到】
: 这round2的题很有意思啊。
: 可惜我一道也没做出来。
: 第一题居然要用FFT。
: 后两道都是DP，我连高手们的源代码都看不懂。
: 有高人能解释下吗？
|
N***m
发帖数: 4460 | 3 haha，估计大部分人都做不出来。
转别人的一句话：Not all programmers are created equal。
【在 b****y 的大作中提到】
: 这round2的题很有意思啊。
: 可惜我一道也没做出来。
: 第一题居然要用FFT。
: 后两道都是DP，我连高手们的源代码都看不懂。
: 有高人能解释下吗？
|
t****t
发帖数: 6806 | 4 第一题我同事提示我要卷积, 而且是实数域卷积, 我还想了半天才想明白怎么卷法.
MMD亏我还是做EE的.
【在 N***m 的大作中提到】
: haha，估计大部分人都做不出来。
: 转别人的一句话：Not all programmers are created equal。
|
N***m
发帖数: 4460 | 5 有人贴题目吗？
是不是facebook上的，可惜我还没账号，是不是太老土了？
【在 t****t 的大作中提到】
: 第一题我同事提示我要卷积, 而且是实数域卷积, 我还想了半天才想明白怎么卷法.
: MMD亏我还是做EE的.
|
N***m
发帖数: 4460 | 6 卷积俺n>10年前似乎学/用过，之后就很少听说了，呵呵
【在 t****t 的大作中提到】
: 第一题我同事提示我要卷积, 而且是实数域卷积, 我还想了半天才想明白怎么卷法.
: MMD亏我还是做EE的.
|
t****t
发帖数: 6806 | 7 给定一个大质数P(250K左右)以及两个长序列A和B(长度10^7左右), 以及threshold 0<=
L
对每个(A[i], B[j])定义C[i][j]=A[i]*B[j] mod P. 求满足C[i][j]>=L的组合(i, j)
的个数.
【在 N***m 的大作中提到】
: 有人贴题目吗？
: 是不是facebook上的，可惜我还没账号，是不是太老土了？
|
t****t
发帖数: 6806 | 8 你不是EE的当然不常用. 我们做信号处理的, 做卷积就跟写i++一样平常.
【在 N***m 的大作中提到】
: 卷积俺n>10年前似乎学/用过，之后就很少听说了，呵呵
|
b****y
发帖数: 169 | 9 第二题： 给定一个字符串，长度<60，只含'a','b'。定义一个操作(i, j, c)为：吧从
i到j（含）的子串用一个字符c替换。c是该子串里的任一字符（当然只能是'a'，'b'）
。子串长度>=2 (i.e. i
比如：输入aab，可能的操作序列为：
1.啥也不干
2.[aab]->a
3.[aab]->b
4.[aa]b->ab
5.[aa]b->[ab]->a
6.[aa]b->[ab]->b
7.a[ab]->aa
8.a[ab]->[aa]->a
9.a[ab]->ab
10.a[ab]->[ab]->a
11.a[ab]->[ab]->b
所以答案是11 |
b****y
发帖数: 169 | 10 第三题：一个整数列长度为N,最小的数在A和B之间，最大的在C和D之间。而且这N个数
不含公共因子。输出这样的数列有多少。N,A，B,C,D都在1和1e6之间。 |
|
|
d********e
发帖数: 132 | 11 在哪能看到高手们的源代码和相应的讨论。 谢谢
【在 b****y 的大作中提到】
: 这round2的题很有意思啊。
: 可惜我一道也没做出来。
: 第一题居然要用FFT。
: 后两道都是DP，我连高手们的源代码都看不懂。
: 有高人能解释下吗？
|
b****y
发帖数: 169 | |
t****t
发帖数: 6806 | 13 第一题我跟同事讨论了下思路, 做卷积确实是神来之笔, 没人提示别说一个小时, 一个
月我也想不到
【在 b****y 的大作中提到】
: 这是看题和源代码的link。也许只有参赛的人才能看。
: http://www.facebook.com/hackercup/scoreboard.php/?round=1787673
: 但是没有人讨论，所以我才跑到这里来问。
|
b****y
发帖数: 169 | |
g*********s
发帖数: 1782 | 15 太猛了。让我想起当年的数学奥赛，还没培训。
【在 b****y 的大作中提到】
: 这round2的题很有意思啊。
: 可惜我一道也没做出来。
: 第一题居然要用FFT。
: 后两道都是DP，我连高手们的源代码都看不懂。
: 有高人能解释下吗？
|
r*******n
发帖数: 3020 | 16 我昨天刚杀掉了facebook帐号
【在 N***m 的大作中提到】
: 有人贴题目吗？
: 是不是facebook上的，可惜我还没账号，是不是太老土了？
|
N***m
发帖数: 4460 | 17 题目太难，不去想也罢！
【在 g*********s 的大作中提到】
: 太猛了。让我想起当年的数学奥赛，还没培训。
|
t****t
发帖数: 6806 | 18 昨天想第一题已经死掉我好多脑细胞了, 不想了.
【在 b****y 的大作中提到】
: 赶紧找你的同事讨论一下2，3题吧！
|
M**u
发帖数: 10158 | 19 想参加，结果资格赛举行也太早恶劣。。。
【在 N***m 的大作中提到】
: 题目太难，不去想也罢！
|
P********e
发帖数: 2610 | 20 是facebook的面试?
【在 b****y 的大作中提到】
: 这round2的题很有意思啊。
: 可惜我一道也没做出来。
: 第一题居然要用FFT。
: 后两道都是DP，我连高手们的源代码都看不懂。
: 有高人能解释下吗？
|
b****y
发帖数: 169 | 21 又研究了一下高手的code，终于看懂了第三题。发现第三题不是DP，主要用了一些集合
论。 |
