ACM_kirakira: 3月 2015

2015年3月16日星期一

New Spam in Codeforces?

WTF is this shit, I don't even know this guy.

2015年3月15日星期日

Codeforces Round #291 (Div. 2)

這場可真是我近來最想最想記下的一場, 記完這一場後真的要寫說好的Trie跟String Matching的Algorithm了...但在此之前這場5題都做了
而且學到更多以前聽過卻沒學過的實用技巧!

Codeforces Round #291 (Div. 2)

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

A: (頹題, Greedy)

又一題改digit 令數字變成什麼什麼的題目...我又再重覆上一場的句子: 通常都是Greedy就行了..

B: (Math, Geometry)

略有一點難度的數學題, 問最少要多少條線才能把所有目標都擊破

也不用特別的技巧或用上大家比賽常用的Geom的Class, 只要計Slope, 一樣Slope 的就Lie on 同一條線了...

C: (String, Hashing)

第一題要詳細記下的題目!

這題跟之後會寫的String Searching不無關係!

先來說題意吧: Given n 條pattern, 和m 條 string (每一條是一個獨立query), 所有string 只會由[a-c] 組成

問是否有任意一個pattern跟 string 只差exactly 一個字母相異?

在學了Trie的基本之後的我, 直接想到的也是用Trie 去解, 事實上看comment也有人說能用

prefix tree (即是Trie)去解...但當時我沒很直接想到怎樣做

String的處理我一向都很弱 (說真的也沒什麼特別強=.=)

我只想到每個query 可以試住做以下的事:

每個位試試改成其它的2個字母 eg: 原本是'a'的話試試改成'b'或者'c', 每個位都這樣做
跟每個pattern比較一下看是否一樣

這題的時間我也很難分析, 因為它是直接說"所有input 的總長度 L<= 6*10^5"

所以這樣說吧, 上面的第一步最壞的情況已經是O(L), 第2步要跟每個pattern比較一下這步卻很痛苦, 這是multi-pattern matching, 用KMP好像也不一定夠快? (我也忘了KMP怎寫, 只記得concept...) 實際上我也真的這樣implement, 也真的超時了

結果還是跑去看Editorial, 又掘到金了! 兩大keywords:

Rolling Hash, Rabin-Karp Algorithm

前者是一個運用Polynomial Hashing的一個技巧, 後者是活用這個技巧的 Multi-Pattern Matching Algorithm!!
這個Wiki 的解釋也真的很好懂, 沒複雜的分析, 但很有說服力, 而且還說明了它跟其它String Matching算法的分別, 例如它說了 "Rabin-Karp始終是Hashing, 可以有很差的效率, Single-Pattern Matching上還是KMP佔優, 但它的強處是在Multi-Pattern Matching (其它的還有AC自動機)"

所以...基本上這題就是Rabin-Karp Algorithm的變種囉
詳細的自己再看上面的wiki-page吧

Rolling Hash 是一個技巧, 不一定要 "減頭加尾", 像這題, "換一個字母" 這類的事當然也做到
只要你是用Polynomial Hashing就行了

我想這題最難的是要說服自己時間複雜度
官方說是 O(L lg n) 我感到有點奇, 因為我自己AC的版本, 最低限度也是O(L lg n) 但這沒算上Hashing Collision後要做String Comparison 然後fail 這件事
理論上Hashing Function柒的話, 這件事可以發生很多次吧? 那就遠超於 O(L lg n)了, 因為要做很多次String Comparison, 這也是為什麼它用在Single-Pattern Matching時worst case可以跟naive algorithm一樣是O(NM)的原因...不過算了AC了就好了, 也可以這樣想吧: 一直以來所有人都是用Polynomial Hashing去比賽的, 這已經是定式了, 自然不會是一個"柒"的hash function...

以某黃字User的comment做一個結語:

Most hashes are certainly not unique or why do we use hash? If C is in ACM/ICPC, you can simply choose a prime other than 3 because the problem setter does not know which prime you used so he can not construct data against you. He can only guess some contestants will choose 3 and build some data to make them failed. However, in Codeforces, hackers can construct data against a solution. So you have to compare two strings themselves when the hash of them are the same. However the probability of two different strings have same hash is low so only a few strings will be compared. So, the hash helped you to evade TLE.

