PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] Interview street: zombie march

看板Prob_Solve (計算數學 Problem Solving)作者 (problem maker)時間12年前 (2012/10/09 12:48), 編輯推噓20(20推 0噓 33→)
留言53則, 8人參與, 最新討論串1/6 (看更多)
題目: 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
推
10/09 15:25, , 1F
這題目真有趣! 但是不會做Orz
10/09 15:25, 1F
→
10/09 22:52, , 3F
還要再實作稀疏矩陣 orz
10/09 22:52, 3F
→
10/09 22:59, , 4F
是說我很好奇有最多zombie的五個node是 "最初" 有最多
10/09 22:59, 4F
→
10/09 22:59, , 5F
還是最後 "期望" 有最多的五個?
10/09 22:59, 5F
→
10/09 23:00, , 6F
如果是最後 "期望最多的五個" 要怎麼做@@?
10/09 23:00, 6F
推
10/09 23:13, , 7F
先做出 markov matrix M, 初始為 z(0) => z(t)=(M^t)*z(0)
10/09 23:13, 7F
→
10/09 23:14, , 8F
M是 n by n ，z(i) 是長度為 n 的向量
10/09 23:14, 8F
推
10/09 23:42, , 9F
n,m到10^5, 2*10^5嗎？這樣(稀疏)矩陣乘法也OK?
10/09 23:42, 9F
推
10/09 23:53, , 10F
不確定，要試試看 orz
10/09 23:53, 10F
→
10/10 00:34, , 11F
suhorng大, 是期望最後的最多zombie的五個node...
10/10 00:34, 11F
→
10/10 00:36, , 12F
bruteforce很執白, 就是隔壁鄰點的殭屍平均分散然後本點
10/10 00:36, 12F
→
10/10 00:36, , 13F
再加總...
10/10 00:36, 13F
推
10/10 01:24, , 14F
麻煩的是 矩陣到10^10個元素 次方數又到10^7
10/10 01:24, 14F
→
10/10 01:26, , 15F
次方還要化為diagonal matrix去解 不知怎利用sparse性質
10/10 01:26, 15F
→
10/10 02:58, , 16F
各位同學, 有沒有解法是適合interview的?一般interview
10/10 02:58, 16F
→
10/10 02:59, , 17F
碰到這個問題如果還要實作矩陣 應該不太多見
10/10 02:59, 17F
→
10/10 07:43, , 18F
次方那邊其實不用在意, 因為又反覆平方法, 最多只要做lg k
10/10 07:43, 18F
→
10/10 07:43, , 19F
量級的個數
10/10 07:43, 19F
推
10/10 08:48, , 20F
只能過第一組測資 orz https://gist.github.com/3862459
10/10 08:48, 20F
推
10/10 09:00, , 21F
我覺得癥結點在於只需要前五名 所以應該可以簡化很多東西
10/10 09:00, 21F
→
10/10 09:01, , 22F
如果直接用矩陣次方 由於矩陣太大 時間一定會爆炸的
10/10 09:01, 22F
推
10/10 11:05, , 23F
我覺得最後的穩定狀態是 #zombie/#node 也就是想成分子
10/10 11:05, 23F
→
10/10 11:07, , 24F
擴散 最後會變平均 只是在此之前還是要用暴力法跑
10/10 11:07, 24F
→
10/10 11:08, , 25F
每做完一個step就檢查是否進入穩定狀態
10/10 11:08, 25F
推
10/10 11:18, , 26F
發現這樣也有問題 zombie不會留在原地 一些case會錯...
10/10 11:18, 26F
推
10/10 11:20, , 27F
Accept 了... 結果他的測資好像都會進入穩定態 orz
10/10 11:20, 27F
推
10/10 11:22, , 28F
也有可能是因為要四捨五入到整數，所以進入穩定態的時間會
10/10 11:22, 28F
→
10/10 11:22, , 29F
大幅減少 ??
10/10 11:22, 29F
推
10/10 11:25, , 30F
cool! 解法是？
10/10 11:25, 30F
→
10/10 11:25, , 31F
https://gist.github.com/3862459 下面的 zombie_ac.cpp
10/10 11:25, 31F
推
10/10 11:56, , 32F
都不用用到k@@ 這…題目整人 s大寫得好精練又好讀!
10/10 11:56, 32F
推
10/10 11:59, , 33F
我原本是在 k<1.6N 的時候會真的算矩陣值，不過還是 TLE
10/10 11:59, 33F
→
10/10 12:00, , 34F
所以就干脆把 k 拿掉亂算... 只能說他的測資不夠強
10/10 12:00, 34F
→
10/10 12:01, , 35F
不然應該有很多反例，比如圖並不是連通的，或是 k=1 之類的
10/10 12:01, 35F
推
10/10 12:22, , 36F
還有個不是穩定態的反例是3個node 0-10-0 <=> 5-0-5
10/10 12:22, 36F
→
10/10 12:22, , 37F
我懷疑題目是不是數值range給錯...
10/10 12:22, 37F
推
10/10 12:45, , 38F
sparse matrix 會遇到一個問題，就是乘到最後矩陣是滿的 @@
10/10 12:45, 38F
→
10/10 13:27, , 39F
感謝stimim 還沒驗證但我也直覺相信不理K才是可行的
10/10 13:27, 39F
→
10/10 13:28, , 40F
因為我覺得最後只要穩態達到, 就不用管k了
10/10 13:28, 40F
→
10/10 13:29, , 41F
可是他的 K 可以小到 1 ，不一定會到穩態，也不一定有穩態
10/10 13:29, 41F
→
10/10 13:30, , 42F
像 arton 就舉了一個沒有穩態的例子
10/10 13:30, 42F
→
10/10 13:30, , 43F
不過zombie_ac.cpp裡最後magic number 5是k=5的意思?
10/10 13:30, 43F
→
10/10 13:31, , 44F
所以如果k很小就照他的走, 如果k很大就看穩態?
10/10 13:31, 44F
→
10/10 13:31, , 45F
沒有穩態就一直算到k就是了@_@
10/10 13:31, 45F
→
10/10 13:32, , 46F
沒有啊，那個 5 是他要的前五名
10/10 13:32, 46F
→
10/10 13:33, , 47F
喔瞭解
10/10 13:33, 47F
推
10/15 07:42, , 48F
要判斷會不會進入穩態 只需觀察eigenvalue就好了
10/15 07:42, 48F
→
10/15 07:43, , 49F
10/15 07:43, 49F
→
10/15 07:45, , 50F
不過要計算eigenvalue是非常花時間的問題...參考看看就好
10/15 07:45, 50F
推
10/15 12:55, , 51F
我也有想過要去求eigenvalue ，不過好像沒有比較簡單 orz
10/15 12:55, 51F
→
10/15 18:28, , 52F
eigendecom ->O(n^3) -> 爆炸
10/15 18:28, 52F
推
10/25 07:59, , 53F
這是圖論裡面一個問題, 我晚點把証明寫上來
10/25 07:59, 53F
‣ 更多 shaopin 的文章
文章代碼(AID): #1GSwok78 (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 shaopin 的文章
文章代碼(AID): #1GSwok78 (Prob_Solve)