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 也是正分, 可以上黃色吧...