[問題] Sum of Three Values 使用雜湊表

看板 Prob_Solve
作者
時間
留言 8則留言,2人參與討論
推噓 0  ( 0推 0噓 8→ )
各位電神安安 o'_'o Sum of Three Values 應該算是很經典的題目,其簡化版本 Sum of Two Values 常見的解 法有兩種,分別是用雜湊表及 two pointer 有趣的是在 CSES 上使用 std::unordered_map 及 GNU PBDS 的 gp_hash_table 分別各有 一筆測資 TLE, 反而改用 BST 才 AC, 證實 log 只是常數 XD 回過頭來看 Sum of Three Values, 我想同樣有雜湊表與 three pointer 兩種解法。 CSES 上 N <= 5000, 顯然需要至少 O(N^2) 的解。 https://cses.fi/problemset/task/1641 這次試過 gp_hash_table, cc_hash_table, unordered_map 但測資 #21 始終過不了。 我也上網搜尋比較好的 hash function, 還是 TLE. https://reurl.cc/4a05rY 把測資載下來研究,cc_hash_table 約十秒多,cc_hash_table + custom hash function 約七秒,cout IMPOSSIBLE 完直接 exit(0) 不管記憶體壓到四秒多,BST 則是慘烈的三十 幾秒 https://cses.fi/paste/25d625b68bc3c2b828e863/ 但我的很好奇為何會這樣?? 明明 N 不過才 5000, 只做 12497500 次查詢竟然要花上 4.3 秒!? 這筆測資到底有何神秘之處??其他同樣 N = 5000 且無解的測資頂多跑個 0.1 秒而已。 實在找不到程式的瓶頸在哪,優化讀 5000 個整數也只快零點零幾秒。 想請教各位板友,這題是非用 three pointer 不可嗎??可是我看 Sum of Four Values 好像還是用雜湊表耶。 還是 hash function 有甚麼改進之處?? 感謝 -- 看到國外 IP, 尤其是來自奇怪地區,請多加留意是否為跳板。 https://ptt.nevikw39.cf/ 輸入 ptt 上的 id, 即列出其最近上站的 10 個 IP 地址、日期、國家與是否為跳板。 --
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.240.165.72 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1628963639.A.030.html
1FoToToT: https://cses.fi/paste/a01de9d1338676682907de/ 可能CSES 08/15 03:20
2FoToToT: memory 很慢? 我沒仔細測,但隨手寫個一個這樣會過 08/15 03:20
3FoToToT: https://cses.fi/paste/333b19bfd1af9e8f290804/ 幫你改成 08/15 03:25
4FoToToT: 這樣也會過,大概就是不要用那麼多記憶體 (戳不存在的會幫 08/15 03:26
5FoToToT: 創,但實際上你也沒有想要用那些被創出來的東西) 08/15 03:26
6Fnevikw39: 了解惹,謝謝 oT 大 08/15 10:20
7Fnevikw39: 原來是因為使用 [] 如果 key 不存在也會自動 insert 的 08/15 10:20
8Fnevikw39: 細節 08/15 10:20