作者shaopin (problem maker)
看板Prob_Solve
标题[问题] Interview street: zombie march
时间Tue Oct 9 12:48:44 2012
题目:
http://goo.gl/pS7Ru (放心 是真正的url)
这题是说 纽约市有N个junction (其实就是graph上的vertex)
整个graph有 M个edge, 是双向的..
每个node上有initial数量的zombie, 这些zombie每一个
单位时间都会随机选一个该node的neighbor向之移动
k是总共的时间
题目是要问: 最後 有最多zombie的五个node上的zombie数量
小弟我写出了解法,
https://gist.github.com/3856634
但是光是在test 五个case就只有过了前三个case 其他都应该TLE
在自己的电脑上run 到最後可以run出正确答案, 显然我的algorithm还不够好
我的做法是brute force每一个时间都计算最後该时间expected
number of zombies. 但显然有更好的做法
在此请教不知道更快的做法是否是跟那只选五个最多的zombie node
有关? 但我还是不知道怎麽做??
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 69.110.234.65
1F：推 singlovesong:这题目真有趣! 但是不会做Orz 10/09 15:25
3F：→ stimim:还要再实作稀疏矩阵 orz 10/09 22:52
4F：→ suhorng:是说我很好奇有最多zombie的五个node是 "最初" 有最多 10/09 22:59
5F：→ suhorng:还是最後 "期望" 有最多的五个? 10/09 22:59
6F：→ suhorng:如果是最後 "期望最多的五个" 要怎麽做@@? 10/09 23:00
7F：推 stimim:先做出 markov matrix M, 初始为 z(0) => z(t)=(M^t)*z(0) 10/09 23:13
8F：→ stimim:M是 n by n ，z(i) 是长度为 n 的向量 10/09 23:14
9F：推 suhorng:n,m到10^5, 2*10^5吗？这样(稀疏)矩阵乘法也OK? 10/09 23:42
10F：推 stimim:不确定，要试试看 orz 10/09 23:53
11F：→ shaopin:suhorng大, 是期望最後的最多zombie的五个node... 10/10 00:34
12F：→ shaopin:bruteforce很执白, 就是隔壁邻点的殭屍平均分散然後本点 10/10 00:36
13F：→ shaopin:再加总... 10/10 00:36
14F：推 Arton0306:麻烦的是 矩阵到10^10个元素 次方数又到10^7 10/10 01:24
15F：→ Arton0306:次方还要化为diagonal matrix去解 不知怎利用sparse性质 10/10 01:26
16F：→ shaopin:各位同学, 有没有解法是适合interview的?一般interview 10/10 02:58
17F：→ shaopin:碰到这个问题如果还要实作矩阵 应该不太多见 10/10 02:59
18F：→ suhorng:次方那边其实不用在意, 因为又反覆平方法, 最多只要做lg k 10/10 07:43
19F：→ suhorng:量级的个数 10/10 07:43
21F：推 DJWS:我觉得症结点在於只需要前五名 所以应该可以简化很多东西 10/10 09:00
22F：→ DJWS:如果直接用矩阵次方 由於矩阵太大 时间一定会爆炸的 10/10 09:01
23F：推 Arton0306:我觉得最後的稳定状态是 #zombie/#node 也就是想成分子 10/10 11:05
24F：→ Arton0306:扩散 最後会变平均 只是在此之前还是要用暴力法跑 10/10 11:07
25F：→ Arton0306:每做完一个step就检查是否进入稳定状态 10/10 11:08
26F：推 Arton0306:发现这样也有问题 zombie不会留在原地 一些case会错... 10/10 11:18
27F：推 stimim:Accept 了... 结果他的测资好像都会进入稳定态 orz 10/10 11:20
28F：推 stimim:也有可能是因为要四舍五入到整数，所以进入稳定态的时间会 10/10 11:22
29F：→ stimim:大幅减少 ?? 10/10 11:22
30F：推 Arton0306:cool! 解法是？ 10/10 11:25
32F：推 Arton0306:都不用用到k@@ 这…题目整人 s大写得好精练又好读! 10/10 11:56
33F：推 stimim:我原本是在 k<1.6N 的时候会真的算矩阵值，不过还是 TLE 10/10 11:59
34F：→ stimim:所以就干脆把 k 拿掉乱算... 只能说他的测资不够强 10/10 12:00
35F：→ stimim:不然应该有很多反例，比如图并不是连通的，或是 k=1 之类的 10/10 12:01
36F：推 Arton0306:还有个不是稳定态的反例是3个node 0-10-0 <=> 5-0-5 10/10 12:22
37F：→ Arton0306:我怀疑题目是不是数值range给错... 10/10 12:22
38F：推 stimim:sparse matrix 会遇到一个问题，就是乘到最後矩阵是满的 @@ 10/10 12:45
39F：→ shaopin:感谢stimim 还没验证但我也直觉相信不理K才是可行的 10/10 13:27
40F：→ shaopin:因为我觉得最後只要稳态达到, 就不用管k了 10/10 13:28
41F：→ stimim:可是他的 K 可以小到 1 ，不一定会到稳态，也不一定有稳态 10/10 13:29
42F：→ stimim:像 arton 就举了一个没有稳态的例子 10/10 13:30
43F：→ shaopin:不过zombie_ac.cpp里最後magic number 5是k=5的意思? 10/10 13:30
44F：→ shaopin:所以如果k很小就照他的走, 如果k很大就看稳态? 10/10 13:31
45F：→ shaopin:没有稳态就一直算到k就是了@_@ 10/10 13:31
46F：→ stimim:没有啊，那个 5 是他要的前五名 10/10 13:32
47F：→ shaopin:喔了解 10/10 13:33
48F：推 DJWS:要判断会不会进入稳态 只需观察eigenvalue就好了 10/15 07:42
50F：→ DJWS:不过要计算eigenvalue是非常花时间的问题...参考看看就好 10/15 07:45
51F：推 stimim:我也有想过要去求eigenvalue ，不过好像没有比较简单 orz 10/15 12:55
52F：→ JingXD:eigendecom ->O(n^3) -> 爆炸 10/15 18:28
53F：推 Leon:这是图论里面一个问题, 我晚点把证明写上来 10/25 07:59