Re: [問題] ACM 704有什麼加速的辦法?

[tkcn (小安)]

※ 引述《iamnotgm (伽藍之黑)》之銘言：
: 標題: Re: [問題] ACM 704有什麼加速的辦法?
: 時間: Sat Jun  4 19:34:57 2011
:
: ※ 引述《tkcn (小安)》之銘言：
: : ※ 引述《iamnotgm (伽藍之黑)》之銘言：
: : : 這題我試著用2-way BFS從input的state和finish的state展開
: : : 只要兩個BFS中有相同的state就能知道走法
: : : 可是光是一個state往下走8步能展開的state就有87381個
: : 每一步都只有四種可能走法，
: : 走 8 步可能的 state 應該只有 4^8 = 65536，
: 那是最後一層的state數
: 在那之前的走7步,走6步...等等的state也要記下來吧
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 220.133.69.80
: 推 tkcn:說的沒錯，我現在知道你的 87381 從哪來的了                  06/04 20:02
: → tkcn:不過扣掉重複的，實際數量會少非常多                         06/04 20:02
: → tkcn:你現在最需要加速的應該就是檢查重複的部份了                 06/04 20:03
: → iamnotgm:就算把檢查重複做到最快依然有將近1萬個不重複的state     06/04 21:37
: → iamnotgm:兩個BFS都有1萬個state全部檢查還是10^8                  06/04 21:38
: → tkcn:10000 個其實挺少的不是嗎?                                  06/04 21:39
: → tkcn:呃，2-way BFS 不會把兩個複雜度相乘吧                       06/04 21:39
: → iamnotgm:不然應該怎麼作?剛剛用hash寫倒是真的變快很多            06/04 21:41

GCJ 快開始了，簡短講一下 (逃)

先從一端 BFS 八層，產生那將近一萬個 state，加入 hash table，
再從另一端 BFS，每到一個新 state 都檢查是否存在 hash table 中。

很顯然複雜度只是兩次 BFS，並沒有相乘 (前題是利用 hash table 檢查為 O(1))


如果還想要加速，試著把狀態用一個 64-bit integer 表示吧


GCJ 衝呀~~~

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.78.231
→ bleed1979:雖然AC在0.5s內，但最後一句我仍參不透。 我拆成兩個。
這題是很久以前寫的了，細節也記不清楚，意思到就好。

三角形共有五種顏色，矩形有六種顏色，所以各用 3-bits 去表示就夠了。
總共有 10 個三角形、11 個矩形，所以 63 bits 足夠放下所有的 state。

只用一個 64-bits integer 還有其他好處，
如果狀態設計的好，旋轉可以只用 shift 和其他 bit-operations 來達成。
※ 編輯: tkcn            來自: 140.114.78.231       (06/05 16:31)
→ bleed1979:原來是用顏色。我是用數字，想說數字10必須4個bits。