New Platform & New Tutorial Material!! SPOJ + T-414-ÁFLV + 短期方向

這篇之後就剩下Google Code Jam 1B的記錄了..那真是慘痛的經驗...經一事長一智吧...
下篇再詳說了

這篇短篇只是把一些散亂的東東集中起來記一下~

SPOJ

首先是一個新發現的Programming Contest 平台~
很漂亮很boostrap的, 我真的覺得很不錯, 叫 Sphere Online Judge (SPOJ)
平台漂亮, 提交容易, 題目也很新很多
不過還是近於POJ 那種題目庫向的, 不太多contest向
contest還是CF / TC 那面較好吧~ :)
這個平台最強大的地方, 是有一個(不知道是否官方) 的 sample case tester
可以自己打input 看看官方答案的output是什麼這樣子
然後還有一個random input generator, 可以按要求random給出數據!
這2樣東西加起來要找counter example / test case就易很多了...
我也是用這兩件事才能AC下面所說的一題...

得知這個平台是從在公司用Ideone.com 打C++時右邊一些廣告發現的,
開頭以為是一些"野平台", 沒太大注意

後來偶然下, 為了解決一條在Stack Overflow的題目 (那題目就是問SPOJ的一條題目)
我就跑去玩了~ 話說在Stack Overflow答題目真的是一個學習/試試自己的好方法
快點有1000分就好了

What is wrong with this solution while solving JUICE on SPOJ?

在我威迫利誘之下, 他還是要Accept我的答案...哈哈! (誰叫他想要看AC的Code, 就要付出啊...)

話說這一題也很有學習的價值, 是一條 O(N^2) 的DP...
題目跟答案直接去看Stack Overflow 的Post就可以了

我再次覺得DP真的很彈性, 而且只要concept正確的話, 在題目的context 下
可以special handle很多東西 (甚至需要你這樣做) 才能AC...

這題來說就是要把同一個Starting Time 卻不是最後的segment 的state強制設定到負無限
其實只要有方法不使用它們update 更大的state就好了, 這只是其中一個方法
要找出這個問題, 我就是利用了 SPOJ Toolkit 這個強大的工具...這也令我更喜歡這個平台

然後針對這類interval graph的題目...其實我也很混亂的說
sort by start time還是end time, 還是sort by segment length...我印象中好像每一題都不同...
看來沒有什麼一定的rule 吧?

還有就是由於之前 (in progress)在重溫 CSC2110的notes
記得interval graph是 graph coloring problem 的其中一種特例, 是有解的
開頭以為是問那個方法, 還跑去重溫了...結果卻不是那回事
但Interval Graph還是一種很特別的東東
立志的notes也提出了一種叫 "Maximum Degree Ordering" 的theory
說了一種greedy找 minimum coloring on interval graph的方法
這種思路是絕對要學習的 (由於是特例, 直接記下也可以, 其實我還是更偏向這種學習方法)

所以結語是:  SPOJ, 好平台, 不用嗎?

T-414-ÁFLV Programming Contest Course

剛剛在某CF comment中看到有人介紹的一個好物...

不知道是什麼人寫的Course, 裡面還很正式的有評分, 功課等等

很好很強大.. 

T-414-ÁFLV: A Competitive Programming Course

暫時看了一下outline 和introduction, 好像很可靠的樣子

盡快學習一下好了~

這時也想了一下放在心中很久的疑慮:
其實material真的不少, 要多少有多少

演算法筆記, 這個programming course, TC 上的Tutorial....等等

問題是各家有各家的心法, 大家不論code還是學習的方法也很不同

即使是同一個技巧 / algorithm也差很遠

以前的我是想找"最好"的一個去學習的, 但慢慢發現根本沒有"最好"這回事

只有"最適合"自己的一套, 例如我很快就會說的 (我記得的...) KMP

那個複雜度的解釋,演算法筆記那個解釋看了明白卻不太能記下

Google隨便找了另一份notes的解釋是另一個合理的思路, 明白易記