強烈建議看一下Code, 也是很有機的寫了一些comment
http://codeforces.com/contest/514/submission/10158032

D: (Binary Search, Two-Pointer Algorithm, Segment Tree)
這題有點難搞
原因在於題意其實很直觀, 就是不斷query 一個range maximum
所以我直接就用Segment Tree上了! 結果也是AC的
(原本有想過能否用BIT可以更易寫出來, 但maximum之類的好像不能用BIT做...只能做統計的工作啊)
http://codeforces.com/contest/514/submission/10172455

正如我的comment上所說, 這是overkill啊,
官方的答案是用一種叫 "Two-Pointer Algorithm" 的方法, 那個方法應用在這條題目上很高明
但實作上我自己是想不出來了, 紅字User們說是用兩個Stack的樣子
總之正解是易寫也很有效率

我反而學到了兩件事: 是否overkill也不要緊, 但起碼concept對, 寫得出來, 就可以AC的, 也不用這麼介意...
然後再來Google了一下什麼是Two-Pointer Algorithm...這東東很多題目都有Tag, 從來都沒認真想過是什麼的一類Algorithm

看了高手們的解說, 就比較清楚了:
這類Algorithm的運作通常是這樣的:
一個pointer指住第一格, 一個pointer 指住最後一格, 然後開始夾三文治
做某些東西或者checking, 然後移動其中一支pointer (不知會否有2支一起動的情況?)
一個pointer只能向單一方向移動, 而每次最少一定要移動其中一支pointer
這樣的話時間性一定是O(N)了
這類Algorithm好像很強大的樣子, 形象化來想有點像什麼Sliding Window還是 Sweeping Line的? 傻傻搞不清, 總之這種思路還是記一下好

E: (DP, Matrix Repeat Squaring)
另一題很想記下的題目!
因為這道題的重點在於當年聽過的Matrix Repeat Squaring應用
話說當年完全不知 "為何, 何時, 怎樣" 用這個技巧
還是CF的高手們好, 一個Reference就解得清清楚楚的說

先說一下題意:
一棵無限的Tree, 每個node 都一樣有同一set的兒子 (最多有10^5個兒子)
eg: root 有 3個兒子, 它的每個兒子也一樣有3個兒子....直到無限深度
每個兒子跟它的parent距離 (edge的長度) 最多是100
現在問有多少個node距離root 是 x ( x < 10^9)

這題很直接就能寫下DP的狀態:

dp(i) 為有多少個node 距離現在的node EXACTLY = i

然後答案就是

但難度在於 dp(x) 的 x 可以有 10^9 那麼大! 即使是 O(N)也超時 (也超MEMORY!)
怎麼辦呢??? 原來....原來....
原來這種情況就是要用Matrix Multiplication的Trick啊
在Editorial 挖金挖到一篇超上乘的tutorial 給我這種新手的
Matrix Exponentiation

But, what will you do if the problem says, given 0 < n < 1000000000, find f(n) % 999983 ? No doubt dynamic programming will fail!

這是它的前言, 說了最簡單的DP例子Fibonacci Sequence, 在 n 好X大的時候也是會吃屎的
而這就是 "Matrix Repeat Squaring" 出場的時候了!
這種加速的技巧只能用於符合某種"形式"的 Recursion Formula, 也就是DP Transition

| f(n) | | f(n+1) |
| f(n-1) | | f(n) |
M x | f(n-2) | = | f(n-1) |
| ...... | | ...... |
| f(n-k) | |f(n-k+1)|

直接引用它的解說, 其實就是先寫下類似以上的算式, 以他的notation

第一格就是我們想要的答案而其它的是計算答案時要用上的東東

然後我們逆算出 M 這個 n*n 的matrix, 之後的就簡單了, 把repeat squaring的技巧用在

matrix multiplication 上算出 M^x, 乘上我們的"base case" (最開頭的 n*1 vector)

