Codeforces Round #288 (Div. 2)

另一場在公司virtual participate 的比賽...

即場只做了A-C 3題

D跟E事後看Editorial 也過了

感覺也很深的, 之前為什麼都不敢面對失敗  就一句"不懂做"就算了

Editorial也沒看, 難怪之前怎樣也不會進步...

現在可能沒壓力之下反而會跑去看Editorial了, 也有看人家的comment

真的獲益良多啊... 有時Editorail寫得很差的, 也有高手在comment中補完

還有很多簡單易明的reference  真的以前怎麼都不會看啊?

Codeforces Round #288 (Div. 2)

題目: http://codeforces.com/contest/508/problems

A: (頹題)

就是暴試有沒有2 * 2的正方形出現了...

B: (頹題, Greedy)

也是頹題, 又是這些"改一個digit變成最小"之類的問題, 現在Codeforces很流行這個嗎??

好吧, 這條有一點不同, 問題求換一pair digit之後, 可獲得最大的even number是什麼...

這類問題只要注意一下會有相同的digit, 也就是考慮如何tie break...通常也就是greedy就行了

C: (Greedy, Math)

我即場做時是一棍過了, 但寫得極度差...可能在公司面對的code也是這個質數, 自然就寫出來了=.=

我欺負它數據小, 用很暴力的方法過了

其實題目的設定好像有很漂亮的方法可以過...詳情可以看Editorial 或者Peter神的Code

D: (Graph, Euler-Circuit, Hashing)

終於到這一題了...這一題是我真正想記下的題目..!

題目是這樣的, 給了n (n < 2*10^5) 條 長度為3的string
然後問可否用它們合成一條長度為n+2 的string,  而每條input的string也是它的substring?
e.g.   aba,   bac  可合成為 abac !

一眼看下去, 是String + Graph的組合題了

嘛結論上我也沒錯的...

但糾結的位是,  那個建圖的方法我太天真了

當然直接想到的是暴試所有input 看能不能連起來吧

就是 aba --> bac,  bac --> acd...之類的

首先這樣就要 n^2 了,  然後這樣建了一個有向圖後, 找一個cycle where length = n 就好了

這就是我的想法...有向圖的cycle, 我沒想到很直接的方法做, 思路一瞬間也飛去SCC之類的東西
然後又在想是不是有方法快速建圖...

就這樣已經GG了, 比賽完結

來看一下正解....竟然是傳說中的Eular Path!!

這個東西自Year 1 學過後基本就沒用過啊...也沒Code過就是了

(反而Hamiltonian Path還Code過幾次...)

來溫故知新一下
Eular Path是所有邊都用上exactly 1次的Path, 是P問題

Hamiltonian Path是所有點都用上exactly 1次的Path 是NP問題,  n <= 16 可用Bitmask DP解

各自都有無向圖和有向圖的版本, 大同小異

多得之前有心寫下的文章和做過題目, Hamiltonian Path我還是有印象記得原理和做法的

所以集中說Euler Path吧...

Ref: http://www.csie.ntnu.edu.tw/~u91029/Circuit.html

Euler Path也就是一筆連遊戲

如果起點跟終點一樣就是Euler Circuit了

其實一個圖有Euler Path, 那它頭尾再連一條線就變成Circuit, 反之亦然, 下面以Euler Circuit為例

有點印象Year 1 說過的, 如果有Euler Path的話, 就可以把那幅圖divide 成很多小component

各自形成一個小的Euler Circuit, 這是Divide & Conquer的思路, 明白是明白 就是不知道怎樣Code, 多得這場Codeforces 還有高手的comment, 讓我找到了這個algorithm的名稱:

Hierholzer's Algorithm

好吧, 名太難讀了, 記到就記吧

重點是實作其實也是DFS!  

而且DFS (有技巧地) 可以寫得很簡單的...

繼續說明算法,  Euler Path的重點一字記之曰: Degree!

有向圖跟無向圖也是Degree的分別而已!
Circuit跟Path也是Degree的分別而已!

道理上如果是有Euler Circuit的話,  所有點的Degree都要

1. in-degree = out-degree (無向圖則無視這點, 因為不能分什麼叫in-out)
2. 從1看來, degree數要是雙數
3. 從1+2看來, net degree (out - in) 一定要是 0

Circuit來說那一點開始都可以

Path的話也大同小異, 只是可以容許多一個可能性: 有2個點的net degree不是0, 而是 1 跟 -1

一個是起點 (out-degree比in-degree 多1)  另一個是終點

如果無向圖的話則是其中兩個點的degree是單數, 它們隨便一個是起點另一個是終點

這個算法是以"邊"為主題的DFS, 所以時間性也是以E為重點

如果是adj matrix的話是O(V^2 + E), list的話則是O(V+E)

由於是每條邊, 只要能走都走, 每條邊只走一次, 所以不像普通的DFS用visit[] 去記錄是否visit過點, 而是考慮從某一點到另一點還有沒有edge可以走, 所以每次弄走一條edge, 實作上怎樣都可以, 可以把degree 減1 , 也可以真的從圖的結構上弄走一條edge, 建議後者

