作者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