Codeforces Round #286 (Div. 2)

老實說一句, 這場真的不想記下的
因為只做了3題, 然後題目也很難...
但還是有記下的價值的, 其一是因為這場是久違的virtual participate
雖然在公司內走出走入, 還是有很多時間浪費了
但由於這場真的比較難, 大部分人做了3題排名也很前了, 我覺得時間反而不是太大影響就是了..

有見及此, 竟然也拿到全場37名, 有點騙回來的感覺, 因為題D我認為是有可能做到的...
都想了個大概了, 可惜要用上SCC的概念, 我自己不熟悉而已...

Codeforces Round #286 (Div. 2)

題目在此: http://codeforces.com/contest/505/problems

A: (String, Ad-hoc)

題目很簡單, 給定一條String s, 問在任意位置insert 一個字母, 能否變成Palindrome
隨便輸出一個Palindrome就可以了, 要是不行的話就輸出"NA"

就...就是做吧, 但Code下去也是比其它題A難一點就是了...

B: (Graph)

給定一個圖, 可以有multiple edges, 每條edge有一種顏色, 然後給它一堆queries,
每個query問 兩個點 u , v 之間要用相同的顏色直接或間接連起來的話, 有多少種顏色符合?
看題目下面的圖解會更易明白

由於數據小的問題, 就直接DFS就可以了...
有趣的是, 我跑去看Editorial的時候發現Div. 1也有一條完全一樣的題目, 只是數據非常大
然後就已經一點思路都沒有了...果然算法最主要針對的是數據, 不是題目模型...

C: (DP)

題目給了一條number line, 上面只有0 - 30000 的位置, 某些位置上可能有某個數量的寶石
一個人原本站在第 0 點, 他一定要跳去第 L 點, 然後下一次他的移動距離可在(L-1, L, L+1) 3種內選擇, 假設他選了L-1,  再下一次的距離可在 (L-2, L-1, L) 裡面選...如此類推
問直到不能再移動的時候, 他可以獲取到最大限度的寶石數目

很Greedy很DP的感覺吧, 問題是L 最大可以是30000, 位置也有30000,  那麼只要DP State是2D以上, 已經超時 / Memory了...

這題開心的地方在於, 本來的思路是一直跑去想Greedy...
大約是像 "什麼時候會選 -1, 什麼時候會選+1...要是L變成1的話, 那麼以後全部都是1 肯定是最好的吧...." 這樣的
然後就開始想, 會不會是有什麼機關令這個人可以用"很快"的速度, 使他的移動距離變成 1 呢?
反正變成 1 的時候就完了嘛, 之後肯定是全部都移動 1 格, 把所有寶石都拿走
然後發現最快的"下降"速度, 也只是每次移動都 -1...
但在下降期間有可能會skip了一些有寶石的位置, 令答案不是最優...
所以應該不是簡單的Greedy, 不斷選 -1, 直接距離變成1 的方向了...

但DP是死路....這時有點運氣, 不知怎的先是發現題目定下30000這個數字很奇怪
然後再想到之前某一場某一題DP用過的一些技巧...就是把某一個Dimension減少的技巧...
說是技巧, 其實是Observation, 發現到數據只是嚇人的, 實際上不會全部用上, 也就不用開那麼大的Array...這題也是這個道理!

事實上, 考慮一下這個人最多跳多少步會去到不能再移動?
咦? 先假設這個人每次都選擇+1 吧...而他一開始最少的L是1, 發現大約跳240多步, 就會超越30000了 , 也就是跳出Number Line, 沒路了!
同樣的, 考慮他每次都選擇-1, 也是發現他大約跳240多步就會走到盡頭了 (其實這也是上述Greedy地最快令L變成1的結果)
那麼雖然移動距離好像有30000個選擇, 但相對起始狀態L的選擇只有24x+24x ~ 500個!

那麼就易辦了, 來定義DP State:
State(i,j) := 在第 i 點,  相對起始移動距離L的變化為j 時最多收集到的寶石數
Transition很簡單的, 只是每次跳下一個距離時要把實際距離算一下而已

 for(int i=d; i<=30000; i++){
        for(int j=0; j<500;j++){
            if(dp[i][j]!=-1){
                ans = max(ans, dp[i][j]);
                int rd = d+j-250;
                if(i+rd > 0 && i+rd <=30000 && dp[i][j] + v[i+rd] > dp[i+rd][j]) dp[i+rd][j] = dp[i][j]+v[i+rd];
                rd = d+j-250+1;
                if(i+rd > 0 && i+rd <=30000 && j+1<500 && dp[i][j] + v[i+rd] > dp[i+rd][j+1]) dp[i+rd][j+1] = dp[i][j]+v[i+rd];
                rd = d+j-250-1;
                if(i+rd > 0 && i+rd <=30000 && j-1 >=0 && dp[i][j] + v[i+rd] > dp[i+rd][j-1]) dp[i+rd][j-1] = dp[i][j]+v[i+rd];
            }
        }
    }

上面rd 是 real distance,  v[] 是寶石數

這場最開心的是, 在公司走出走入的情況下, 還能在比賽時間內 A-C都一棍過有不錯的排名...
還算是這樣了吧


順帶一題, 題E沒有看題目, 題D如之前說的, 是有SCC概念的題目
而且一定要用上Topological Sort, 但詳情就不清楚了, 也沒動力去研究了...這陣子有點心散
(其實是想花點時間跑去玩Unity跟Maya)

Codeforces Round #287 (Div. 2)

2015年大年初一
還是先把要做的做完...就是把解題過程記下..

這場是"回頭"打的#287,  所以上一篇先記下#289...
#286也有做的, 可是該場較特別...下篇再記 (順序什麼的先不管了=.=)

Codeforces Round #287 (Div. 2) 

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

雖然這場也是5題做完..可是這場比較特別, 在於題D我卡了好幾天, 最後的最後才發現自己中伏了...然後也好不容易才AC的...題E相對下還易很多呢..起碼是短時間內自己過的...(雖然是某個圖論的白痴東西弄到錯了很久..)

D跟E也要花點時間說呢 zzz...

A: (Greedy)

一題赤裸裸的Greedy...沒什麼好說的

B: (Math, Geometry)

這題比較令我出奇地覺得原來Div 2的題B也可以這樣啊...然後才發現原來也是很直觀的說

分類上絕對是Geometry, 但Geom也是Math的一部分, 也就標上Math的Tag好了...

上圖就是題B的題目, 就是給定一個圓形, 然後在邊上任意一個點作pivot, 然後該圓形可以繞住pivot轉一圈, 這樣算一步。問要多少步才能使圓心由原本的位置轉到目標的位置?

這類的題目很自然一想就會想到Shortest Path, BFS 之類的東西...

拉上Geom也好像很複雜...

但是只要在紙上畫兩畫, (或者腦子強的空想一下真實的情況)

不難發現一步之後, 圓心的軌跡 (Locus) 很有趣...

(Locus 是不是這裡正確的用語? 我也不太清楚, 只記得中學時老師說過Locus已經不再考了, 但我想一定是個很有用的道具吧...)

看我上面漂亮的小畫家圖...

黑色是原本的圓形, 紅色是繞住pivot 轉動時的圓形位置, 然後籃色虛線就是圓心的"走向"

也就是圓心的Locus