所以其實根本不用強求, 也不用硬要學習那一份material

反正就都看看, 不明白就再找同一個topic的其它material, 找到自己最能明白理解的就好

Code的方面則最好在明白了之後有自己一套習慣的寫法

這是現在自己最習慣易學習的模式了...怎麼以前都不懂這些道理

最後的最後, 由於近來真的忙死了...還是一樣一樣整理下事件的先後次序吧...短期的計劃是這樣吧:

1. 先集中準備下星期的Google Code Jam 1C...誰叫我1B差幾名才能Advance...
2. 1C完了之後, 把1B, 1C的題目能學能做的都先搞定
3. 繼續重溫CSC2110的Notes, 還差最後幾課了不能放棄
4. 學習+記下說了很久的String Searching Algorithms + Trie!
5. 開始跟住 T-414-ÁFLV 的課程學習 (重中之重)

中間的其它比賽能不打的都先不打了, 不然學習不了也沒好處

把這些都做得七七八八再繼續看演算法筆記尋尋寶吧

還有之前一直玩的Maya 2015也要找時間繼續...真的忙死了 = =

Codeforces Round #300

先來兩張圖:

久別的參賽...這是一場 Div 2 + Div 1一起玩的比賽....
誘因是前300名有機會有T-Shirt...才厚臉皮參加的

運氣使然下, 結果比想像中好太多了...

雖然只做了最簡單, Div 2水平的4題 (共8題題目)

Room中竟然也排第6 

Rating也+158..差一點就變黃色User了=.=

興奮開心過後, 還是要面對一些問題:
首先頭4題一棍AC是高興的, 但除了D之外其實是很簡單的Div 2題目

D也不算難..但我認為之前的我未必能做到就是了...

而E 跟 F 才是真正的考驗, AC人數很合理的Div 1水平...

我認為要在比賽中能AC 這2題 其中1題才能算是Div 1吧...

這2題賽後幾經辛苦下也AC了...雖然還有些疑問

這場的Editorial 這2題寫得很亂..基本還是要自己想, 外加Peter神秒殺後也給了一點hints之類

過了之後在Editorial也試著把自己的想法留了comment, 題 E也有幾個正評, 太好了

至於G跟H 果斷放棄, 賽中不過100人能提交...賽後看Editorial也看不懂

暫時先放棄

結論: 先集中記下 題A-F好了

Codeforces Round #300

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

A: (Ad-hoc, String)

很基本的String題目, 就是問把一個substring移除後, 可以把string 變成 "CODEFORCES"嗎?

B: (Greedy)

這題可以秒殺是因為跟我曾經答過的Stack Overflow題目很像...
題目給了一個數字(n <= 10^6), 問把它拆成sum of Quasi Binary, 最少需要拆多少個?
Quasi Binary的定義是數字只由0或1組成: 10001, 10101, 10000...etc

先看Stack Overflow的題目: (shole是我在SO的名字)
Logic: Applying gravity to a vector

I think it is as simple as counting the total '1' bit of each position...

我這句也完全能apply在這題呢! 基本上就是每個digit 要不是0的話就是 >= 1, 還可以 (需要) 拆多一個Quasi Binary而在該位置也是1...然後原數字的該digit 就減1, 如此類推直到原數字變成0就好了

這題好像有人用很強的DP做...我是完全不知道怎樣用DP做的

C: (Math, Greedy)

題目給了n pair 數字 <a_i, b_i>
a_i 代表日子, b_i 代表高度
每日與隔日(前後一日)的高度最多能相差1
在給定了的n pair 數字和要符合這個條件下
最高的高度可以是多少? 要是本身 n pair 的input 不合理則說"IMPOSSIBLE"