就能得出我們想要的答案 (右邊的n*1 vector, 的第一格)

例如 Fibonacci Sequence, F(n) 要用上F(n-1) 和F(n-2) 對吧

右邊先寫上 B

| F(N) |

| F(N-1)|

左邊是比它"前一步"的States, 我們叫它A: | F(N-1)|

| F(N-2)|

然後要做的就是人手逆推 M, 使 MA = B

| ? ? | |F(N-1)| | F(N) |

| ? ? | * |F(N-2)| = | F(N-1)|

不難推出 M 是

| 1 1 |

| 1 0 |

那麼當我們要算 F(10^9) 的時候只要算 M^(10^9) * A , 然後得出的B 的第一格就是我們的 F(10^9)了!

其它詳細的看那個優美的Reference吧, 都說得很清楚了, 通常M 都會很有Pattern 不需要hard code就能generate出來的

由於是做 lg(x) 次 matrix multiplication, 假設matrix 是 N*N

那麼就是 O(N^3 * lg(x))

很好很強大的DP輔助技巧!

回到原題目上, 基本就是用這個想法, 當然作為Problem E也沒這麼直接

最不同的是我們要求的答案不是單一的 DP(X) , 而是 summation DP(i)

但也是大同小異的

首先注意到我們的A (也就Base Case的vector) 要用上全部DP(100) 個State

所以 X <= 100的時候, 直接用普通的DP就好了

當X > 100的話, 我們就要用上這個技巧了

注意先Update X = X-100, 因為現在我們的"Base"不是 0, 而是100

然後由於我們想要算的是 summation DP(i) 那麼乾脆把它放進我們的A (還有B) 內加上本來的 DP(1) to DP(100) 總共是一個

101 * 1 的vector

官方的notation是 1* 101的, 思路一樣, 我想我以後還是會跟Reference那個notation

接下來的就是逆推 M了, 這一步是這一題的唯一難度 M 是什麼可以自己看Editorial:
(注意它跟我 / Reference的notation不同, 應該是Transpose了還是怎的)

http://codeforces.com/blog/entry/16398

就是這樣了!

最後把AC的Code貼一下以作記念: comment應該也算清楚的日後重溫應該也明白的吧...
http://codeforces.com/contest/514/submission/10218534

2015年3月12日星期四

Codeforces Round #290 (Div. 2)

又一場在公司Virtual Participate 的round
可能題目較易, 這次也較少同事的打擾
成績也算不錯

第5題看了Editorial後了解是Flow的題目
Flow在計劃中還沒打算詳細學習所以就沒深究了
也就是說這場4題都是即場AC的算是很有運氣的一場

Codeforces Round #290 (Div. 2)

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

A: (頹題)

就考你寫 for loop的題目...

B: (Graph)

在很小的圖內找有沒有長度 >= 4 的cycle, 就暴力的用DFS

C: (String, Graph, Topological Sort)

這題有點有趣...不過也是很直觀的Topological Sort就是了

給了 n 條string, 它說明了"這些String是按lexicographical order"來排列的

這當然是指 a<b<c.... <z 了, 但題目也說了情況有點改變, 字母的rank並不是原本的rank

而是另一個新的食物鏈, 例如 e<d<a<z<x<g<h... 而input的lexicographical order是以這個新的rank來說的

現在求一個permutation of [a-z] such that 按這個permutation來比較字母大小

input的string 的而且確是順序排列的, 如果沒有答案則print impossible, 否則隨便print 一個合理答案就ok

由於 n 很小, 建圖不會像上一場那麼有難度了...直接考慮建圖後要做的事

這個有向圖求序, 根本是裸跑的Topological Sort, 有cycle 就是沒答案了

建圖比較有伏, 所以說一下:

我們用O(n^2) 來比較pair-wise strings, 找出它們第一個不同的字母, 這2個字母之間就可以加一條edge了

問題是要是完全沒不同呢? 那麼就直接看長度, 要是較短的排更前就對了, 不然就直接print impossible

這樣建了一個有向圖後, 就做Topological Sort吧