然後這只是假設pivot是定在那個點的情況, 實際上pivot可以在黑色圓形的邊上任意一點

發現到Locus也是一個半徑一樣的圓形, 而圓心剛好就是pivot位置

結論就是在任意選pivot的情況下, 圓心的Locus是以黑色圓形的邊任意一點作圓心來畫圓形的Union

按上圖來想像一下, 就是有很多藍色的圓形, 一個疊一個的, 組成了一個跟原本圓心一樣, 兩倍半徑的圓形

總結一下的話,  就是在一步內, 圓心可以移動到一個兩倍大的圓形範圍內任意位置
這樣的話, 到目標點的最少步數就很易找了....就是拉直線然後Greedy地一直走過去吧

實際上可以寫成公式, 所以是O(1)

C: (Graph, Tree, Ad-hoc)

一題很奇怪地不知怎麼被人Tag為Math的題目, 後來看Editorial才知道我的解法不是官方的

好像是跟某堆User一樣, 是O(h)的解法, 比官方的好一點...

題目有點Counting的意味, 給定了一系列的instruction, 基本就是, 由根點不斷"左右左右..."地向下走, 直到葉就回上一層...然後問, 要到達某一個葉子前, 會先經過多少個nodes?

這題我的解法是很簡單的逆向思路...

首先由終點向上走...會發現一個很單純的事實: 如果終點是 RIGHT CHILD, 那麼在上一層時的instruction一定要是"右" LEFT CHILD的話就是"左"

那麼要是在instruction 必需要是"右" (才能到達終點) 時的instruction, 不巧是"左"的話

很自然地該點的所有左子孫都會經過....關於這點我沒有很詳細的思考過程, 反而是有一個

很人性化的想法說服了自己: 要是該點的左子孫內有點不會經過的話, 那麼要是問題的input是裡面的其中一個葉子怎麼辦? 題目也沒說明沒有solution時要怎麼做...就是說每個葉子都可以自然走遍的....很有說服力吧=.=

回到問題上, 這樣思考的話就是說: 由根點開始走到目標點的路只有一條 (Tree...)

我也清楚知道這條路的走法 (eg: "左左右左右右左右...") 然後我也知道instruction是"左右左右"不斷loop的, 那麼當一個instruction跟我要走的路需要的instruction不同的時候, 就是"走錯路", 而走錯路是必定會經過下面所有子孫, 才會回到該點, 然後就走回正路去下一層...一直到終點

這樣算法就很簡單了: 先找出由根點到終點的路線, 然後以O(h) 的Loop, 試住左右左右的走下去,要是"走錯路"的話, 就把答案加上"錯路"的sub-tree size, 由於是full binary tree, 不用precompute也可以, 最後把答案加上 h-1, 因為根點到終點的路本身就會經過h - 1 個點啊...

D: (DP, Combinatorics)

題目簡單卻陰濕 (其實是我低能...), 答案很難寫...起碼我看過別人的code, 也不是很直接就寫完的DP...

題目是這樣的: 

求符合以下條件的數字總數目 mod m

該數字要有n 個位 (沒有leading zeros)

該數字要有suffix y, y > 0,  y % k = 0

n,k,m 也是input,  n <= 1000, k <= 100, m <= 10^9

要說的話, 這題最直接想到的也是直接的DP做法

State就是這個吧: 

State(L, r) := 長度為L的數字而 mod k 之後剩 r 的數字數量

這樣也只有1000 * 100 個State, 很有DP的樣式

問題在於, 怎樣數呢?  做過一些Combinatorics的題目也會知道, 怎樣去防止repeat counting絕對是重中之重, 只要這個搞定了, 其它也只剩簡單數學 / implementation技巧而已...

然後這個開頭我是難倒了, 甚至完全想錯方向, 不知怎的竟然走去想 inclusion-exclusion principle了...

事實上是很簡單的...在於這題的context上, 不要重覆數的同義解釋是, 用長度為L的suffix數出來的, 跟長度為L' 數出來的要不交集 (L' > L)

