作者KitWoolsey (難得好天氣)
看板Prob_Solve
標題[問題] SPOJ 8545:subset sum
時間Thu Apr 14 22:55:38 2011
http://www.spoj.pl/problems/MAIN72/
(題外話: dirty nopaste 是不是壞掉了??)
http://codepad.org/WqDFt07d
我用Python寫的 , 內容大致是 當得知了前t個數的subset sum 後,
再把第t+1個數分別加上前面所有可能的sum,如果有出現未重覆的就加入記錄並加進總和.
時間複雜度應該是O(n^2) (不知道我有沒有搞錯?)
不過還是TLE了 不知道是因為
(1) Python速度太慢?
(2) 我的演算法實際不是n^2?
(3) 這題n^2仍究不夠快@_@?
我對演算法其實還不是很熟@_@ 不知道是哪一種情形 還請板友賜教
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.231.102.225
1F：→ tkcn:3 04/14 23:37
2F：→ KitWoolsey:那正解是n or nlgn @@? 可以給點提示嗎 04/15 01:05
3F：推 seanwu:是2... n=100的n^2怎麼可能不會過XD 你的做法是 2^n 04/15 01:41
4F：→ seanwu:呃..如果你要說因為數字範圍給定<=1000所以是1000n^2也行啦 04/15 01:43
5F：推 seanwu:剛剛傳ac了，你的想法是正確的 04/15 01:54
6F：→ seanwu:問題在於python的list(是嗎?不太熟)，那個 not in 的操作 04/15 01:54
7F：→ seanwu:不知道它是怎麼做的，不過我想應該不是 O(1) 04/15 01:54
8F：→ seanwu:考慮到數字總和的上限是10^5，直接用一個bit array檢查 04/15 01:55
9F：→ seanwu:會快很多。附帶一提，我用C寫的時間是 0.03 04/15 01:56
10F：推 tkcn:我錯了，沒仔細看程式跟題目 Orz 04/15 11:11
11F：→ AmosYang: Proving an upper bound is human; an lower bound, 04/15 13:28
12F：→ AmosYang: divine. XD 04/15 13:28
我跑了n= 10 100 1000的case 看起來是n^2...@@
n= 500 takes 0.212345638688 sec
n=1000 takes 0.843093548846 sec (不過這樣看起來好像太久了.. = = +)
※ 編輯: KitWoolsey 來自: 61.231.96.43 (04/15 23:26)
13F：→ KitWoolsey:還是我就乖乖用C郝了@_@ 04/15 23:26
14F：→ KitWoolsey:n=100 0.008秒左右 還是太慢QQ? 04/15 23:26
15F：推 suhorng:自己測的話說不定會有數值問題 可能測不到比較強的測資 ? 04/15 23:36
16F：→ KitWoolsey:不知道會有什麼比較難的case @_@ 04/15 23:41
17F：→ KitWoolsey:我有點懷疑是我光IO就超時了. @_@ 04/15 23:41
18F：→ bleed1979:輸了，我跑0.04s。 04/16 00:26
19F：→ danielsig727:配備不同不能這樣比吧@@" 04/16 01:22
20F：→ KitWoolsey:?_? 04/16 20:42