r***u
发帖数: 241 | |
i**********e
发帖数: 1145 | 2 是好难啊... 5555
第三题基本思路有了，但是最后关系到好复杂的组合数学，不知道怎么解啊
Two bonus assignments are different if at least one worker gets different
bonus in each assignment.
这句话什么意思？
最后一个 sample test case 也给得太大了吧。。。。。。。。。。。。。。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
r***u
发帖数: 241 | 3 是啊，直觉觉得第三题最容易，解出来的人也最多，可是具体做起来还是没思路，取值
范围太大了。
【在 i**********e 的大作中提到】
: 是好难啊... 5555
: 第三题基本思路有了，但是最后关系到好复杂的组合数学，不知道怎么解啊
: Two bonus assignments are different if at least one worker gets different
: bonus in each assignment.
: 这句话什么意思？
: 最后一个 sample test case 也给得太大了吧。。。。。。。。。。。。。。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
i**********e
发帖数: 1145 | 4 看了看 topcoder 的讨论，第三题似乎是用 inclusion-exclusion principle 来排除
多余的组合，看来关系还是比较棘手的。出的题目也真是太难了，说要派 300 件
tshirt 给前 300 名，结果只有 150 人答对至少一题...
这轮看来是专门针对那些专做 topcoder 的选手，看看第一题的讨论就知道，听说要用
FFT 或者 Karatsuba algorithm 来做快速乘法。看了排第一名大牛级别的代码，还真
不是一般的复杂...
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
f*******4
发帖数: 1401 | 5 顶一下参赛的大牛们
苦苦地写dissertation中... |
p*****r
发帖数: 1883 | 6
第三题确实是 inclusion-exclusion，当时猛人大头同志指导推算这个公式，得到一个
递归解，就按照素数的组合来，先建立个素数表，把所有情况里单个素数的去掉，
素数的2个组合加回来，三个组合再去掉，递归写起来就行。过了example，包括最后
那个141990那个，结果屁颠屁颠下载数据，我艹，好慢，内牛了，时间来不及。后来
看别人的代码，公式和算法都一样，不过他们不是拿ABCD除那个素数，而是先乘好了
再减，速度快了不少。
第一个题目，其实有不要做乘法的办法，欧拉某定理的推论，如果a^(p-1)=1 mod P,
那么a*a^(p-2)=1 mod P，那么，你要找a_i, b_j这一对满足ab mod P = n
那 b也就是n*a^(p-2)，那么找每个b_j就只要在a^(p-2)到(L-1)*a^(p-2)之间搜索一下
就行了，这个时间复杂度是O(P*L)，比O(N*M)快许多。不过这个是结束之后才谷歌出来
的，现场显然不会做啊。
第二个题。。。看不懂。果断放弃。
老了啊，要是放我高中的时候，这些题还不随便上。。。。
【在 i**********e 的大作中提到】
: 看了看 topcoder 的讨论，第三题似乎是用 inclusion-exclusion principle 来排除
: 多余的组合，看来关系还是比较棘手的。出的题目也真是太难了，说要派 300 件
: tshirt 给前 300 名，结果只有 150 人答对至少一题...
: 这轮看来是专门针对那些专做 topcoder 的选手，看看第一题的讨论就知道，听说要用
: FFT 或者 Karatsuba algorithm 来做快速乘法。看了排第一名大牛级别的代码，还真
: 不是一般的复杂...
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
l********n
发帖数: 9 | 7 Problem 1 seems asking for FFT, the O(N^1.5) algorithms is too slow. In fact
, I tested Petr's solution and it takes around 8m to finish. He must have
other tricks like running testcases in parallel to finish it within 6min.
Problem 3 asks for Mobius function which I have no idea before.
Among over 2700 participants, only 150 have solved at least one problem. It
is hard, especially compared to previous rounds that most problems are
trivial. |
