題目: 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
有關? 但我還是不知道怎麼做??

這題目真有趣! 但是不會做Orz

還要再實作稀疏矩陣 orz

是說我很好奇有最多zombie的五個node是 "最初" 有最多還是最後 "期望" 有最多的五個?如果是最後 "期望最多的五個" 要怎麼做@@?

先做出 markov matrix M, 初始為 z(0) => z(t)=(M^t)*z(0)M是 n by n ，z(i) 是長度為 n 的向量

n,m到10^5, 2*10^5嗎？這樣(稀疏)矩陣乘法也OK?

不確定，要試試看 orz

suhorng大, 是期望最後的最多zombie的五個node...bruteforce很執白, 就是隔壁鄰點的殭屍平均分散然後本點再加總...

麻煩的是 矩陣到10^10個元素 次方數又到10^7次方還要化為diagonal matrix去解 不知怎利用sparse性質

各位同學, 有沒有解法是適合interview的?一般interview碰到這個問題如果還要實作矩陣 應該不太多見

次方那邊其實不用在意, 因為又反覆平方法, 最多只要做lg k量級的個數

只能過第一組測資 orz https://gist.github.com/3862459

我覺得癥結點在於只需要前五名 所以應該可以簡化很多東西如果直接用矩陣次方 由於矩陣太大 時間一定會爆炸的

我覺得最後的穩定狀態是 #zombie/#node 也就是想成分子擴散 最後會變平均 只是在此之前還是要用暴力法跑每做完一個step就檢查是否進入穩定狀態發現這樣也有問題 zombie不會留在原地 一些case會錯...

Accept 了... 結果他的測資好像都會進入穩定態 orz也有可能是因為要四捨五入到整數，所以進入穩定態的時間會大幅減少 ??

cool! 解法是？

https://gist.github.com/3862459 下面的 zombie_ac.cpp

都不用用到k@@ 這…題目整人 s大寫得好精練又好讀!

我原本是在 k<1.6N 的時候會真的算矩陣值，不過還是 TLE所以就干脆把 k 拿掉亂算... 只能說他的測資不夠強不然應該有很多反例，比如圖並不是連通的，或是 k=1 之類的

還有個不是穩定態的反例是3個node 0-10-0 <=> 5-0-5我懷疑題目是不是數值range給錯...

sparse matrix 會遇到一個問題，就是乘到最後矩陣是滿的 @@

感謝stimim 還沒驗證但我也直覺相信不理K才是可行的因為我覺得最後只要穩態達到, 就不用管k了

可是他的 K 可以小到 1 ，不一定會到穩態，也不一定有穩態像 arton 就舉了一個沒有穩態的例子

不過zombie_ac.cpp裡最後magic number 5是k=5的意思?所以如果k很小就照他的走, 如果k很大就看穩態?沒有穩態就一直算到k就是了@_@

沒有啊，那個 5 是他要的前五名

喔瞭解

要判斷會不會進入穩態 只需觀察eigenvalue就好了http://ppt.cc/bCZw不過要計算eigenvalue是非常花時間的問題...參考看看就好

我也有想過要去求eigenvalue ，不過好像沒有比較簡單 orz

eigendecom ->O(n^3) -> 爆炸

這是圖論裡面一個問題, 我晚點把証明寫上來