好吧,...我承認我出Cheat, 我抄演算法筆記的寫法, 我不害羞, 反正一棍過就好

好吧其實也不難理解, 也就是一個DFS, 用post-order 記錄 ordering, 跟上一場Euler-Path的道理也是一樣的...post-order時機的確很有用

D: (DP, Math, STL)

最後也最有成功感...也最有運氣的一題

我是用數學的方法做的事後發現題解是用DP?

這題的靈感也來自於Facebook Hacker Cup 2015 Round 1的Problem D

題目給了 n 張card ( n <= 300)

每張card有自己的費用c 跟距離 l

買了一張卡之後, 便可無限次使用, 功能是向前/向後跳 l 格 (由x 變成 (x+l) 或 (x-l))

你現在在第0格, 問如何用最少的費用, 令你能去"所有"的格子

如果不可能則print -1

老實說我是不知官方如何DP的, 我跟很多參賽者也是更低級的DP手法過的

而且題目是說要用某幾張卡鋪滿整條NUMBER LINE

就是無限的距離, 所以更像數學題的feel

我最初想到的是只要我有兩張卡, 它們的difference是1 那就一定行了

然後進一步發現, 好像是只要有兩張卡, 它們的GCD 是1 也可以的說

GCD啊...互質...我直接就去wiki找 Extended Euclidean 了, 但好像沒什麼關係.. (這個Extended什麼的學了這麼多年都不懂, 太神奇了)

然後我轉個角度想其它東西, 如果是多過2個數字的情況怎辦呢?

2個數字可以是因為 GCD(x,y) = 1 iff ax + by = 1 for some integer a,b

但如果多過2張卡的情況我是想要

a_0 x + a_1 y + ... a_n z = 1

而我所知的只有 x,y...z , 我當然希望有這麼一個定律

gcd(x,y,...z ) = 1 iff a_0 x + a_1 y + ... a_n z = 1

但印象中沒學過這樣的東西?

運氣這兒就派上用場了, 我在紙上想了幾個case, 剛好都好像match這個rule

我就猜想是這樣了, 就這樣做下去吧, 那兒來的膽啊...

要是這樣, 問題就要改寫一下了, 改寫成數學一點的形式吧

given set {a,b,c....} 求 non-empty subset X such that GCD(x0, x1...) = 1, 而且是最平的

這兒說一下, 每個數字(就是原題目中的距離) 可以是 10^9 那麼大

那麼....可以怎麼做呢?

這時Facebook Hacker Cup的慘痛經驗又派上用場了

我再猜想不論怎樣, 不同的GCD數量很少

(還記得FB Cup 那題的Color其實也很少嗎...凸)

要是這樣的話就好辦了, 用DP!
設DP(g) := 任意set 的gcd 為g , 最低的cost

DP的方法嘛...很抱歉的說, 我不能很好地寫出來

我當時是邊code邊想也覺得很對就做完了發現跟普通的DP有點不同很難把transition好好的寫出來

總之思路就是用STL的set 儲下所有gcd (因為我猜想數量不多)

然後iterate 所有卡, 每張卡都去改動這個set, loop這個set 同時update DP state

  st.insert(a[0]); mp[a[0]] = c[0];
    for(int i=1; i<n;i++){
        if(mp[a[i]]<= 0 || mp[a[i]] > c[i]) mp[a[i]] = c[i];
        for(set<int>::iterator it = st.begin(); it!=st.end(); it++){
            int x = *it, g = gcd(x, a[i]);
            st.insert(g);
            if(mp[g] <= 0 || mp[g] > mp[x]+c[i]) mp[g] = mp[x]+c[i];
        }
        st.insert(a[i]);
    }

也就是每次有一張新卡, 我都做以下的事:

跟暫時所有得到的gcd 跟它都算一下gcd, 並且把新算出來的gcd 加進set內
跟暫時所有得到的gcd 跟它算一下gcd g, 然後看要不要update DP(g)
就直接一張卡自己去看能不能update DP(), 還有把它自己加進set內這主要是應付有一張卡本身已經是 1 的情況