就是說在算 State(L', 0) 的時候, 我不可以算一些由 State(L, 0) 來的數目 

也不是直接 State(L'-1, r), r > 0 就可以的, 因為這個state也可以包括來自某些State(L,0), L' -1> L 的數目...

想到這兒, 自然就會想到在算任何的State時, 也不要用上 r = 0的State...這兒會發現這題用bottom-up / iterative 的寫法絕對更易想/寫

以iterative的想法, 一個State(L,x) 轉移去另一個State(L+1, r) (我較喜歡用"生成" 另一些States) 的physical meaning 就是在某一個長度為L, mod k = x 的數字, 加多一個digit [0-9],  變成長度為L+1, mod k = r 的數字,  而上面的說法就是說當x = 0時直接skip, 不要用它來"生成"其它States

去到這兒, 複雜度是 O(N * k * 10) = O(N*k) 還是ok的, 再來看一個完美的圖解

上面代表長度, 下面代表mod k 後的數字...

紅色就是現在iterative的位置, 我們的目標是要加一個數字令到加上 234 mod k = 0

假設我們填了5 吧, 那麼所有 "????5234" 的數字都是答案之一了, 而且我們之後不會再數到suffix = "5234"的數字吧? 所以這兒就要一次過數了

那麼簡單的counting,  我們還有4個位沒有填上, 除了最左的位置之外, 中間所有位置都是任填 [0-9] 就是10 個choice, 最左的位置是9個choice,  所以就是 9*10^(n-3-1-1) * State(4,0)

這樣的想法很對吧? 最後special handle一下 n = 1的case, 因為 suffix不能為0, 而 0 在n = 1時一定會包括的, 那麼 n = 1時把答案減去1 就好了....

然後當然果斷WA了...老實說這樣做連test case #3 也過不了 但確實想不到那兒錯了

看了Editorial, 你他媽的用Top-Down啊...幸好下面comment有人說了bottom-up, 跟我的做法是一樣的說...

連State definition跟公式也都一樣, 細節上例如不用 r = 0 的 state 生成其它state 也都一樣了...

那麼錯什麼呢?

很幸運地, 在昨晚喝了些酒的狀態下終於發現了...我中伏了!

"因為 suffix不能為0, 而 0 在n = 1時一定會包括的, 那麼 n = 1時把答案減去1 就好了...."

這句是bullshit, 完全錯的!

因為不止是n = 1,  事實上不論n是什麼, 要是suffix只有0 mod k = 0, 的話, 不就是 y = 0了嗎?
記得題目條件是 y > 0 的吧....

所以不止是 n = 1時的0 才有問題, 例如k = 3,  n = 2,  那麼10也是不行的, 因為唯一mod k = 0的suffix就是0 啊...同理, 30是可以的, 因為除了0之外, 30也是mod k = 0的suffix

考慮了這個原因, 題目又更複雜了...

我也不想大改我的code / state definition

事實上, 那時我才明白為什麼有很多黃字/紅字user的state有3個甚至4個dimensions,

其中一個是 0-1 flag特別處理這個問題的 (就是有沒有suffix 是全部都是0...)

老實說這樣改了State是一定能過的, 但我不想

我也看到有人跟我一樣用2 dimension就過掉了...

於是我想呀想...想到了一個奇怪的點子

這題正常來說, 是Loop完所有state, 最後一次過把r = 0 的states 加起來做答案

而我發現, for 每一個長度 L,  dp(L, ?) 只會在那個iterative有用, 之後不會再用到了

然後 0 那個問題, 其實可以想成是 "要是suffix mod k = 0, 那麼我再append 一個0 的時候不要算進答案內"...有點難解釋, 看看state transition吧

State(L, r) --> append 一個digit 變成 --> State(L+1, x),  

如果 r 不是0, 那麼沒影響, 原本的算法是正確的

如果 r 是0,  那麼就要看看我append了什麼digit了, 要是digit = 0的話就skip掉吧, 其它digit 就沒影響, 原本算法正確

然後每次iterative完, 直接把答案update! 原因下面解釋

但這樣會把 數個連續是0 的suffix少算了 (eg: ???0000)

但是發現到其實也只是少算了 全部是0 這一個case而已

然後iteration到這一步, r = 0的state已經算進答案了, 該state不會再用到了, 我們直接把dp(L, 0) = 1就好了!

所以其實上述的state transition中,  要是 r = 0, 其實只是代表了suffix全部都是0的數字, 其它令到 r = 0而suffix不是0的, 已經算進答案去了

好吧, 我解釋得很複雜, 因為這題真的很複雜, 很難解釋

我只能說我看到有紅字user 也做了類似的東西, 就是在loop中把state 的value改成1

我說這題不是普通dp是因為, state的意味在中途已經變了...話說這樣的題目, 不論做多少題也沒信心即場一棍過啊...

E: (Graph, Shortest-Path)

一題也是很難, 但不是難在算法, 是難在I/O的問題, 如我說的, 相對題D 真的很易了...

題目給定了一個Graph, 圖中有兩類edge, 一類是完好的路, 一類是破路

求由 s 點到 t 點的最短路的最低cost, cost的算法是: 最短路中"破路數目加上最短路以外的完好路數目"

由於題目很好人的已經告訴你, 最優先條件是最短路, 那找最短路是一定的了

這兒說一下, 由於圖不是weighted, 用BFS也很足夠了 但我心血來潮想用這條題目溫故知新一下Dijkstra Algorithm, 於是寫了兩個version, 兩個都AC了

Dijkstra的確是很易寫也很易明的Algorithm, 不明白為何當年我認為SPFA會更易寫, 比彈性來說Dijkstra絕對較好, 時間也沒很慢 (用Priority Queue的話)

然後..我們來想一下cost 的定義有什麼提示, 隨便寫一下就會發現cost 其實只depends on 完好路的數目 (同理, 其實只depends on 破路的數目, Editorial用前者, 我用後者, 只是Maximize / Minimize的分別)

Dijkstra / BFS的其中一個副作用是, 可以同時找到起點到其它點的最短路

那麼很自然想到可以用一個DFS 作Backtracking, 由終點backtrack到起點, 同時數算(所有)最短路中possible最少破路的數目, 這個Backtrack肯定很快, 因為我們DFS的條件是以該點距離起點的距離 (Dijkstra找出來的)作判定, 要是跟現在的點相差一步才Backtrack的, 基本就是一次DFS的時間吧

去到這兒, 也很順利的, 總共寫了一個Dijkstra/ BFS, 一個DFS, 沒想到 (其實是沒看清楚...)

難處在於I/O...!!!
題目不止要求找出最低Cost...也要找出那些路要修好, 那些路要破壞...!

有見給此, 很自然想到, 在Backtrack時順路把最優最短路整條記下好了

(最優最短路就是令我們有最低cost的最短路)

那麼最優最短路的破路要修好, 最優最短路以外的完好路要破壞!!

這樣問題變成一個最基本的圖論問題了: 如何儲起edge最方便!!!

好吧, 不賣自己關子了, 最好的結論是....溫故知新, 要用上最方便最神的儲圖方法

也就是用 array 做成的adjacency list...

老實說, 溫習後再次發現這個圖的儲法真的很方便, 也很高明

它兼備了adjacency list跟edge list的優點...

int from[200005], to[200005], nxt[200005], adj[200005], w[200005], e = 0;

void add_edge(int a, int b, int type){
    from[e] = a; to[e] = b; w[e] = type;
    nxt[e] = adj[a];
    adj[a] = e++;
}

高明在, 要是edge / vertex有什麼特別的property, 只要再開一條array就可以了..

這題也就這樣了, 但我還是WA了一次

原因也在這個圖的表示方法...!
就是....我開Array開太小了...路是有10^5條, 但是由於是雙向, e 的數目會雙倍啊親...

把array開成2*10^5後就AC了...低級低級錯誤...證明我真的很少用這種表示方式解題啊...

也是一道不錯的題目呢 :)

送上我其中一個用Dijkstra寫的Code
http://codeforces.com/contest/507/submission/9813132

Codeforces Round #289 (Div. 2, ACM ICPC Rules)

又是一場百感交集的Round...

相對的學習到的東西好像比較少, 也就是為做而做了...(證明我在公司的確很閑)

難得的是跟ACM ICPC的rules, 就是即場判定, 無hacking, 之類吧

共有6條題目, 當然我也只是做了最多人AC的4題了...(還有一題是水過的=.=)

Codeforces Round #289 (Div. 2, ACM ICPC Rules)

題目在此: http://codeforces.com/contest/509/problems

A: (頹題, DP/Math)

題意: Given 2D matrix, 某一格的value = 上一格+左一格,  求某一格的value

很直接的所謂DP題目, 其實就是學DP時一定會教的基本例子而已....

有見及此, 我很無聊的不打表, 而跑去試著找個有創意的Solution
....

就是上OEIS找找看有沒有這樣的Sequence, 肯定是有的吧...

原來就是 (2n C n)....

所以我就這樣幹了...O(n) , 如果打表的話是O(n^2)

    for(int i=2*n; i>=n+1; i--) a*=i;
    for(int i=1; i<=n;i++) b*=i;
    printf("%I64d\n", a/b);

B: (頹題, Constructive Algorithm, Greedy)

題意: Given 幾條不同長度的List, 需要把每條List的所有位置填色。任意兩條List的任意顏色的數量差距不能大過1 (eg: 不可以List A有3格紅色, List B 只有1格紅色), 求任意一種填色方法 s.t. 使用的顏色數量 <= k

又一題頹題.....我是很想這樣說的

無耐我中伏多次, 卡題很久, 所以不這樣說了...

只能說它是不太用什麼特別的方法, 可是有一些陷阱一個不注意就會被抓了...

基本就是Greedy地填...是這樣說, 實際如何呢?
把第一層填顏色1, 第二層填2, 如此類推?  

錯了

因為頭兩層可以一起用顏色1....那麼特別處理最低層跟次最低層...可以嗎?

Code起上來也很煩...

結果我還是改邪歸正, 看它數據很小, 所以干脆Brute Force, 每次試填某種顏色之前

先看看會否令Configuration violate要求, 如果要的話就把顏色+1, 不然的話就繼續用該顏色, 同時update 每條List 使用該種顏色的總數...

很慢很蠢, 但AC, O(n^2) 甚至 O(n^2 lg n)也可以

C: (Math, Greedy)

我做的4題內最難/煩的一題...也是我水過了的一題...

題意很簡單: Given 一個Sequence B, 求一個Sequence A s.t. a_i 的 sum of digits = b_i
而且A要是increasing sequence!!

Sequence 長度跟值的maximum都是300, 所以自然想到暴力的方向, 所以就暴力起來了...

我的方法也沒什麼好講的...就是每個可能的數 [1,300]

都Greedy地找出它最小的 a_i, 就是除9除9除9...這樣的方法

然後再寫了一個function 可以把某個數加大, 加大完之後的sum of digit也是一樣的, 當然所謂加大就是最低限度地加大...這個function寫到我快哭了, 其實跟人手進位差不多, 不過要考慮得更多...不然會太慢, 最後類似是找到進位的位置, 把位置後面的部分, replace成上述的最小的a_i

for eg,  "18970", 進位變 19???,  而???的總和是16, 所以replace成16的最小a_i "79",  中間還有位的則補零--> "19079"

開頭的做法是更加笨實的, input每一個數, 我就由該個數的最小a_i, 一路加大直至比sequence中上一個數更大才停止...

當然超時了, 說到時間性, 這題的分析有點複雜, 我大約猜是 O(n^3), 但editorial很嚴謹地說出 n ~340, 我就沒深究了..

那麼如何不超時呢? 很簡單, 暴力

只要發現到其實可以分case解決的話就可以不用由最小的a_i 開始試起, 而是直接加大一次就完事, case分為 b_i 比 b_i-1  大 或者 小, 然後內面再分case...共3-4個cases..

我就不詳細寫了..這題我真心認為沒太大價值, 玩玩就好...

趣事是, 我第一次AC的code, 被我一個很簡單的test case駁倒了...(我找其它AC的code試過, 我的code的確是錯的) 我也在Editorial的comment上留了個言 lol
不過那個bug加一句就fix了, 改了後再交也是AC的

不過這題令我了解到, 只要不怕煩, 也不怕醜, 很難看的Code也是可以AC的=.=

自己看那個醜陋的程度吧...我不想再面對了:

http://codeforces.com/contest/509/submission/9779109

E: (Math, String, Combinatorics)

一題似深還淺, 難分淺與深的題目...
題目給了一條公式, 用來計算一條String的漂亮度

hen the simple prettiness of s is defined by the formula:

The prettiness of s equals

當中vowel = "AEIOUY" 其中的characters. String的長度有5*10^5那麼長, 

肯定是O(n)或是O(n lg n)的了...

由於公式的屎忽程度...

那個分母啊...是各自substring的長度啊..不能抽出來算的啊 

怎樣不用兩個loop以上去計... 不知怎的就是會把思路引去partial sum, 的確也是很有幫助的.. 

但不是直接去數"每條substring內有多少vowels"這樣的, 因為這樣是以substring數為主 避不開n^2的 

那麼換個思路, 數每條substring長度為 s 的, 共有多少vowels? 這樣也沒用, s 的確只有n 個變化, 可是還是要一條條substring去數, 次序換了而已=.= 

當這樣的情況, 我也應該要開始習慣下了... 就可以試試逆轉思路, 

我們肯定正確 (只是太慢) 的solution是 "每條substring內有多少vowels" 

把它逆轉就是"每個vowel被多少條substrings包住?"

這就是正解了! 接下來就只是小心的數, 而且當中自然會用得上partial sum的, 看我用久違的小畫家來解說

圖中紅色的是以O(n) scan string時現在的位置, 剛好是vowel 那麼發現, 要包含它在內的長度為4的substring, 最多只有4條...就是如圖中, 它剛好在substring的最右, 一路移位, 直到substring的最左, 總共4條 同理, 長度為i的最多也只有i條,  但注意, 可能不足 i 條 ...
然後, 長度一樣為 s 的substring其實可以一起算, 題目的公式其實是統計了所有的substrings, ?/1 + ?/2 + ?/3 + .... + ?/N,   當中分母代表substring 長度s 先來看看code...(有時看回去, 我也不知我在寫什麼, 為什麼這樣能AC...=.=) OK, 洗個澡後回來想清楚了, 關鍵性的一步就是把 substring 數分開三個部分來算 首先是長度為 i 也有i 條的, 他們加起來就是 1+1+1..+1 也就是for loop內的 第一個部分: mi
然後兩部分可以說是對稱的, 那時在公司不知怎的沒怎麼想就分兩個partial sum去做了.. 第一部分是上圖的藍色箱子(代表substring) 一直向右移, 移到整個比紅色格子右了 也還沒到整條string的盡頭...這樣的一些substring
第二部分是反過來, 一直向右移,  還沒移到最左格跟紅格重疊時, 最右格已經到了整條string的盡頭了...這樣的一些substring
這樣算起來還是很快的, 只用了O(n)的時間, 我要重申兩點...

1. 有時真的不知為什麼我會做到那條題目的
2. 學一個朋友說話: Counting真的是一樣很神奇的工具

#include<bits/stdc++.h>
using namespace std;

char s[500010]; 
int l;
double sum[500010] = {0}, sum2[500010] = {0}, ans = 0;
int main(){
    scanf("%s", s);
    l = strlen(s);
    for(int i=1; i<=l;i++) {sum[i] = sum[i-1] + 1.0/i; sum2[i] = sum2[i-1] + (l-i+1.0)/i;}
    
    for(int i=0; i<l;i++){
        if(s[i] == 'A' || s[i] == 'E' || s[i] == 'O' || s[i] == 'I' || s[i] == 'U' || s[i] == 'Y'){
            //Counting! count each vowel contains in how many substring and add their sum by partial sum directly
            int pre = i+1, post = l-i;
            int mi = min(pre,post);
            ans += mi + mi*(sum[l-mi+1] - sum[mi]) + (sum2[l]-sum2[l-mi+1]);
        }
    }   

    printf("%f\n", ans);
    return 0;   
}

Codeforces Round #285 (Div. 2)

終於開始追上完成了的題目了..
還差說好的Facebook Hacker Cup 2015 還有我又走了數的Rockethon@Codeforces...

話說這場#285, 雖然是Div 2...
可是題目難度不一樣...(是指C開始的題目)

C很快想到算法可惜在實作上碰釘碰死了
D到現在我還是覺得不可能現場即時做到的...除非那個人即時Google 看了Wiki 再秒速理解+實作那個Algorithm...
E的AC人數太可怕了, 我連題目也沒看...

那麼開始吧

Codeforces Round #285 (Div. 2)

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

A: (頹題)

就是代數入公式做一些比較之類的...

B: (String, STL)

String 與Map (背後思路也有DFS的份兒) 的基本應用實作...

C: (Graph, STL)

開始有趣的一題...

Given n (<= 2^16) 個node 的 degree 跟 XOR sum of its neighbors' ID

node的 ID 是由0 到n-1

求符合該條件的圖, print 出該圖的 edges (任意次序)

題目不算很直接的...倒也不算很難

首先 答案的圖不一定connected, 可能有node 是完全沒edge的也不奇怪 (雖然對算法沒影響)

然後很自然地就會注意到題目設定的 2^16 跟XOR sum..

完全指向bit operation嘛...

由於XOR的Associativity ( (A^B)^C = A^(B^C) ), 然後 A^A = 0 即 A^0 = A

所以它是可以"Reverse"的 (可以這樣說嗎..)

(A^B)^B = A^(B^B) = A^0 = A

那麼注意到, 我們已知題目內每一個node 的XOR sum  A1^A2^A3^...^A_n
假設我們肯定了它其中一個neighbor 是A3

那麼我把可以把  XOR sum 去走A3 的部分:

(A1^A2^A3^...^A_n) ^ A3 =  (A1^A2^A4^...^A_n)^(A3^A3) =  A1^A2^A4^...^A_n

如此類推 最後該node的XOR sum只剩一個A_i,  那麼A_i 就是它最後的neighbor

問題是怎樣找出它第一個neighbor呢?? 其實答案已經出來了, 只是要逆轉思維

我們把題目的Input 排好序, 以degree少的優先處理

degree = 0 就跳過吧, 根本沒有neighbor...

degree = 1 才是我們要的!

degree = 1就是說該node 只有一個neighbor, 那麼它的"XOR sum" 不就剛剛是它唯一的neighbor id嗎??

然後我們把它這一個neighbor的XOR sum 除去自己的id (用上面 xor 一次的方法)

同時把它的degree - 1

repeat 直至 所有node 的degree 都少於1就完成了

時間複雜度呢? 由於每個node只會選擇一次, 但是每次處理完一個node都要把update完degree的nodes 重新排序...也不可能每次都sort 一次吧??? 考慮上只剩下每次都自動以 O(lg N) 排好序的方法了.... 有點像Dijkstra Algorithm的影子呢

所以自然! 就是想起heap 這個神奇的data structure, 實作用的就是STL的 priority_queue了吧

老實說, 想到這個做法的時間還是很短的...實作起來才是痛苦的開始

應該是我太久沒用過STL的priority_queue吧, 我發現我是不懂實作customize 的 compare function的...google了一大輪, 無限試驗後, 才有一個像樣點的寫了出來

bool compare(int x, int y){
    return deg[x] > deg[y];
}

priority_queue<int, vector<int>, decltype(&compare)> w(&compare);

當然我印象中是絕對沒那麼複雜的...看了Gary神與Peter神的實作也沒那麼複雜, 這題真的感受到除了思路之外, coding的技巧還是太嫩了=.=

來學習神人Gary的寫法:

struct node{
 int id,deg,s;

 node(){}
 node(int id,int deg,int s):id(id),deg(deg),s(s){}

 bool operator<(const node &d)const{
  return deg > d.deg;
 }
} ss[100000];

priority_queue<node> q;

人家輕鬆寫個struct再override operator就行了, 寫反了的原因是STL priority_queue好像default是Max. Heap來的, 所以要人手把degree少的當成較高priority讓它們排在前

還有一件事也是煩了我很久的....可能我中了幻術, 

我總以為這個priority_queue是online auto sort的...也就是說每次裡面的element有update也會自動再sort一次...當然這是不可能的, 太理想了...

所以要完成上面的算法, 實際上是每次update degree後, 看看degree變成1了沒有, 

如果沒有就別管了, 完全不處理, 反正最後一定會有它的一個neighbor把它的degree降成1 的時候, 而那時候我們再push 一個新的degree 為1的node進去priority_queue (O(lg N)的時間)

就好了, 這樣說的話,實際上每個node就不止access一次了, 更可能是2次 (第1次發現degree還沒變成1, 可是又已經到了heap的頂了, 直接拿走; 直到我們再push它進heap底, 這時它必定是degree 1了)

總的來說還是O(N*lg(N))

D: (Math, Binary Indexed Tree)

我就直說了吧, 這題根本不可能做到的...要不是我即場做的時候有點眉目, 不甘心下跑去看Editorial, 根本不會發現這題所需要用的冷知識...

當然還是很感謝它的, 令我又再跑去學了Binary Indexed Tree (BIT)一次...

先來說說題目吧, 題目是很簡單易明的

Given length N 的permutation 兩個 p,q.

然後每個permutation 都有各自的Order, 代表它們lexicographical 的排名, 由0到N!-1

定義permutation的sum為  (Order(p) + Order(q))%N! 

找出排名為 sum 的permutation

這題的變態位在於 N <= 200,000    (O:*2036

先不說別的, 只是要執行 mod N! 這一步已經不知怎做了...

第一次做的時候我還是沒放棄的, 我姑且去解Order()這個function

這個還是勉強靠一些combinatorics 可以count出來的~

設p = (3,4,2,1,5)
我數的是有多少個permutation比它少對吧?
那麼第一個數字比3少的肯定要數了...(1,?,?,?,?) 跟 (2,?,?,?,?), 各自都是 4! 個可能性

然後即使第一個數是3, 也有可能第2個數比4少的, 注意比4少的卻不能是3, 因為3已經在第1個位, 那麼有(3,1,?,?,?) 跟(3,2,?,?,?) 各自都是3!可能性...

注意到了嗎??  其實比一個permutation少的permutations數目, 就是Editorial說的

    (應該是(k-1)! 才對?)

當中 d_k 是比第k 個數字少,而且還沒出現的數字的可能性, 換句話說,

是比第k個數字少, 又在第k個數字右面的數字 數目

然後乘上 (k-1)!  

我找了些N很少的permutation來算, 也是對的...算是可以開心吧

問題是...這個方法去找Order, 也是避免不了要算 N!  , 你媽啊...

我也有想過會不會 mod N! 有些我不懂的方法是不用直接算出N!的...

可是連Order()這個function也已經要用上N!了啊...

Peter神的指引下, 還是跑去看Editorial了...一看之下可真是嚇呆了

Factorial Number System

這個奇特的Number System竟然存在的啊...而且它跟permutation還有一種奇妙的關係...

而這條題目就是要利用那個關係啊啊啊啊啊啊.......

誰會懂這個非主流的東西啊....

好吧...我只能說這個Number System 我也沒看完, 但由於也是一個Number System,

還不算難理解的

正常的Number System, 例如十進制跟二進制

每個位數也是 10的次方, 或者2的次方,    第 i 個位 (0 <= i) 就是 coefficient 乘以 10^i  或者2^i
其它進制也是這樣

而Factorial Number System則把"次方" 改為 Factorial...

就是 第 i 個位 是coefficient 乘以 i ! .....  

然後談進位的問題,  十進制每個位置不能大於9,   二進制不能大於1...

又Factorial 進制則是 每個位置都不同,  第 i 個位不能大於 i 

舉個合法的例子  341010_!  = 3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0! = 463₁₀

十進制轉換Factorial進制就跟轉二進制差不多, 也是通過連續的除法取其餘數

詳情wiki 很清楚

好了, 要完成題目, 必需要用到的是Permutation那一節, 原來這個Number System跟Permutation有個神奇的關係, 就是它可以直接找出lexicographical = 該number 的permutation!

看例子最實際了: 4041000_! (equal to 2982₁₀) 

(0,1,2,3,4,5,6) 的第 2982 個 permutation 是什麼呢? 

Factorial 進制的每一個數字, 都代表 (0,1,2,3,4,5,6) 剩下未用的數字位置!
例如4, 就是第4 個數字 4,  然後我們把4 踢走:  (0,1,2,3,5,6),  答案: (4,?,?,?,?,?,?)
再來是0, 就是第0個數字0, 加入答案, 然後踢走: (1,2,3,5,6) 答案: (4,0,?,?,?,?,?)

再來是4, 就是第4個數字6, 加入答案, 然後踢走: (1,2,3,5) 答案: (4,0,6,?,?,?,?)

如此類推....

竟然可以這樣真直接找出來了....!

那麼是咁的, 把這個轉換逆轉,  就可以把一個 permutation 直接轉成 Order了 !(以Factorial Number的形式)

事實上, 不論由Permutation 換成Factorial Number還是掉轉,  也是要用到BIT的...詳情再說

假設我們成功獲得了Input p跟q的 Order了, 就是有兩個Factorial的數字了

如何算出它們的Sum???
加法是沒問題的...我要再強調, 它也算是一個Number System, 照樣理解的話, 

就可以linear地手動進位去算加法了

問題是 modular N! ....

首先要發現, 兩個數加起來, 肯定不會超過2N! , 就如十進制的 9+9 也不會比20大吧..

對了...十進制的十, 就等於 Factorial 進制的N!, 這樣理解很好

所以modular N! 跟減N! 在這裡是一樣的..

然後! 事實上由於N! 不可能以 N 個位數表示的, 想一想就知道了, 剛好要進位的嘛!!

所以N! 根本就一定是  10000....000 的形式存在啊! (跟二進制的 2^x 一樣, 10,100,1000000...)

所以....modular N!  = 減N! = 其實就是兩個Order加起來 ignore 第N 個位就好了....

這是何其聰明的做法啊...

最後把這個SUM 再換成permutation就好了...

太淫賤了, 正常人根本不可能懂的嘛...

我們最後來看一下最重要的部分: 

1. Permutation --> Order (Factorial Ssytem)
2. Order (Factorial Ssytem) --> Permutation

首先要先溫習一下BIT....

以我最新的理解...BIT跟Segment Tree最大不同之處, 是簡單易code

同時也很多限制, 好像只能作一些 accumulative sum的工作 (借此可以達成 range add x 的效果)

例如Permutation 換成Order, 其實我們每看一個數字時, 我們要知道比它少的數字已經出現了多少次 (踢走了多少個)
用同一個例子 (4,0,6,2,1,3,5):
看4時,  我們把BIT[4..N] 都加上 -1, 看0時也把 BIT[0..N]加上-1

看6時, 我們其實Query了 BIT[6], 發現是-2了, 所以我們實際儲存6-2 = 4, 當然也要BIT[6..N] 加上-1  如此類推

int sum(int x){
    int ret = 0;
    for(x;x; x-=x&-x) ret += bit[x]; // 找出[0, X] 的accumulative sum
    return ret;
}

void update(int v, int x){
    for(x;x<=n; x+= x&-x) bit[x] += v; // 把包含 x 在內的樹加上v
}

void toFac(int *arr){
    memset(bit,0,sizeof(bit));
    for(int i=1; i<=n;i++){
        int tmp = arr[i]  + sum(arr[i]+1);  // eg: 位置6 加上 [0,6]的accumulative sum(-2)  = 4
        update(-1, arr[i]+1);  // 不忘update, 把現今位置及包含現今位置的樹加上-1
        arr[i] = tmp;
    }
}

最後了, 把Order 算出Permutation來

這個反而有點tricky, 是要用上Binary Search 加BIT的

思路是找出第一個 位置+BIT[]  = Search Value 的位置

要強調第一個是因為可能有多個出現, 例如

( 0, 1,  2, 3,  4, 5, 6)

(-1,-1,-1,-2,-2,-2,-2)

如果我們要找 "1"的話 (現今Factorial Number的數字)

(2-1) 跟(3-2)都是 1, 我們要取2還是3?
答案是肯定取最前的,  因為後面那個(那些) 會減至跟前面一樣只有一個可能性: 它們已經先被取掉了, 然後update了, 所以才會減那麼多次變成跟前面那些一樣

但由於它們不論怎樣減, 也不會被前面位置+BIT少, 就是說  (位置+BIT) 是長期處於Sorted狀態

所以才能用Binary Search
老實說, 在看了wiki之後, 獲得算法之後, 這部分算是最難搞的 (腦內清楚卻很難表達...)

這題的感受是...什麼Factorial Number System, 不打算詳細記下...倒是BIT的用法跟實作

可能要找個時間做一下啊...可能是個很強大又性價比高的武器

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的數法

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

Bipartite Matching Basic & UVA10418 大冒險

說好的Bipartite Matching...難得學了一些基本又做了一些基本題目
當然要留個名...

話說所有理論/證明/寫法都是參考演算法筆記的, 這個神網真的幫了我很多
以下全部都是向未來的我的自白:

 To 未來的我:

基本要說的都可以在裡面找到了...這裡只留下一些讓"你"更易回憶/理解的思路...

首先 Bipartite Matching與General Matching的關係很深, 基本上General Matching
的算法 (雖然還未看)都是以Bipartite Matching的算法加以變通, 明了一就應該明了全部...

然後所有Matching的題目好像都可以用Flow相關的算法來解 (不肯定)...
可恨我也不會Flow..慢慢再學起吧...=.=

再來Matching的算法複雜度基本還是很高的...題目要求如果不太大 (~10^2 - 10^3?)
特徵相附的話, 很可能可以用Matching過的

Bipartite Matching的算法實作起來100%是DFS (相信General Matching也是)
不難寫, 但背後概念要很清楚...
另有一版本是BFS取代DFS, 複雜度更低但好像有點難寫....

Matching 問題以我暫時理解可以有3種: Max/Min Cardinality, Max/Min Weight, Perfect Matching
沒有Weight的情況下, Max Cardinality = Perfect, 有Weight的考慮則很多變化, 也不是這篇的主題 (其實是還不懂=.=)

所以這篇就是學基本中的基本: 沒有Weight的 Max. Cardinality Bipartite Matching
雖然是所有Matching中最簡單的, 出奇地很多題目都用得上, 攻利地說算是性價比高吧...

OKOK, 有點長氣...入正題吧..

理論 / 算法

Bipartite Matching基於一個理論: Augmenting Path Theorem (Berge's Theorem)

證明很勉強地理解了, 但不會記下的..."你"有興趣自己回演算法筆記看吧...

首先定義Augmenting Path (跟Flow 那個Augmenting Path不知有沒有關係?)

是一條兩個end points都是未匹配點的梅花間竹path

這類path的特性是: 把path上的邊逆轉, 匹配的變成非匹配 (and vice versa) 則總Matching Cardinality會+1

然後 Augmenting Path Theorem證明的是: 圖上任意一個不能作Augmenting Path起點的未匹配點, 把它移除, 剩下的圖仍能找到原圖其中一個Maximum Matching

這直接導出最簡單, 基本的Bipartite Matching算法: Augmenting Path Algorithm

設G={X,Y}  X跟Y是二分的兩組vertex,  隨便選X或Y都可以, 把它們全都當作未匹配點

然後一個個試著找Augmenting Path, 找到的話Cardinality就加1了, 同時該點會變成匹配點

如果找不到的話, By Augmenting Path Theorem, 我們移除它 (或者直接不管它)就好了

每個點要不變成匹配點, 要不直接不管, 都是Access一次而已
而當中找Augmenting Path的部分則是用一次DFS (或者用BFS, 如上面所說)

這個很重要, 直接簡單地分析了複雜度:  V次DFS的複雜度

DFS又視乎圖用什麼結構,  Matrix的話是O(V^2),  List的話是O(V+E) = O(E)

所以整個Augmenting Path Algorithm 是 O(V^3) 或者 O(VE)

基本題目

先來看幾說基本題目, 各自都有得益

UVA259, UVA10092

題目很直接的就會讓你聯想到Matching

然後這道題也有很多Bipartite Matching的特性...

就是建圖的麻煩!  很多時要自己想個簡易的方法給vertex一些id

才能用Augmenting Path Algorithm去解!

例如這道題, 題中的一些貌似vertex的東西可以重覆使用數次, 例如4次

建圖時真的要把它們當時4個分別不同id的vertex!

當初我做的時候, 我自作聰明, 沒用分開4個不同的node, 我用同一個node
讓他找4次Augmenting Path, 其實我到現在還是認為可行的...

test case好像也過的了, 不知怎的就給我WA

結果還是要乖乖把它們分開幾個不同的node才行...這個要記住

UVA10080

也很直接的一題, 就是建圖時計一下距離吧...

UVA10243

哇哇哇, 這題真的可以重點講一下

來頭不小的...可是某年ACM World Final.....的試機題目 (o:

但已經獲益良多了...

如果要說直接題意的話, 其實是求Tree 的Minimum Vertex Cover

老實說 我開頭是完全不明白關Bipartite Matching什麼事...

然後開始發現Tree一定是Bipartite Graph嘛....(所以也可以2-color的)

但...Vertex Cover跟Max. Matching有關係嗎?

用筆畫了畫, 不知怎的好像剛好答案都一樣, 就交了

竟然AC了....

百思不得其解之下, 跑去問Google了, TMD 竟然還真的有這樣的一條Theorem
König's theorem

"...an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs..."

FUCK...我記住了...

話說General Graph的 minimum vertex cover好像也跟maximum matching一樣的說...?

UVA10418 大冒險

這條真的另開一篇說都不過份...

我為了這題流了多少血汗....

現實來說, 這題是WA的, 但我不知羞恥地認為是UVA Judge的問題

在我看來應該是AC的了...

這篇來看為什麼我這樣認為...

先說一說題目, 題目的變態程度很不一般

因為是劉汝佳"白書"中的題目 (好似係)

題目的running time是30秒 =.=

明顯是告訴你 "量你也做不到"...

題意是這樣的:

Given 一個 m*n的棋盤, 棋盤上有 2*k + 1 隻棋子

k 隻是紅色的, k隻是綠色的,  1隻是金色的

它們初始狀態是放在某些格子上, 同一格可以放多於一隻棋子 (放全部也可以)

然後再選定 t 個格子, 每個格子有一個值叫 r
代表該格子內最後要放 r 隻棋子

所以 t 個格子的 r 總和一定是 2*k + 1

再來是棋盤每一格都有不同高度,  

紅色棋子只能平走或向上爬; 綠色棋子只能平走或向下爬; 金色則無限制地移動

每一步可以選任意一隻棋子向上,下,左,或右走一步 (不能出棋盤外)

由於這樣的限制下, 可能無solution, 所以玩家可以使用一種魔法

把棋上所有棋子換成任意一種permutation, 即把它們任意互換位置

好了, 問題是問, 要達成目標, 最少需要用多少次魔法呢?

只是要理解題目就已經有種吃屎的感覺了對吧?

好吧, 我要高興的是在進一步調查之前, 我的思路基本是正確的...

是要Binary Search + Bipartite Matching的了

先來說說思路跟解法

首先大約的想法是...如何建圖!

這個Bipartite的兩Group很明顯是棋子與 t 個格子了..

而由於有法術跟金色棋子, 基本上每隻棋子都可以去任何一個格子的, 差別在於用多少次魔法

那麼有沒有可能分別找每粒棋子到每個格子的 最少魔法使用數呢?

正確性又如何?

答案是可以的!

正確性建基於一個Observation: 使用魔法的時機, 是在於所有棋子都沒路走的時候!

所有棋子(不包括金色)都沒路走, 其實代表紅色不能再爬上, 綠色也不能再爬下...

解決方法有一個, 而且肯定是最好的, 因為只使用 1次魔法! 把紅綠互換! (各自都是k隻!)

互換後, 所有沒路的變成所有都有路了!

發現這點後, 再來看看建圖的部分, 可以用BFS類似找最短路徑的方法, 找出每隻棋子到每個目標格子的"最少魔法使用數" 這個數字再進一步當成 Bipartite Graph 的 edge weight!

給個例子吧,  假設棋子A 最少用3次魔法可以到目標, 棋子B則要用4次

Physical Meaning是這樣的: 棋子A跟B 各自走這條"最好路徑" (好 = 用最少魔法次數的路徑)

直到沒路, 使用1次魔法; 然後再走下去...重覆3次,  這時A已經到目標了, 而B 還需要多一次魔法

就是說 它們的頭3次是"重疊"的, 可以用3次魔法同時解決它們的困境

說到這兒, 又開始理解Augmenting Path Algorithm的實作時, 自然會想到

用Binary Search去估算 魔法的次數, 每次估算就用一次Augmenting Path Algorithm!

只是找Augmenting Path的時候, 如果edge weight 大於正在估算的數值則要ignore

(就是當沒有這條edge的意思), 這樣確保所有Augmenting Path都能以少於等於

估算數值的魔法次數達成

然後又會發現, 怎麼沒考慮金色棋子?  其實這時再考慮也不遲

以上分析在沒有金色棋子的情況下是絕對成立的, 那金色棋子改變了什麼呢?

最直接想到的是, 金色棋子可以以1次魔法 直接把任意1隻棋子送到任意目標!
實際上, 就是金色先到任意目標, 跟任意棋子互換, 金色自己再次走到任意目標即可

那麼情況產生變化了, 這樣首先發現, 最多只需要2*k 次魔法就可以了, Binary Search的上限!

然後在Binary Search中的Maximum Matching, 假設Cardinality不是2*k+1

就是有某些棋子不能以估算數值內的次數移動到目標了...

那麼自然就可以試試用金色幫助它們吧?
可以想成是: 金色原本去所有目標的weight都是0 , 如果幫助了1隻棋子, 則全部變成1..如此類推

最高可以去到估數算值

所以,  如果 2*k + 1 - #max matching <= 估算數值x  

仍然可以說是成功!  因為剩下的棋子可以全部以金色棋子幫助它們!

呼! 終於做完了!!! Test Case都過了!  為什麼都是WA!

一直WA!!

嗚啊...難得一條非水題....

我心有不甘, 於是上演了我自導自演的偵探日記

首先, 當然是Google了...

出奇的是, 由於這題是變態Asian出的題目, 網上resources非常非常的少

我最先找到的是知名的UVA 解說網站 Algorithmist

它的solution跟我的基本就是一樣, 而且它的test case我都過了...信心大增, 再交

還是WA

UVA Official Forum竟然也沒人問這條...

很絕望, 這時我找到這個Github 上面有一堆UVA題目的solution啊!!

當中也有UVA10418的, 高興死我了

我可以random generate一些input跟它的對比一下再debug了

我也真的這樣做了...結果都一樣, 應該沒問題的啊..!?

難道...難道是它的code也是WA的嗎?  我就這樣把Github上的code 直貼上judge

果然WA了...

這不正常啊...那個Github用家不太像這樣腦殘吧? 把WA的Code放上來陰人嗎?

於是我隨機選了其它數條問題的solution再放上judge, 全都AC了!

這更加奇怪了...這時我跑去UVA Official Forum 開了一個thread虛心求問

果然還是吃白果了

然後我還厚面皮的去StackOverflow問了

果然還是吃白果了, 還不知那個路人給了我一個負皮了 (本來還1-2個正皮的=.=)

然後我還試住找了一下劉汝佳的email 發了一個email給他 (o:

果然還是吃白果了

很絕望的情況下, 我又跑回去Github...

這時我在想, 有沒有機會找到這個Github的作者資料? 

於是我Google這個用家 Bruce3557

發現他在UVA的帳號叫"Monkey D. Luffy"!
而他的確曾經AC了這道UVA10418的!

事情更加奇怪了 我也無從入手了...

這時發現這傢伙在Codeforce上也有帳號啊...叫"bruce3557"

雖然2年沒上線了..我還是試住給他發了一個message

然後竟然今天他給我回覆了!!

我當然打了一大段文字感謝神, 還有請他幫忙verify一下他的code是否亦能AC?
但他沒再回覆了...

話說我也叫Peter神幫忙試了一下, 他也WA了..

然後Peter神給了我一個網站看UVA的Submit Status

發現很久都沒人AC了, 而最近試交這題的除了我跟Peter神

還有一個叫 BrianFry 的神人 (AC了4200多條問題) 也WA了

這個人我認得是UVA Official Forum的常客, 經常回報Bug或是什麼的

可能他看到我在UVA Official Forum 的另一個post吧...

總之事情的發展就是這樣了...我當自己AC了不過份吧? 當它的Judge錯了也不過份吧?
最低限度是太不負責任了吧...說一句"我們試過了, 完全沒問題啊柒頭" 我也會高興點的

再等等看事情的發展吧....(最主要是看Bruce本人在CF怎樣覆我了...)

Codeforces Round #284 (Div. 2)

雖然#281 - #283都有做...
但看了一下好像很麻煩, 所以還是直接跳過
反正最想寫的還是這場 #284
因為它令我跑去學新東西了
話說這場只做了4題, 雖然其中也包括了Problem E啦...

Codeforces Round #280 (Div. 2)

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

A: (頹題)

頹題...只要沒看錯題目就是考你寫for loop而已=.=

B: (頹題)

也沒什麼算法可言的...就直接做吧, 一題關於STRING PROCESS的頹題

C: (Math)

這題開始有趣了,  簡化一下題意吧

Given n 條線, 它們把空間劃成很多不同region. 然後問你由point A 到point B, 最少要經過多少個region 

應該說, 只要把題目理解成上面的意思, 就變成很單純的數學題了...
由於題目所有point都以(x,y) 輸入,  感覺也不太需要變成vector 來做了

首先發現, 把AB 連成一條直線肯定是經過最少region的其中一個方法 (用Greedy的想法就知道不可能比它更好了) 

然後問題變成, 有多少條線橫跨AB之間?

利用一下簡單的數學特性:  把A點跟B點各自代入 n 條線之內

如果一個是正數一個是負數, 就代表他們被隔開了...

(不會等於0...因為題目說明A跟B都不在任何一條線上)

所以就是O(N) 算一下究竟A跟B是否處在第 i 條線的兩邊

話說實作時, 不能以一句 

  if((sx*a+sy*b+c)*(gx*a+gy*b+c) < 0) ans++;

來算答案...因為.....兩個數相乘會比long long更大...我的兩個WA啊...

D: (???)

沒看題目...而且就AC人數來說, 也沒什麼心情看...

E: (Math, Bipartite Matching)

重點來了! 正正是因為這一題, 我跑去學以前都沒心情學的matching了=.=

發現如果是bipartite graph的matching還是很好理解, 很好code的...

因此還繞了個道跑去做數題bipartite matching的題目....下一篇再詳談吧...

要說這題的話, 絕對不是馬後炮, 一開頭想的算法就已經是答案了...

無奈發現算法中要用到bipartite matching, 所以就跑去學了..

題意大約是這樣的:
有 n 個正整數 n, 再有 m pair 數字(mx ,my), 你可以把位於第mx 個的數字和位於第my 個的數字除任何一個大於1的數字 (要能整除),  同一pair 位置的數字可以選擇多次, 問最多可以執行多少次相除?  Given mx + my 一定是單數, n, m <= 100

是咁的, 由於mx + my 一定是單數, 所以可以選擇的位置一定是 單數跟雙數, 

自然把單數位置的數字跟雙數位置的 分開兩組...

然後由於是問最多可以相除多少次....自然會想到不論選擇那一pair 都會選擇除最小的公因數

最來就是如果一個數字同時可以跟另外數個數字相除,  那不論選擇那一pair 都沒所謂...

反正他也就只有限定數量的"因數" 而已...因數A 跟那一個數字的因數A相除都沒關係, 反正相除數都是加一, 又不影響以後的結果 (1999 MODE)

想到這兒, 不難想像Prime Factorization了吧...?
每個數字都有unique的prime factorization, 那麼把100個數字, 每個數字各自化為自身prime factorization 所有質因數的一堆vertex可行嗎? 

每一個數字 a <= 10^9,  最小的質因數可以是2, 那a 最多可以有 lg (a) 個質因數吧, 大約30個

所以也就共3000個vertex...

算法就出來了, 單數位置一組, 雙數位置一組, 有共同質因數的就連線, 組成一個bipartite graph

找這graph的maximum matching cardinality 就是答案了

好吧, 分兩步來說, 其實主要圖論的題目, 最煩人的都是建圖的部分...

後者的部分基本都是直plug 相關算法而已...

這題的建圖部分, 重點就是prime factorization, 我印象中不懂很快的算法

還是先找所有需要用到的質數吧...我這次用的是新學的改良後的質數篩法

很聰明的一邊打表, 一邊篩, 實際每個合成數只會access一次, 達至O(N)

感覺要一段時間才能理解並記下, 所以先留一個名

實際只要找 sqrt(10^9)內的質數, 就可以做到 10^9 的prime factorization了...

void make(){
    memset(f,false,sizeof(f));
    f[0] = f[1] = true;
    ps = p;

    for(int i=2; i*i < N; i++){
        if(!f[i]){*ps = i; ps++;}
        for(int j=0; i*p[j] < 31630; j++){
            f[i*p[j]] = true;
            if(i % p[j] == 0) break;
        }
    }
}

void fac(int in, int x){
    for(short *pi = p; pi < ps && x > 1; pi++){
        while(x % *pi == 0){
            x /= *pi;
            group[in].push_back(*pi);
        }
    }
    if(x > 1) group[in].push_back(x);
}

然後就是直接用bipartite graph的算法了...

我是用最簡單的augmenting path algorithm, 用adjancency list的話是O(VE)
這個分析有點難...editorial的分析也有人提出了...其實應該也是超時的...不知怎的還是過了..

關於augmenting path 或bipartite matching的算法以及題目, 下篇再說吧...

總之這題做到是很開心吧....學到東西又不算太易...至少對我來說不算很易=.=