[問題] SPOJ 8545:subset sum

[KitWoolsey (難得好天氣)]

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
→ tkcn:3
→ KitWoolsey:那正解是n or nlgn @@? 可以給點提示嗎
推 seanwu:是2... n=100的n^2怎麼可能不會過XD  你的做法是 2^n
→ seanwu:呃..如果你要說因為數字範圍給定<=1000所以是1000n^2也行啦
推 seanwu:剛剛傳ac了，你的想法是正確的
→ seanwu:問題在於python的list(是嗎?不太熟)，那個 not in 的操作
→ seanwu:不知道它是怎麼做的，不過我想應該不是 O(1)
→ seanwu:考慮到數字總和的上限是10^5，直接用一個bit array檢查
→ seanwu:會快很多。附帶一提，我用C寫的時間是 0.03
推 tkcn:我錯了，沒仔細看程式跟題目 Orz
→ AmosYang: Proving an upper bound is human; an lower bound,
→ AmosYang: divine.                                           XD
我跑了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)
→ KitWoolsey:還是我就乖乖用C郝了@_@
→ KitWoolsey:n=100 0.008秒左右 還是太慢QQ?
推 suhorng:自己測的話說不定會有數值問題 可能測不到比較強的測資 ?
→ KitWoolsey:不知道會有什麼比較難的case @_@
→ KitWoolsey:我有點懷疑是我光IO就超時了. @_@
→ bleed1979:輸了，我跑0.04s。
→ danielsig727:配備不同不能這樣比吧@@"
→ KitWoolsey:?_?