實作如上面貼的, 用了STL的Map 做DP的容器, 用Set 儲下gcd....

很亂來吧

時間我不懂分析, 因為大部分都是猜想的, 我也沒想到過了...(雖然很勉強)

那麼當然就要看Editorial跟Comment了

首先,,,猜想1...有神人果然貼了這條rule

Bézout's identity (看Generalization 的部分)

For three or more integers

Bézout's identity can be extended to more than two integers: if

$\gcd(a_1, a_2, \ldots, a_n) = d$

then there are integers $x_1, x_2, \ldots, x_n$

such that

$d = a_1 x_1 + a_2 x_2 + \cdots + a_n x_n,$

has the following properties:

d is smallest positive integer of this form

every number of this form is a multiple of d

d is a greatest common divisor of a₁, ..., a_n, meaning that every common divisor of a₁, ..., a_n divides d

所以基本就是說 [a-z]的gcd 是 1 的話, 就會有它們的multiple的sum = 1 ....好可怕

至於猜想2 就要看這兒

http://codeforces.com/blog/entry/16147#comment-210808

In fact, 735134400 has 1344 divisors, so a safe guess would be 1500.

看吧!! 人家都是Guess來的...只是有很好的理由他們總是有很好的理由去guess一點很重要的hint

至於官方解法...我也沒深究了, 因為被大部分User屌到上天花板, 說"不用那麼複雜啦" , "就暴試所有gcd啊" 之類的

2015年3月11日星期三

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都要

in-degree = out-degree (無向圖則無視這點, 因為不能分什麼叫in-out)
從1看來, degree數要是雙數
從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|, 因為圖可能不連通

總結的話算法是這樣的:

查一下degree的條件, 是否有"可能"有Euler Path / Circuit

如果可能的話順便記下起點和終點

DFS, 用post-order的時機記下整條Path / Circuit
確認一下Path / Circuit的長度是否正確, 因為圖可能不連通

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

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

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

好吧回到題目上了

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

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

看穿這是Euler Path的本質
建圖的方法, 技巧 (方便的Code法, 不超時的方法...etc)
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:

2 3

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的證明基本思路跟信心吧..!!

2015年3月5日星期四

2015 Facebook Hacker Cup, Round 1

說好的Facebook Hacker Cup 2015, 終於有空寫了
事實上在前幾天才做完四題...
FB的比賽很不好地沒有practice mode 幸好偉大的CF以Gym的形式提供了練習途徑
Gym在沒有AC前不能看Test Cases 和別人的Code就是了...

這場比賽有4道題目, 難度我覺得是CF 較難一點的Div. 2 吧..?
比賽使用計分制, 實際執行時間也有幾分鐘, 這是我一直在想的問題
因為大部分比賽只用1秒, 算法也比較易逆推出來
數分鐘的話反而很混亂, 好像什麼 "不正常" 的算法也有機會是官方的答案...

即場我只做了2題, 而規則上所有跟第500名同分的人都可以去Round 2
沒想到遠超過500人4題全對了...
我交的2題也只AC了1題, 另一題錯了一個白痴的exceptional case...唉!!

還有另一題沒有做的, 其實不是難做, 是語癌的問題, 直到現在我也搞不清楚是我英文差還是什麼原因, 總之完全不明白題目的意思, 跟Test Case怎樣理解也有點矛盾, 即使AC了也是半合理地
推斷"題目是這個意思"...這個有多少生氣跟遺憾

最後一題則是看了答案後更加知道沒有抵賴的餘地, 現場是怎樣都不會做到的, 主要原因是...算法是想到了, 倒是算法的parameter limit 我完全沒有頭緒, 暴試的話怎樣也會超時...
所以即場我是"打倒自己", 感覺那個算法是錯的, 有其它方法....原來方法是對的, 倒是有聰明的想法證明parameter limit很小...

2015 Facebook Hacker Cup, Round 1

題目: http://codeforces.com/gym/100579/attachments

A: (Math)

Given range [A,B], B<=10^7, 問有多少數的primacity = K, K<= 10^9
primacity的定義是 # of distinct prime factors

