Codeforces Good Bye 2014

這也是一場我很想寫下的一篇...
一場Div 1 + Div 2一起打的比賽
這類比賽如果即場參加應該當炮灰了

總共有7條題目, 勉強做了前面4題...

Codeforces Good Bye 2014

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

A: (Graph? 頹題)

題目直接一個簡單的DAG, 基本上起完圖 (實際上不用真的"起"出來)

按住題目由起點到終點跑一次就完了

B: (Graph)

一題即場不懂做的題目....其實還是很簡單的...

題目給了一個Permutation 和一個0-1 Matrix, 代表該Permutation
任意兩個位置能否互換

問lexicographical smallest 的Permutation

其實只要發現, 互換的位置其實是一個connected component
然後該component內的數字完全可以完美排序, 用類似 bubble sort的方法就可以了...

所以基本就是求出所有connected component, 把每一個component內的數字們排好序就是答案

C: (Greedy, Ad-hoc)

對我來說不知為什麼很難的題目=.=

很Ad-hoc, 要是以前應該會跑去想DP了...

其實是沒什麼算法的..只要有一個Observation...自己跑去看editorial 吧...

D: (Graph, Combinatorics, DP?)

最有成功感的一題, 是完全自己想到的....可惜, 昨天再想起時, 竟然完全不明白為什麼自己會想到, 甚至不明白為何自己的解法會AC...所以..我盡力寫吧=.=

題目是這樣的, 給了一棵Tree, edge有weight, 問任意選3個node (c1,c2,c3)
這3個node互相的最短路線的總和 expected value是多少?

一看題目就很有counting的感覺了...總之先試著寫一下

大約是  [所有 可能性 的總和 /  nC3 ] 的感覺吧

所以就是 6 * [所有可能性的總和] / n*(n-1)*(n-2)

問題是 [所有可能性的總和] 怎樣算? 

不知怎的, 又運氣到了, 我覺得可以換個方法數: 

數每條edge 總共會用上多少次怎麼樣?

假設我知道每條edge 在所有 combination之下, contribute了多少次

然後把每條edge 的contribution 加起來也就是答案了

那每條edge 會用上多少次呢?  這時發現到樹上的每條edge也是bridge

然後...就是說該條edge 把graph的點分成兩堆, 由一堆去另一堆必需要經過它的

設 X 為一堆的SIZE Y為另一堆的SIZE, w 為 該edge 的weight

那麼該條edge contribute了 X*Y*w的 value啊...

這時發現了,  這也只是任意取兩點的總和...可題目是任意取三點啊..好像又有點不對

數呀數, 好像發現了一件事

假設 3點(a,b,c) 是會用得上這條edge的, 當中一定有2點是在堆的兩邊 (廢話)

假設 這個ordered tuple (a,b,c) 的頭2個頭就是在堆的兩邊, 那麼第3個點有多少選擇呢?
正正是 n-2 ! (不是factorial -.-)

換句話說我先fix死order pair 頭2個點 (a,b, ?)  先不管第3點, 由於a跟b 剛好要在堆的兩邊

(a,b,?) 的選擇數 正是 上面說的 X * Y, 然後第3點 只要不是頭2點的都OK, 所以是n-2

這樣選會double count嗎? 是不會的 (我沒很大信心就是了)
因為我們的tuple 是 ordered tuple, 條件是頭2點要各自分開在兩個堆, 意思是這樣必定會使用了該EDGE一次

所以 假設其中一個valid的tuple 是 (3,5,4)  就是說 node 3 跟 node 5 的path中必定經過該edge 一次, 這兒其實node 4 是完全不影響的, 也沒考慮

然後假設 node 4 跟node 3 是不同堆的 (就是node 4 跟node 5是同堆的)

必定會另有一個valid tuple (4,3,5) 或者 (3,4,5) (只會數到其中一個, 因為我們是用tree size X*Y來數, 不然就真的會重覆數了)

這兒說的是 node 4 跟 node 3 之間的path也會用上該edge 一次

注意到了嗎? 同樣是選了 (3,4,5) 這三個nodes, 但我們把題目要求的 d(3,5) , d(3,4) 拆開來數了

所以(3,5,4) 跟 (4,3,5) 都要數, 並沒有錯也沒有重覆

那麼最後的最後算式就出來了...

6 * (n-2) *  Summation ( X*Y* 某條edge的weight) / n * (n-1)*(n-2)

約簡後就剩 6*Sum / n*(n-1)

當中X跟Y是以該條EDGE作為Bridge, 兩個end point 的sub tree size

這兒的tree size可以用一次DFS (Editorial 說是DP) 來找

基本隨便找個node作root 作DFS一次,  然後 X跟Y分別是

size (end point 1),   size (end point 2) - size(end point 1)

原因是其中一個end point必定是另一個的parent, 它的size 減去另一邊的size才是真正"拆橋"後的sub tree size

最後的最後...這題真的要看editorial, 分別有兩個不同的editorials

兩個都有不同的數法, 連我自己的共有3個 ...

其中一個易明一點的 數的時候是全部都數, 然後約掉重覆的數目 (就是除 n*(n-1)*(n-2)而不是nC3), 解公式時我不同明白為何它可以一步就變了個(n-2)在分子...

另一個是用expected value的linearity + symmetry, 說明可以把題目化為一條條edge的數法

說真的, 這條能過真的是運氣, 完全不是實力=.=  (但是這條也破千人過了)