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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是好难啊... 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看了看 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. |