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