這題算很易了...就是改一下Prime Sieve (就普通的Prime Sieve, 不用前文所說的Linear Sieve)
每次刪去合成數時把該合成數++, 代表這個合成數又多一個prime factor了
是我唯一現場AC了的題目...

void make(){
    p[0] = p[1] = 1;
    for(int i=2; i<10000005; i++){
        if(!p[i]){
            for(int j=i; j<10000005; j+=i){
                p[j]++;
            }
        }
    }
}

B: (String, Trie, STL)

正是我說的語癌題!!!
其實看時已經知道是用Trie / 字典之類的方法做了, 數據量問題不太肯定能不能用STL做
事後知道是OK的, 但我也說了想借此機會也應用一下Trie, 就用Trie做了
這題沒難度的...只要理解了題目的話!!!

題目大意是: 給定一堆字, 現在想把它把儲進電話內做autocomplete. 那麼當然是打該字的prefix就ok了, 然後問最少total打多少字....重點的一句是這樣的: The prefix must either be the whole word, or a prefix which is not a prefix of any other word yet in the dictionary.

媽啊, 你UP咩春呀...
最開頭也直接的想法是: 啊, 當第某一個prefix已經儲進去了, 之後就不能再以同樣的prefix代表這個字了
這樣的解釋連第一個test case也過不了, 因為要是這樣, 第4個字的prefix就是 "hi" 不是"hil"

那麼...是不能跟已經儲進去的prefix所代表的那個字一樣嗎? 然後 either be a whole word 又是怎樣, 是說整個字都是另一個字的prefix要特別處理嗎??

靠, 怎樣想也不能同時滿足所有test case, 尢其第3個

而這樣導致的結果是, 我知道是用Trie做也無從入手....語文能力是多麼重要啊...

好吧, 開估吧, 以下是正確的題目意思:
每次加一個字進字典時, 盡量加最短的prefix, 但這個prefix 不能是前面其它字的prefix!

所以sample test case 1 第4個字不能入"hi"! 因為第1個字已經是"hi", 即使第一個字儲進電話的prefix是"h"而已也不行!

然後test case 3 答案是11 並不是我原本想的 "4+3+2+1+1"...而是"1+4+3+2+1"!!!
解釋是第一個字當然就入一個字母的prefix "a", 然後第2個字, 不論怎樣切都是第一個字"aaaaa"的prefix, 所以就只能以"whole word", 也就是"aaaa"這樣加進電話...之後的字也一樣

他媽的, 明白題目是這樣之後就是直接應用Trie了...我也知道我第一次寫Trie
但的確是直接用而已...你媽的語癌題目

有關Trie的理解跟應用 (以及其它String Matching的Algorithm) 我打算另開一篇詳寫, 因為近來很巧的做了兩場CF也有兩題題目學到新東西了...

這題一句, 用Trie! 每次加字就一個個字母插進去...一發現還沒生成該node 就是前面沒有相同的prefix了...采用之!

另外如之前說的, 這題用STL的Map 好像也行, 其實重點還是題目的理解啦...

C: (DP, Combinatorics)

第二題即場有交的題目...而且是"正確"的!!!
我只是沒有處理一個特殊的Base Case而已...而且那個Base Case也是反直覺得很嘛...
老實說Download完input file後我也有特別留意這個Case, 反而我是認為我的output對才提交的呢...

題目有點複雜, 給了一個體育比賽的完結分數, 例如 3-1
代表第一隊以3分勝出, 第二隊拿了1分, 就輸了

然後定義一種叫"無壓力勝出", 是說勝出的隊先拿了第1分, 然後一直到完結它的分也比另一隊高!
另一種叫"無限壓力勝出", 是說勝出者直到敗者達到它的完結分數之前, 一直也比敗者隊低分!

問題是數出有多少種不同的組合可以"無壓力勝出" 及 "無限壓力勝出"?

簡單來說, DP, 而且是2個DP, 2個互相很像, 沒有交集
無壓力勝出較易數的, 另一個因為敗者到達結果分數後你可以反超前, 較難數, 但也大同小異