n pair數字把日子分隔了n+1段
每段各自求最高的高度就可以了...
由於要符合條件, 最高的高度是能直接算出的
在紙上算了算...我好像寫了一條formula 出來
直接把 第 x日跟第y日之間的最大高度算出 (第x日的高度與第y日的高度沒有限制, 可以是h_x > h_y 或 h_x <= h_y)

   LL k = (h[i+1] + d[i+1] + d[i] - h[i])/2;

h 跟 d 是高度跟 日子

每一段都算一下取maximum的高度, 頭尾兩段特別處理就好了
O(n)的Greedy算法完成

算高度那一段有人用binary search做的 (好似係)

D: (Brute Force)

這題是賽中最後做到的一題了...話說本來連這題也苦無對策的
在AC之後才覺得這題其實很直接啊...證明以前水平太低了-.-

題目給了一個棋盤 棋盤上有棋數隻 (同一種類的)
然後mark了 那些位置是能被某些棋"吃掉"的
棋子自己的位置 可以是被"吃掉" 可以沒被"吃掉"

然後問: 這類棋子的移動方式怎樣? (可吃掉的位置)
要是有多種答案隨便輸出即可
(詳細要看輸入輸出例子, 自己按link看吧)

這類題目....除了暴試我也沒其它想法了
題目數據最大也是O(n^4) , 絕對是叫你暴試的

但開頭的想法怎樣也要O(n^5), 所以也想放棄了...
然後逆轉思維的時間到了..其實是在看例題輸出的時候想到的

題目input是 n*n 的棋盤 (n <= 50)
而output 是 2*n-1 * 2*n-1的棋盤...而棋子是在這兒的中間

如果我不是 "for 每隻在input的棋, for 每一格看看是不是由這隻棋吃掉.. for..." 這樣傻的想法
而是從output來想, "output的每一格, 與正中央(棋子)的 delta x, delta y 是已知的, for 每一格 O(100^2) , 看看input 的每一隻棋 O(50^2) 的delta x, delta y 位置是不是能吃掉 (或者另一隻棋或者out of bound)"

這樣的話是 O(2*2*50^4) = O(n^4)! 很像樣了, 正確性我認為也是self-explain! 也很好code!
太好了....回頭再想為什麼這樣暴試會快一點, 是因為output 限制了一隻棋能吃掉的range...
這樣其實不用每隻棋把全範圍試了...

Editorial好像不是這樣試的, 但comment中有一個很多正評的做法是這樣
Editorial也有一個挑戰: 用O(n^2 lg n) 解決同一問題...很變態的挑戰=.=

E: (DP on Tree, Graph)

終於到這一題了...賽後檢討的一題
很難很難, 我認為絕對是 Div 1的題目
而且下次再出現這樣的題目我也應該不懂=.=

題目很直接是DP on Tree的了, 由於每個state只會做一次, 基本上也可以用DFS代替

由於我花了一段篇幅在Editorial的comment寫了這題的思路, 就不詳細說了
http://codeforces.com/blog/entry/17612#comment-225396


