作者查詢 / hcsoso

總覽項目：發文 | 留言 | 暱稱

作者 hcsoso 在 PTT [ Prob_Solve ] 看板的留言(推文), 共71則

限定看板：Prob_Solve

首頁

尾頁

Re: [問題] 有關binomial heap的find min的複雜度

[ Prob_Solve ]30 留言, 推噓總分: +6

作者: DJWS - 發表於 2017/11/30 05:11(8年前)

8^F推hcsoso: 不過的確就算以學習理論的角度而言, binomial跟Fibonacci11/30 12:26

9^F→hcsoso: heaps為了達成deterministic而使證明複雜的代價太大了.11/30 12:27

10^F→hcsoso: 稍微引入一點隨機性就可以教treap了, 更別說它跟quicksort11/30 12:28

11^F→hcsoso: 的緊密關聯...11/30 12:28

[問題] 找四環有幾個，有沒有比O(n^3)快的算法

[ Prob_Solve ]22 留言, 推噓總分: +10

作者: rareone - 發表於 2017/08/23 00:17(8年前)

1^F推hcsoso: 無向圖嗎? 有 O(n^2) 的算法08/23 01:25

2^F→hcsoso: 對每個點 x, 以及每對 x 的鄰居 (y,z), A[y,z]++08/23 01:28

3^F→hcsoso: 最後檢查有沒有某個 A[u,v] 的值大於 108/23 01:29

4^F推hcsoso: 如果圖的邊數不多的話有更外的算法08/23 01:36

5^F推hcsoso: http://www.tau.ac.il/~nogaa/PDFS/ayz4.pdf O(m^{4/3})08/23 01:38

6^F→hcsoso: *快08/23 01:38

7^F推hcsoso: 抱歉，上面的算法應改進成一發現某格值已為 1 而要加為 208/23 02:10

8^F→hcsoso: 時就要停下08/23 02:10

9^F→hcsoso: 不然最糟時會是 O(n^3)...08/23 02:11

16^F推hcsoso: 哎呀我沒有意識到原 po 需要的是計數不是存在性…上面的08/23 08:51

17^F→hcsoso: 推文是存在與否的算法08/23 08:51

18^F推hcsoso: 另外請問 a,c 或 b,d 可相同嗎？08/23 08:58

20^F推hcsoso: 我指的是連結前面的那個08/23 09:01

[討論] A Solution of the P versus NP Problem

[ Prob_Solve ]6 留言, 推噓總分: +2

作者: FRAXIS - 發表於 2017/08/15 11:23(8年前)

1^F推hcsoso: 別鬧了,這不可能是對的. 他的學生前一年宣稱 PH != P 的08/15 11:35

2^F→hcsoso: 論文還掛在 arXiv 上呢...08/15 11:36

5^F推hcsoso: 他的學生那篇已經在上面了, item 112.08/15 11:49

Re: [問題] 可停留的路線安排程式

[ Prob_Solve ]77 留言, 推噓總分: +18

作者: DJWS - 發表於 2016/12/14 08:46(9年前)

22^F推hcsoso: 我想樓上的 n 指的是矩陣的邊長? 題目中 n 為天數.12/18 14:45

23^F→hcsoso: 不論如何, 這題不難做到線性時間, 一次 BFS 加上證明一些12/18 14:46

24^F→hcsoso: 最佳解的性質就行了.12/18 14:46

25^F推hcsoso: 噢, 漏了一步, 得先做一次 DP 計算不停留的最大利益.12/18 14:59

27^F推hcsoso: 請教 aaaaajack 的算法若碰到負圈怎麼辦? 有負邊的圖中12/19 06:57

28^F→hcsoso: 最短路徑 (simple path) 應是 NP-hard?12/19 06:58

29^F→hcsoso: 啊, 可以先將所有負的位置移除, 最佳路徑不使用他們12/19 06:59

33^F推hcsoso: 不是盤面上的負值, 而是 a 大算法中終點值減原值可能為負12/19 07:07

34^F→hcsoso: D 大提到的情形不會發生在最佳路徑上12/19 07:09

38^F推hcsoso: a大的算法可能有另外的問題。固定終點後也許有另一條獲12/19 07:57

39^F→hcsoso: 利較少的但較短的路徑，在天數較少時也許才是最佳解。得12/19 07:57

40^F→hcsoso: 計算 k 步內最短路徑才行？12/19 07:57

41^F推hcsoso: 最糟的情形多一個 n^2 項。也許用動態最短路徑資料結構12/19 08:02

42^F→hcsoso: 可以快一點，不過有點噁心…12/19 08:02

44^F推hcsoso: Good point.12/19 08:42