這樣DFS直到沒有Edge了, 算法就完成了, 然後這算法精秒之處,是用post-order來儲下Euler Path的點/邊, 這是因為不能用pre-order, 在traversal的過程中不能肯定次序, 但post-order是確定的倒序...這個思路很多算法也用得上

最後的伏位是做完DFS要再CHECK一下那條Path的Size是否 |E|,  因為圖可能不連通

總結的話算法是這樣的:

1. 查一下degree的條件, 是否有"可能"有Euler Path / Circuit
1. 如果可能的話順便記下起點和終點
2. DFS,  用post-order的時機記下整條Path / Circuit
3. 確認一下Path / Circuit的長度是否正確, 因為圖可能不連通

最後順帶一提, 不可能在P時間內完成找出所有Euler Cicruit這件事, 因為一定要用Backtracking 而且是沒什麼剪枝的方法

大道理說完了, 我很有心機地加上了給未來的我的COMMENT的Code在這邊: (先把整篇看完再看Code會易明點)

http://codeforces.com/contest/508/submission/9975685

好吧回到題目上了  

我們從Code跟思路上還有點東西要學

首先回歸原點,  要解決這道題目, 需要幾樣重點:

1. 看穿這是Euler Path的本質
2. 建圖的方法, 技巧 (方便的Code法, 不超時的方法...etc)
3. Euler Path的Algorithm

上面很大部分是第3點了, 至於第1點嘛...可能是經驗吧

因為以我最原本很直接的建圖方法, 我所謂的找一個cycle which size = n
靠你媽的這不就是Hamiltonian Circuit嘛... 一看應該就知道不是這樣做了

起碼不是這樣建圖 所以說對這些經典問題的了解對分析題目很有用的...

而1跟2其實是有關係的...

這題要把它轉化成Euler Path 需要特別(起碼我是很少這個經驗)的建圖技巧,  

就是不要3個字一起看, 而是2個字一起看

eg,  abc   我們把它變成 ab --> bc   , ab是一個node, bc是一個node

這是一個以2個字母為一個node的有向圖

這樣的話 Euler Path就找出了一個 "最大限度" 把字連起來的Path

要是這個Path 也不是答案, 那就是沒有答案了

然後Code法也夠神的,  竟然是傳說中的hashing

神對我真好, 近期(Round 290還是291) 也有一題是以hashing為主題的題目, 我會把它跟說好看Trie一起作一個String Searching的記錄...

這裡就這樣簡單說吧...由於只有2個字母(或數字), 所以hash value不會很大

128就包了所有基本的ASCII,  hash base通常用接近於alphabet size的數字, 如果要mod的話, 最好選單數, 這兒由於不用mod, 所以比128 大的就好了

h("ab") = 128*a + b

h("bc") = 128*b + c

就這樣,  神奇的是, 這樣建圖易code, 方便, 不超時!!
因為所有一樣的string 都可以O(1)就找到它的node (的id)了  很方便是吧??
而要revert print回原本的字母也很方便,  就是  h() / 128 而已!

一定要看回上面的Code, 其實我是參考了一個紅字User的寫法! 當中的DFS也有更多奇投淫巧, 就這樣又學到很多新的有用的技巧了!

E: (DP, Greedy)

由於上一題的光, 這一題失色很多了

這一題是給了一堆括孤的位置, 求能否找出一個可能的配置

eg:  

3

2 3 

1 4

1 4

是代表 第1個 "(" 相對的 ")" 距離它 2 或者 3的距離

第2個"(" 距離它的")" 有 [1,4] 的距離 

第3個也是這樣

答案是 (())()

直接地說吧  我完全忘了所謂"相對"的意思!

好在comment有人提醒了我一下!

就是說"(())"  第3個位置的 ")" 不可能是第 1個"("的伴侶!

有了這個concept才能解釋所有答案!

官方的答案是用DP, 大意是 每個"(" 與相對的")" 之間要是 另一個合理的配置!

由於我有點忙跟笨, 也就沒太看懂這個DP的意思..

更大的原因是, 有很多高手已說明了一個更強大的更快更易Code的Greedy方法!

方法很簡單:

用一個Stack去做, 每次可以")"的時候, 就立即這樣做! 不然的話就開新"("

每次開新"("的時候就push它的位置進stack, 方便下次iteration去check能否關上")"

其實這題的所有難度, 如果要用Greedy做的話, 是它的正確性!
很多人也在Editorial的Comment問了正確性, 也有很多紅字User答了!
就自己去看吧 :)

http://codeforces.ru/blog/entry/16048?locale=en

重點的是Greedy的Prove的思路, 讓我引用某紅字User的話

Typically, whenever we see a problem with greedy and we want to prove that it is correct, we do some sort of "exchange" argument (i.e. given a valid/optimal configuration, we can always swap some things so it looks like what our greedy will do).

所以這個做法的正確性證明就是, 先假設有其它的Solution跟我們Greedy找出來的不同, 然後證明最終它們還是可以diverge into 我們Greedy找出來的Solution, Q.E.D.

我認為這題最大的得著是學到了Greedy的證明基本思路跟信心吧..!!