詳細就不寫了, 也不太記得了, 直接貼Code...
而我中的伏是...是...是敗者0分的情況..? 好像是...不太記得了
總之是一開始敗者已經到達完結分數, 這樣的情況下組合只有1, 而我的DP出0了...
真的只差這一個Case, AC與WA之差....!!!!!!!

  dp[1][1] = dp2[1][1] = 1;
    for(int i=2; i<=a+b; i++)
        for(int j=1; j <= a; j++){
            dp[i][j] = dp[i-1][j-1];
            if(2*j > i) dp[i][j] = (dp[i][j] + dp[i-1][j])%C; //無壓力勝出
        }

    for(int i=2; i<=a+b; i++)
        for(int j=1; j<=b;j++){
            dp2[i][j] = dp2[i-1][j-1];  // 有壓力勝出
            if(2*j >= i || j == b) dp2[i][j] = (dp2[i][j] + dp2[i-1][j])%C;
        }
    printf("%I64d %I64d\n", dp[a+b][a], !dp2[a+b][b]? 1: dp2[a+b][b]); //特別處理中伏CASE

D: (DP, Graph)

最後的一條好題目...
只能說我輸了

題目很簡單的, 給了一棵Tree, size N <= 200,000
要color這棵樹, 但每個node不能與它的parent一樣color
color 由 1開始到 N, 無限量使用, color i 花費 $i , 問total 最少多少錢才能完成coloring?

當時還沒學到Bipartite Matching, 但當然現在直接就會想到, 2-coloring吧?
但很明顯沒這麼簡單的...

看官方FB的Solution, 2-coloring不一定是最好的吧...

這種Tree的題目, 很易想到DP去, 但先慢慢想一下
最初想的, 會否有Greedy的水分在內... (因為是Round 1...這個心態真的要改, 害死我很多次)
Greedy來說, 會否由根一直把能填最小的都填, 又或者由葉一直填上根?
很可惜的我自己也找到一堆反例子

在一直寫反例子的途中, 有個感覺, 就是可能會使用到的color數目不會太多...但證實不了
結果這就是問題的重點...我當時想到的是, 既然Greedy好像不行, 只能DP了

設DP(x, c) 為 node x 使用 color c 時, 以它為根的subtree 的minimum cost
問題是c 實在可以太大了, 可以到N 啊...
那時我的確沒想到, 也想不到, 如果 c 很小, 其實問題就解決了...
也就是說...!
這個DP是正解, 讓我來貼一下CF高手們的答案

也沒什麼好解釋的, 有點self explain, 感覺就一定對的了....
所以這題最後一題的難度是在證明 c 很小啦!!!!

官人來看, 小的找到兩個不同的方法去證明...一個簡單易明但有點出cheat的, 另一個是官方FB的嚴謹數學證明!

先來看簡單易明的Version:

由某CF高手提出, 我們想要證明的是 會用到的不同color種類很少, 這個數字跟Tree Size N 有關係。
有點逆向思路, 來定義一個function C(x):= Root node一定要使用color x的話, 達成的minimum cost 的Tree的minimum size. 有點語癌, 其實不難明, 看頭幾個數字:

C(1) = 1, 代表的是只有一個node的Tree, 它能達成最minimum cost就是1, 也是我們的x
C(2) = 2 對嗎? 因為 root 使用 2, 它的獨生子用 1....很可惜這是錯的
C(2) = 3 才對!! 因為我們希望這是唯一的樹, 它是最小的, cost也是最低的, 然後root 一定要使用 2, 所以就是 root使用2, 兩個兒子用1, 這3個node的color怎樣變也不會比這個填法更優
而如果只有獨生子, 則那個樹不是唯一的, 因為也可以root 用1, 獨生子用2, 同一個size, 同一個cost, 但root 可以不使用 x=2 為color

C(3) 開始複雜了, 直接套用該高手的話:
root要是3的話, 它最少有3個color 是1的兒子, 不然可以把全部color 1 的孩子(最多2個) 變為 2, root改為 1, 導成相同的cost相同的size...
同樣道理, 它最少有 2個 color 是2的兒子
那麼C(3) 最少是 1 + 3*C(1) + 2*C(2) = 10