50^F推hcsoso: 請問如何依照天數決定終點呢？假設我們固定一終點，按終12/19 10:27

51^F→hcsoso: 點值調整各位置值為虧損，並將忽略負值位置。若這時最佳12/19 10:27

52^F→hcsoso: 路徑虧損10並花費10步，而有另一路徑前往同一終點虧損1012/19 10:27

53^F→hcsoso: 0但花3步。當天數為三時如果只跑 Dijkstra 該點因最短路12/19 10:27

54^F→hcsoso: 徑花費10步因此不會被選取，除非演算法紀錄對每個點每個12/19 10:27

55^F→hcsoso: 天數的最短虧損路徑，但這就需要 k-Dijkstra 了。不知我12/19 10:27

56^F→hcsoso: 是否誤解了？12/19 10:27

Re: [問題]zerojudge競賽題目b841:104北二5.骨牌遊戲

[ Prob_Solve ]29 留言, 推噓總分: +8

作者: DJWS - 發表於 2016/07/24 10:56(9年前)

3^F推hcsoso: 不介意純理論方法的話可以做到 O(n log^3 n), 使用07/24 12:16

4^F→hcsoso: multiple-source multiple-sink max flow on planar graph07/24 12:16

5^F→hcsoso: http://cs.brown.edu/~pnk/publications/msms2.pdf07/24 12:16

6^F→hcsoso: 不然的話, 用 electric flow 可以做到 O(n^{10/7})07/24 12:17

7^F→hcsoso: 另外 Gaussian elimination 加上 nested dissection 可以07/24 12:18

8^F→hcsoso: 做到 randomized O(n^w/2) <= O(n^1.19)07/24 12:18

9^F→hcsoso: 這幾種方法全部都很難實作...07/24 12:19

13^F推hcsoso: 使用 msms max flow 本身就需要 bipartite, 把一側全當 s07/25 11:36

14^F→hcsoso: ource 另一側全當 sink；如果你指的是 max flow 在 bipar07/25 11:36

15^F→hcsoso: tite planar 上有無更好的演算法，我想沒有，因為 subdiv07/25 11:36

16^F→hcsoso: ide 所有邊便可將任意圖轉為 bipartite07/25 11:36

17^F推hcsoso: 這題可能的希望是在 unweighted grid 上有更好的演算法，07/25 11:40

18^F→hcsoso: 不過我沒有什麼想法…07/25 11:40

21^F推hcsoso: msms max flow 是我所知最快求 bipartite planar matching07/26 00:23

22^F→hcsoso: 的方法了, 去掉 bipartite 連能不能做到 O(n polylog n)07/26 00:24

23^F→hcsoso: 都是未知07/26 00:24

[心得] 1D/1D DP and convex hull trick

[ Prob_Solve ]5 留言, 推噓總分: +5

作者: FRAXIS - 發表於 2016/03/17 18:39(9年前)

1^F推hcsoso: Nice summary. 推!03/18 03:32

Re: [問題] 給定n個排好序的整數陣列找中位數

[ Prob_Solve ]4 留言, 推噓總分: +1

作者: FRAXIS - 發表於 2014/10/17 19:40(11年前)

2^F推hcsoso: cstheory 上已經有人問過了:10/17 23:49

3^F→hcsoso: http://cstheory.stackexchange.com/q/20944/180010/17 23:50

[問題] 單紙帶圖靈機與 o(n log n)

[ Prob_Solve ]9 留言, 推噓總分: +3

作者: suhorng - 發表於 2011/11/08 23:22(14年前)

1^F推hcsoso:This theorem is proved by Kobayashi, which is not an11/08 23:56

2^F→hcsoso:easy result. This may be helpful to you:11/08 23:56

3^F→hcsoso:http://arxiv.org/abs/cs/031004611/08 23:56

[問題] 一個關於演算法的問題

[ Prob_Solve ]9 留言, 推噓總分: +3

作者: bin90909 - 發表於 2011/06/08 23:55(14年前)

1^F推hcsoso:就算沒有 weight, 這是所謂的 max. P_3 packing problem,06/09 00:14

2^F→hcsoso:即使在平面圖上都是 NP-complete. 你的圖有特殊性質嗎?06/09 00:15

3^F推hcsoso:用 local search 可以有 1/2-eps 的近似演算法.06/09 00:19

4^F→hcsoso:可參考 "On Local Search for Weighted k -Set Packing",06/09 00:20

5^F→hcsoso:by Esther M. Arkin and Refael Hassin.06/09 00:20

6^F推hcsoso:另外, 可以注意到就算是亂挑也會是個 1/3 近似演算法,06/09 00:26

7^F→hcsoso:因為每一條 path 最多破壞另外三條 paths.06/09 00:27

首頁

尾頁