由M$主辦 確實條件很簡單 只要在能advance到Round 2就有T-Shirt了
這個比賽的流程是 Q-Round-->Round 1A / B (各500名advance)--> Round 2 --> Final
先來說結果吧 我Round 1A 不打算玩的, 所以遲了一小時多開始玩, 結果AC了 3題中最多分的一題, 但因為太遲玩 + 錯了一個白痴錯誤, 只有504名
今天全力玩Round 1B, 狀態卻奇差, 也進級失敗, Round 1止步了
然後是一些我對這個比賽 / 平台的comment
每場比賽跟GCJ一樣只有3題, 題目也有趣的
但我還是很不滿
首先, 這個平台沒有練習模式, 賽後想再submit試試看也沒有機會
也沒有Solution 跟Editorial, 有幾題真的我認為pattern很常見卻不會做的題目
我真心很想知道思路啊...
就結果來說, Qround我就不特別寫了...沒什麼好寫的, 打得也不特別好
A跟B應該都會做的, B-Large自己白痴交了個TLE的solution, 之後其實改好了
但正如我所說的賽後根本不能submit試試看能不能過...唉
C是完全沒想法, 開頭以為是那個簡單的分開 x 跟y axis來算optimal value的技巧
卻完全不是, 問了GG 也說有點難做就不了了之, 這是一題我很想知道思路的題目
來到沒認真打的Round 1A, 遺憾是有的, 要是認真打的話應該advance = 有T-Shirt了..
Round 1A的3題:
A 我真心認為是語癌, 它的sub-tree跟我認識的好像完全不同意思, 題目也沒特別說明它的sub-tree是不是common說的sub-tree..總之是語癌題, 果斷跳過
感過要不是語癌的話, 應該是中等易一點的dp on tree...
B 我認為是最難的一題...也是另一題我很想知道思路的題目
給了 n (< 1000) 個直角等邊三角形, 斜邊都在x-axis上面, 三角形可以overlap
你可以決定要build那一些三角形
build一個三角形的收入 = w_i - 它的area
要是某部分有overlap的話, 那部分只需要算上一次就ok
問最大可能的收入是多少
感覺很像knapsack類的dp, 但overlap area 背後的trick 完全沒想通
總之就沒多少想法就是了...真的很難
C 是我唯一過了的一題...竟然small + large有45分, 根本沒多難的...
但這題是唯一我想記下的, 因為還是很有成功感的說
MSBOP 2015 Qualification Round
(2015-05-03) 先更正下對這個平台的看法, 過了數日後終於能夠賽後Submit了
結果還算是合格的平台吧...
至於比賽的Editorial 還是沒出...看來這堆題目要成為遺憾了
之前 (上面) 所講的 Qround B-Large 雖然是白痴開錯了array size
但即使不開錯也不算是太易過的,,,終歸還是在運氣+摸魚的情況下過了...
至於C-Large, 還是沒想法, GG也沒更進, 果斷把它從腦中丟掉比較好
A: (Ad-hoc)
找潤年的基本題目...就按住題目給的定義判定下就好了...
B: (DP)
Q-Round來說重點是這題吧...找Peter神試了一下, 他也認為不算是容易的,,.
所以就記一下吧
DP來說我認為也是有趣的一題...思路可以學習一下 (原來可以這樣DP的啊)
題目是這樣的 (以Large來說), 給了string S 一條 (|S| <= 1000)
題目是這樣的 (以Large來說), 給了string S 一條 (|S| <= 1000)
問有多少Subsequence 是palindromes...
注意是subsequence 不是substring, 所以也不算太直接
由數據來說, 應該是O(n^2)的DP
(好像做過palindrome相關的題目不是DP就是Greedy?)
(好像做過palindrome相關的題目不是DP就是Greedy?)
問題是怎樣dp 才能不超時...
由於O(n^2), 又是palindrome
狀態應該是近於 DP(x,y), x跟y 是S 內的range這樣...
我是用Top-down的做法的 (bottom up不太會code那個順序...這些事其實也不用強求)
Top-down內不能有for loop吧, 不然就不是O(n^2)了...
然後在紙上畫兩畫, 發現了一個有趣的Observation:
首先設DP(x,y) 為position x 到 y (inclusive)之間所有palindrome subsequences的總數
然後大約是 S[x] 跟S[y]慢慢拆走再看DP(x+1, y-1) 是常識吧....
那麼會出現S[x] == S[y] 或 S[x] != S[y]兩個情況
先看 S[x] != S[y]的情況
由上圖能發現,
DP(x,y) = A+B+C-2C, 要 -2C 是因為 A+B的子狀態時會重覆算了C的子狀態2次...
所以 DP(x,y) = A+B-C = DP(x+1, y) + DP(x, y-1) - DP(x+1, y-1)
再看 S[x] == S[y]的情況
首先, 要explicitly 加上 1, 因為S[x]S[y] 自己已經是一個palindrome, 而這個palindrome不能由任何子狀態 (A,B OR C) 算出, 所以要自己把答案 + 1
然後就跟上面差不多了
DP(x,y) = A+B+C-2C+C, 要 -2C 是同樣原因, 要+C 是因為 C跟 S[x]CS[y] 是兩個狀態分別數了兩個 disjoint set of palindrome subsequences, 兩個disjoint set 的size 跟都是 C 那個狀態的Size...
所以 DP(x,y) = 1+A+B+C-2C+C = 1+A+B = 1 + DP(x+1,y) + DP(x,y-1)
就是這樣了...combine 兩個case 一下可以很簡單一行code就完成
至於時間複雜度嘛...Recursion的complexity我從來都不太懂算
但由於沒有for loop, 而每個狀態都會把 [x,y] 的range縮少至少 1
x跟y 只有O(1000) 也就是最多只會有O(n^2)個狀態, 每個狀態算一次這樣 (with memorization)
MSBOP 2015 Round 1A
C: (Math, Bipartite Matching)
這題簡單來說, 是Math + Maximum Bipartite Matching有成功感的原因是, 除了它高分以外, 是以為不多久前學的Maximum Bipartite Matching
終於派上用場了, 果然如我當時所說的, 性價比真的很高
而且思路也是從當時某一題題目引申出來的, 再從這一題學到了另一個 fact
(詳情請自己找回之前Bipartite Matching那篇文)
我直接以large的數據來說一下
題目給了 n (< 1000) 個數字, 2個數字 a, b (a<b) 叫prime dependent iff a*p = b for some prime p
問這n 個數字 最大的subset where subset內任何2個數字都是prime independent的subset size
這些數字 < 500,000
直覺認為跟prime factorization脫不了關係, 打質數表也是必需的, 500,000內的質數還是很少的(5000個左右)
然後就在紙上畫了畫 把sample case都畫了一下
畫的方法是把 n 個數字內 prime dependent 的都連上一條線, 這樣就得出一個graph
然後不難發現, 答案就是這個graph的 Maximum Independent Set!
這個問題我也知道是NP-Complete的, 而在題目中有NP-Complete的情況只有幾種:
要不是 n 很小, 可以用某些dp 暴試之,
便是這個NP-Complete的題目在某些條件下不是NP-Complete的, 例如General Graph下的問題在Bipartite Graph下通常都很易解的
這也是一樣! 這樣就引至我逆轉去懷疑, 題目給出的這些Graph其實是不是 Bipartite Graph呢?
這個要prove也不算難, 基本上證明graph中沒有"三角形"就好了...
Case 1: 假設 a, b < c, 然後 a跟c 有edge, b跟c也有edge, 證明 a跟b之間不能有edge
--> Given a*p1 = b*p2 = c
assume a跟b 有edge , then a*p3 = b
--> a*p1 = a*p3*p2 = c
--> p1 = p3*p2
--> contradiction as p1 is not prime now!
Case 2: 假設 a < b,c, 然後 a跟b 有edge, a跟c也有edge, 證明 b跟c之間不能有edge
--> Given a*p1 = b, a*p2 = c
assume b 跟c 有edge, then b*p3 = c
--> a*p1 = b, a*p2 = b*p3
--> a*p1 = a*p2/p3
--> p1 = p2/p3
--> contradiction as p2 is not prime now!
--> 這個Graph 是bipartite的!!
好了, 接下來, 我記憶中 Bipartite Graph中的independent set 好似有解的
...好吧, google了一大輪, 原來我記錯了
其實...Bipartite Graph 的Minimum Vertex Cover 才是有解
Min Vertex Cover = Max Bipartite Matching
然後...經由推理 (這個其實已經足夠肯定)
再加上google wiki, 就肯定了以後事實:
For Any Graph
Max Independent Set = # of vertex - Min Vertex Cover
在Bipartite Graph的情況下,
Max Independent Set = # of vertex - Max Bipartite Matching
這就出現算法了!
先打質數表
再用 O(n^2) 建圖
然後在圖上找Max Bipartite Matching...
咦?
Maximum Bipartite Matching 可是要 O(V^3) 或者O(VE)啊...
前者是用matrix來儲圖, 這個題目一定不行了
只有O(VE)可行... (用adj, list來儲圖)
但...這不是等於要 E = O(V)嗎?
這下又要證明一下了...(其實真正比賽時可以直接去了...感覺根本就是正確做法, 不用懷疑)
這個證明比賽時沒很全做完...事後再試試嚴謹一點的
我想證明這個Bipartite Graph不能有cycle ( i.e. even cycle)
也是用contradiction來證明:
證cycle存在, cycle中最小的數字叫a, 最大的叫z
則
a*p1*p2*...p_n = z (一直按最長的path由a走到z)
同時
a*p_x = z (a跟z 直接連起來的edge)
則p1*p2*...p_n = p_x
-->contradiction as p_x not prime!
由於不能有cycle, 所以最多只能有 V-1條Edge了
QED!
Code起, AC了
遺憾的是Code仍是要出cheat的...concept是記得, code卻沒有上手呢...
結語: 這題真的會比題B難嗎...
結語2: 今天認真玩的Round 1B比1A更加強差人意, 就不特別記下了...倒是很想有賽後submit作practise用的機制呢...還有solution啊....M$ Why you suck so much
結語3: 有開始在看KMP / String相關的算法了, 我沒有忘記要寫一篇String Searching的詳細文, 這才是原本的步調...但看來要在Code Jam Round 1B後再說了...希望1B別比1A難吧..
