很久之前看到CF推出的Education Round 系列已經感到興趣, 決定玩下 Round 1
看名字覺得是for 新手學習用, 所以很想玩, 但竟然...此Round 無Editorial...
究竟無Editorial 點樣可以Educate到人呢 ?
Anyway 這場有A-F共6題, 難度我覺得也是D2至D1尾吧? 最後AC了5題, 最後一題有點想法但Code不出來
要說學習了什麼, 倒不如說溫故知新, 特別是問了Peter神及GG 一些埋藏多年的白痴問題
Codeforces Education Round 1
A: (Math)
題目就不詳說了。
數據很小, 題目也很直觀, 基本有bitwise operation的底子可以直接code出來。
要是沒有的話其實暴試, repeat squaring之類的 怎樣也能AC。
數據很小, 題目也很直觀, 基本有bitwise operation的底子可以直接code出來。
要是沒有的話其實暴試, repeat squaring之類的 怎樣也能AC。
B: (String, Ad-hoc, STL)
這題是Given 一條 string S, 然後 有一堆range query [l_i, r_i] 及T , 代表在這個range (inclusive) 內的substring 要向右rotate (shift ) T 次.
老實說這條應該是想最久的吧...因為比題目結構嚇倒了, 直接想到什麼range query什麼segment tree都出來了。
結果第二天扮工時間再看題目, 發現數據根本很小, 直接暴力做就可以了...
當然T 可以很大, 但由於 rotate 多過range的長度等於重置一次, 直接T%L (L = r_i - l_i + 1) 就好了。
我是用最慢但應該最易看的白痴寫法: C++的 STL, substr() 了很多次, 左拆右拆的, 一樣能AC。
只是看了Peter神跟 Gary神的 Code, 他們都不需要用C++的東西, 有點慚愧...
老實說這條應該是想最久的吧...因為比題目結構嚇倒了, 直接想到什麼range query什麼segment tree都出來了。
結果第二天扮工時間再看題目, 發現數據根本很小, 直接暴力做就可以了...
當然T 可以很大, 但由於 rotate 多過range的長度等於重置一次, 直接T%L (L = r_i - l_i + 1) 就好了。
我是用最慢但應該最易看的白痴寫法: C++的 STL, substr() 了很多次, 左拆右拆的, 一樣能AC。
只是看了Peter神跟 Gary神的 Code, 他們都不需要用C++的東西, 有點慚愧...
D: (Graph: DFS)
容我先跳過C, 因為題C數據上是最少人AC的, 我也最後才做, 也是相對學習得較多的一題。
題目很有趣, Given 一個2D Grid, 每格可以是路, 可以是牆。 如果是牆的話上面會有名畫一張。 然後Given m 個起始位置, 問如果你由該位置開始一直行, 怎樣行都可以 (除了穿牆), 你總共能看到多少名畫。
這樣想吧, 其實連續起來的路是一個component, Grid入面就有數個disjoint 既 components, 每個component入面不論那點作為開始, 看到的數量也是一樣的。
每個component 就像是圍棋內的一塊棋, 他們的「氣」就是名畫的數量
扯遠了...其實沒什麼關係XD
所以做法很簡單, 直接DFS, 把每個位置都歸入某個component內, 順便計算該component能看到的名畫數量。如果某點已經知道屬於那個component, 那便不用再花時間DFS了, 直接output 答案便可。 每個格子能看到的名畫數量可以在DFS前先計算好。
思路不難想, 算是鬥快寫DFS吧?
AC Code: http://www.codeforces.com/contest/598/submission/18879479
題目是這樣的: 有朱古力一條, 有N*M 格, 現在你可以拆斷它, 但一定要直線或橫線, 整數地拆。每拆一次 cost 為該線的square, 問如果你想要exactly k 格朱古力, 最少cost 的拆法要多少
這類題目我有陰影, 總是想起從前有條POJ 好像叫Stick的題目, 當年覺得完全沒有思路, 不可能做得出, 然後Leo好像淡淡說了句: 呢條唔係Search ja咩?
自那時起我都以為Search是一類特別的題目Category...
其實到現在也不太清楚他講乜春, 但這條的確是Searching, 雖然實作上是用DP做啦 (可以這樣說吧?)
數據很小, 其實也明顯是要你直接用DP做的了, 數據小到DP的方法也很直接
DP(N, M, K) := Minimum Cost to get K chocolates out of N*M one
DP(N, M, K) = Min ( DP(N_1, M, K_1) + DP(N_2, M, K_2) + M*M, DP(N, M_1, K_1) + DP(N, M_2, K_2) + N*N) for all N_1+N_2 = N, M_1+M_2 = M, K_1+K_2 = K
說白了, 就是每條邊, 和K的每種可能性 (K=4的話, 左邊0粒, 右邊4粒 / 左邊1粒, 右邊3粒...)都試掉, 看那種最優。
Code是不難寫的, base case小心點處理就好了。我是用Top-Down的寫法, Peter 神是用Bottom-Up的, 分別也不太大。
唯一WA了一棍...是被白痴位陰掉了...他有很大量的Query數目...但其實DP State pre-compute一次就行了, 第一棍把DP 放進 Input Query 的loop 裡了, 吃了TLE。
要說這條的學習, 我總是在想要是數據再大一點, 不能直接DP時, 會不會有其它做法, 這個還未有答案。
另外就是我對於分析這種Recursion + Memorization 的Complexity 很弱, 完全不知怎樣分析, master theorem好像也不能apply, 當然靠經驗感覺我知道肯定不會TLE, 但從來不知道正確及General的分析方法, 究竟是Big-O of 什麼。
有關這個, 我在Stack Overflow上問了一下, 好像也沒什麼特別的答案
http://stackoverflow.com/questions/38215549/how-to-analysis-the-time-complexity-of-this-code/38240874?noredirect=1#comment63937690_38240874
倒是Peter神的想法是把DP state的tree 做一次DFS, 所以是O(|V|+|E|), 然後看題目決定|V|和|E|是什麼, 這個想法當然好, 但我不肯定是不是General所有DP 的solution都可以這樣想, anyway仿然要#Adore#一下
扯遠了...其實沒什麼關係XD
所以做法很簡單, 直接DFS, 把每個位置都歸入某個component內, 順便計算該component能看到的名畫數量。如果某點已經知道屬於那個component, 那便不用再花時間DFS了, 直接output 答案便可。 每個格子能看到的名畫數量可以在DFS前先計算好。
思路不難想, 算是鬥快寫DFS吧?
AC Code: http://www.codeforces.com/contest/598/submission/18879479
E: (DP)
這題老實說, 對我來講算是開始有難度了...雖然我知還是很簡單的題目。題目是這樣的: 有朱古力一條, 有N*M 格, 現在你可以拆斷它, 但一定要直線或橫線, 整數地拆。每拆一次 cost 為該線的square, 問如果你想要exactly k 格朱古力, 最少cost 的拆法要多少
這類題目我有陰影, 總是想起從前有條POJ 好像叫Stick的題目, 當年覺得完全沒有思路, 不可能做得出, 然後Leo好像淡淡說了句: 呢條唔係Search ja咩?
自那時起我都以為Search是一類特別的題目Category...
其實到現在也不太清楚他講乜春, 但這條的確是Searching, 雖然實作上是用DP做啦 (可以這樣說吧?)
數據很小, 其實也明顯是要你直接用DP做的了, 數據小到DP的方法也很直接
DP(N, M, K) := Minimum Cost to get K chocolates out of N*M one
DP(N, M, K) = Min ( DP(N_1, M, K_1) + DP(N_2, M, K_2) + M*M, DP(N, M_1, K_1) + DP(N, M_2, K_2) + N*N) for all N_1+N_2 = N, M_1+M_2 = M, K_1+K_2 = K
說白了, 就是每條邊, 和K的每種可能性 (K=4的話, 左邊0粒, 右邊4粒 / 左邊1粒, 右邊3粒...)都試掉, 看那種最優。
Code是不難寫的, base case小心點處理就好了。我是用Top-Down的寫法, Peter 神是用Bottom-Up的, 分別也不太大。
唯一WA了一棍...是被白痴位陰掉了...他有很大量的Query數目...但其實DP State pre-compute一次就行了, 第一棍把DP 放進 Input Query 的loop 裡了, 吃了TLE。
要說這條的學習, 我總是在想要是數據再大一點, 不能直接DP時, 會不會有其它做法, 這個還未有答案。
另外就是我對於分析這種Recursion + Memorization 的Complexity 很弱, 完全不知怎樣分析, master theorem好像也不能apply, 當然靠經驗感覺我知道肯定不會TLE, 但從來不知道正確及General的分析方法, 究竟是Big-O of 什麼。
有關這個, 我在Stack Overflow上問了一下, 好像也沒什麼特別的答案
http://stackoverflow.com/questions/38215549/how-to-analysis-the-time-complexity-of-this-code/38240874?noredirect=1#comment63937690_38240874
倒是Peter神的想法是把DP state的tree 做一次DFS, 所以是O(|V|+|E|), 然後看題目決定|V|和|E|是什麼, 這個想法當然好, 但我不肯定是不是General所有DP 的solution都可以這樣想, anyway仿然要#Adore#一下
C: (Geom)
最後解到的這題, 只有63個人AC了的這題, 其實不難理解。
題目本身不算難...但是一碰到Geom, 就一定會弄到精度問題, WA也不為過
我沒有為自己WA了 13棍而開脫。
好吧先說題目 :)
題目是Given 10^5 個 vector, 全部連住Origin的。問那兩支vector的角是最小的, 這裡說的角沒有方向, 總之是該兩支vector的+角或-角magnitude 最小的 就ok。可以print出任何答案。
話說這樣的數據量, 基本上是要O( N lg(N) )的了, 看完題目基本就是Sort by Angle了吧
印象中Sort by Angle有兩種方法做, 但我只記得一種: 用atan2() 來sort.
當然n年沒有code過 geom題目的我, 一定要google atan2的用法...那些就不說了 :(
題解就是sort 完, 然後每一支vector跟前一支 (或後一支) 計一下角度, 然後找最minimum 那一pair 就好了 (最minimum 那一pair 在sort 完後一定是相鄰的, 對吧?)
小心最後一支也要跟第一支比較。
問題來了, 一直WA一直WA, 完全不知錯在那裡。看完TEST CASE更加相信是精度問題...
所以這題的99%難度在精度問題。 以往我只知道要用eps, 但怎樣用, 為何要這樣用我也忘光了。所以我發射飛彈, 試了eps 由 e-6 開始到e-18 都試過了, 全部都WA....
終於最後, 忍不住, 隨手打開第一名那個的Code看...根本與我沒分別...唯一的分別, 在於他是用long double, 我是用double!!!!
我改完之後, 果然AC了.....!
究竟何時要用long double, 何時要用double? 我也不知道, 這是一個謎...
另外之後我問了GG, 究竟何時要用eps, 現在有一個更好的concept了....
原來eps的原意是比較2個double variable是否一樣, 而當你想 differentiate 它們的時候, 就要用上eps 來比較 ( <= 或 >= ). 在這題中用不上, 因為我們只考慮角度, 有些題目可能也要考慮長度, 那麼可能就有分別了 (sort by 角度, 角度一樣不等於"一樣")
而eps 通常是set e-8, 是-8, 至於為什麼, 連GG也說不知道 =.=
F: (Geom?)(最後一題的思路有時間後補吧...)
這題的題目光用看的也感受到變態程度, 直到現在更只有 2個人AC...
題目大意是Given 一個 N-Side polygon, 可以Concave, Input格式為N 點, 點可以同線。
然後Given 一堆query, 每個query 是一條線, (可能) intercept with this polygon.
問, 在這條線在polygon 內的總長度是多少?
好吧我的確沒什麼完整的思路, 但腦海中立即出現的是當年CSC326 學的 Ray-Casting Algorithm (好像是叫這名字?)
好像是Given一點, 向住某一條線"射"出去, 看看穿過多少條polygon的邊。按照單雙數, 可以得知該點是否在Polygon內。
或許當中有某些思路可以apply? 沒什麼方向。 結論是為何Education Round沒有Editorial??
F: (Geom?)
這題的題目光用看的也感受到變態程度, 直到現在更只有 2個人AC...
題目大意是Given 一個 N-Side polygon, 可以Concave, Input格式為N 點, 點可以同線。
然後Given 一堆query, 每個query 是一條線, (可能) intercept with this polygon.
問, 在這條線在polygon 內的總長度是多少?
好吧我的確沒什麼完整的思路, 但腦海中立即出現的是當年CSC326 學的 Ray-Casting Algorithm (好像是叫這名字?)
好像是Given一點, 向住某一條線"射"出去, 看看穿過多少條polygon的邊。按照單雙數, 可以得知該點是否在Polygon內。
或許當中有某些思路可以apply? 沒什麼方向。 結論是為何Education Round沒有Editorial??
PS (Bonus)
雖然很慢, 但有感覺自己一直在進步, 可能一些以前沒有學懂的現在都會主動去學而且大約都能學會。但實在是不夠時間用, 在教會也開始要幫忙作鼓手跟導師, 工作上也愈來愈忙 (雖然快將轉工了應該), 加上要做Gym還有一大堆聚會要去, 有種感覺是一天24小時真的太少了....
另外之前在FB 路過看到一條好像是數學Olympic的題目, 對於0數學底的我, 也有些想法, 跟Peter神討論了一下, 可惜還是沒有答案~
以下是完全沒有數學底子 我的想法, 正確答案在Facebook 這幅圖的top comment已經有了 (按照那個like的數目來看) 好像是用一些我看不明白的number theory 的argument
所以這兒的想法只是自己的FF
By Fermat's Little's Theorem, y^2 = 1 (mod 3), So L.H.S. = y^2 ... y^2 * y (mod 3) = y (mod 3)
R.H.S. = x^3 + 37 (mod 3), So y = x^3 + 37 (mod 3), Q.E.D.
然後下面是一些完全9 up 的東西, 是關於Chinese Remainder Theorem的。
從 Wiki 可以看到,
這兒我重點關注 any sequence of integers a_i 這句。
我想, 這是不是等同說明
Given y = x^3 + 37 (mod 3)
There Exist some a' = x^3 + 37 (mod 5) such that
y = a' (mod 5)
因為 3 跟 5是co-prime嘛, 然後x^3 + 37 也肯定是integer for any x
同理 其它 prime number 也跟 3 是 co-prime, 所以 y = x^3 + 37 (mod p)
然後L.H.S 跟R.H.S. 一同自乘 37次 就行了...
但這只是我的狂想, 因為我根本不了解Chinese Remainder Theorem, 特別是我覺得以上的argument 有違
以下是完全沒有數學底子 我的想法, 正確答案在Facebook 這幅圖的top comment已經有了 (按照那個like的數目來看) 好像是用一些我看不明白的number theory 的argument
所以這兒的想法只是自己的FF
首先證明 y = x^3 + 37 (mod 3)
By Fermat's Little's Theorem, y^2 = 1 (mod 3), So L.H.S. = y^2 ... y^2 * y (mod 3) = y (mod 3)
R.H.S. = x^3 + 37 (mod 3), So y = x^3 + 37 (mod 3), Q.E.D.
然後下面是一些完全9 up 的東西, 是關於Chinese Remainder Theorem的。
從 Wiki 可以看到,
Suppose n1, ..., nk are positive integers that are pairwise coprime. Then, for any given sequence of integers a1, ..., ak, there exists an integer x solving the following system of simultaneous congruences.
這兒我重點關注 any sequence of integers a_i 這句。
我想, 這是不是等同說明
Given y = x^3 + 37 (mod 3)
There Exist some a' = x^3 + 37 (mod 5) such that
y = a' (mod 5)
因為 3 跟 5是co-prime嘛, 然後x^3 + 37 也肯定是integer for any x
同理 其它 prime number 也跟 3 是 co-prime, 所以 y = x^3 + 37 (mod p)
然後L.H.S 跟R.H.S. 一同自乘 37次 就行了...
但這只是我的狂想, 因為我根本不了解Chinese Remainder Theorem, 特別是我覺得以上的argument 有違
所以也就沒再深究下去了。(後註: 後來想下去果然還是錯得很離譜XD)A solution x exists if and only if