小總結, C(1) = 1, C(2) = 3, C(3) = 10....怎樣, 有點Pattern / Sequence的感覺吧??
然後高手說, 把這個數字去OEIS找一下, BOMB! 出現鳥!
Number of order-consecutive partitions of n

1, 3, 10, 34, 116, 396, 1352, 4616, 15760, 53808, 183712, 627232.... 這個當年KN介紹的神網想不到在這兒能夠用上... 那麼廢話就不多說了吧...實際上 c 去到 ~11-12, 最小的樹已經超過200,000個nodes... 也就是說我們的DP是可行的, 也就 O(N*c)而已!

下面是FB官方的數學方法:
We can also prove that O(log N) is an upper bound for C. Let C(k) be the size of the smallest tree that needs all colors 1, 2, ..., k in an optimal coloring. Trivially, it holds that C(1) = 1 and C(2) = 2. Without loss of generality, we can pick the node with color k to be the root. In that case, the root needs to be adjacent to all colors from 1 to k-1 and we can apply the inductive hypothesis as follows:

C(k) ≥ C(k-1) + ... + C(2) + C(1) + 1 ≥ 2^{k - 1} + ... + 2¹ + 2 + 1 = 2^k
^{這...這個是傳說中的M.I. 啊...思路是直接猜想 c ~ O(lg N), 逆向只要證明到上面那句statement就ok了...我說我真的不能即場就有這麼嚴格的證明啊..}
^{CF另一些高手的思路想像, 卻更像是比賽中可以學習使用的想法:}

I think there is: a[1] = 1
a[x] = 1 + 2 * (a[x - 1] + a[x - 2] + ... + a[2] + a[1])

At least 2 v values must appear in children. If there is only one v < x value, you can swap it with root and you have v in root.

So a[x] = 3x - 1 I assumed second y < = 13.

思路是一樣的, 也是很roughly地寫出 color = x 的root 下面最少要用多少個兒子
然後不用直接找lower bound, 但upper bound已經是 O(lg N) 了....這個思路也真的要學習下

順帶一提, FB官方也有說到這題有O(N)的解法, 解法很巧妙, 我不知怎樣實現就是了
大約就是不用把10多個color暴試, 只要試"最好"的2個color就好了
然後precompute 最少要給多少錢, 然後看看那些node要將就使用"第二好"的color 就把它加上那一個offset...詳細自己看官方答案: https://www.facebook.com/notes/1047761065239794/
我是不知道怎樣找出"最好"的2個color就是了...

來個小總結, 這是一場學到很多東西的比賽, 而且只是Round 1, 了解到自己實力很不足啊
以前的話應該會很不開心吧, 現在好像沒那麼介意了, 還有點小開心可以繼續進步學習挑戰, 我想我是瘋了 0.0

訂閱：文章 (Atom)

2015年3月16日 星期一

New Spam in Codeforces?

2015年3月15日 星期日

Codeforces Round #291 (Div. 2)

Codeforces Round #291 (Div. 2)

2015年3月12日 星期四

Codeforces Round #290 (Div. 2)

Codeforces Round #290 (Div. 2)

A: (頹題)

B: (Graph)

C: (String, Graph, Topological Sort)

D: (DP, Math, STL)

For three or more integers

2015年3月11日 星期三

Codeforces Round #288 (Div. 2)

Codeforces Round #288 (Div. 2)

A: (頹題)

B: (頹題, Greedy)

C: (Greedy, Math)

D: (Graph, Euler-Circuit, Hashing)

E: (DP, Greedy)

2015年3月5日 星期四

2015 Facebook Hacker Cup, Round 1

2015 Facebook Hacker Cup, Round 1

A: (Math)

B: (String, Trie, STL)

C: (DP, Combinatorics)

D: (DP, Graph)

2015年3月16日星期一

2015年3月15日星期日

2015年3月12日星期四

2015年3月11日星期三

2015年3月5日星期四