這題印象最深的是...DP min 跟DP max 這2個state的轉移方式可以完全不同...
以前直覺上是相差不遠的
而這題完全經過一些很變態的分析之後, 發現一個的轉移是 summation(), 另一個是maximum()
太變態了...
把DP的答案強硬地控制在 [1, # of leaf under this node] 這個狀態定義也很變態

終歸一句: 這題學習到的是 DP的彈性真的很大...不聰明地分析根本不可能做到的吧...

F: (Data Structure Usage, BIT, Segment Tree, Math)

另一題變態的題目...

這題也有點故事的...話說有2個approach

一個是O(n lg^2 n)的, 另一個是 O(n sqrt(n))

我本身的想法是第一個approach which is 正確的想法

但那一個approach 以我的想法來說

是要用某些data structure(我認為BIT/ Segment Tree都可以) 在O(lg n) 內query 到 range 內的inversion總數, Editorial也是這樣說的, 但沒詳細解說怎樣做, 我在comment問了一下吃白果了

為此我還在Stack Overflow問了, 但是沒答案, 有人知道的煩請答一下

Range Query the number of inversion in O(lg N)

由於Peter神用approach 2 已經秒殺了這題, 我就認輸了

看了一下某些紅字User的code, 發現90%人都是用approach 2的

而另外10%人, 用了一種叫"Wavelet Matrix"的template, 我認為就是approach 1需要用到的data structure吧....話說也看到有人真的用很簡單的Segment Tree過了...沒深究下去了

果斷用approach 2試試做一下 (比賽中90%用的方法, 理論上應該要學習下思路的)

approach 2 是有 sqrt(n) 在內的...

關於這一點, 我早有感受: 我對 SQRT(N)相關的複雜度完全不敏感!
什麼RMQ, LCA好像也有SQRT(N)的存在...所以其實SQRT(N)也不是冷門的

也是要學習開始敏感了

暫時我的感覺是, 如果有關於 FACTOR / 除數 之類的題目, SQRT(N) 也可能有關係

(想想Prime Sieve的原理)

這題也是這樣, http://codeforces.com/blog/entry/17612#comment-224861

我comment中的2個case 是由於那個除數直接導出的結果, 令到總segment的數量只有

2*SQRT(N) = O(SQRT(N))

感覺上這樣分2個case歸納出SQRT(N)的手段可能很common, 記下比較好 (我是第一次見)

另外這題也是很有得著的!

首先就是一個可能頗常用的技巧
"Delta Encoding + Partial Sum"!! O(N)

Delta_encoding是第一次聽, 但做法不是第一次用了...這次更"學術"地看看這是什麼東東

簡單地說, 他是一個array, array中的每一格記下與上一格的difference

然後把這array 做partial sum, partial sum後每一格是原來的data array

例如 現在range [1,10] = {0}, 我做了幾個operations

1. [3,5] +1

2. [7,8] +1

3. [4,6] - 1

問現在range[1,10]的value?

這樣每個operation可以用Delta Encoding的手法以O(1) update一下:
[3,5]+1 --->  range[3]++; range[6]--;

[7,8]+1 --->  range[7]++; range[9]--;

[4,6]-1  ---> range[4]--; range[7]++;

現在range的array是 {0,0,1,-1,0,-1,2,0,-1,0}
然後以O(N)在這上面做 partial sum, 得出
{0,0,1,0,0,-1,1,1,0,0}

完全正確!

這樣代表什麼? 是代表其實可以用這方法取代BIT / Segment Tree嗎?
不!!
這個方法只能處理Static的operation, 不能online dynamice地update segment和query segment

是有點相像但卻完全不同的處理手法...

另外這個方法感覺上好像一定要配合partial sum才有用武之地?

所以"Delta Encoding + Partial Sum"是一個以O(N) Offline 處理range update operations的手法

另外學到的是 Floor() / Ceil() Properties!

這題用approach 2 的核心思路, 是在於由一個Floor() / Ceil() 的Property推算出一個連續的 k  range

這個推算如果不懂 Floor() / Ceil() Properties (如我一樣) 是很難的...

幸好賽後找到了一個不錯的 Reference! 

Useful Properties of the Floor and Ceil Functions

除了在這次Editorial 推算中出現的Property外, 還出現了很多年前忘了是Chin爺說的還是說的

"沒有precision lost的ceil 方法"! 就是:⌈​m​​n​​⌉=⌊​m​​n+m−1​​⌋

在coding中, 直接 (n+m-1)/m 就做到 ceil (n/m) 的效果了

Reference也很好的解釋了如何得出這條式的...!

所以這題就這樣了...

學習到的是

1. 對SQRT(N)要更敏感一點
2. Delta Encoding + Partial Sum的技巧
3. Floor() / Ceil() 的Properties

話說我對Approach 1 (就是我原先的想法) 還是念念不忘, 要是有神人能用簡單的 BIT / Segment 做到 而不是用什麼 "Wavelet Matrix" 的話, 煩請告知一下!

PS: 希望下場CF 也是正分, 可以上黃色吧...