Codeforces Round #293 (Div. 2)

一場只有Div. 2 的比賽

題目有6題, A-E基本上都應該能做得出來吧 , D跟E要小心一點...

其實A-E已經做完很多日, 只有F一直沒做所以就沒記下...

終於昨晚也過了F

今天也順路經過了 Google Code Jam 2014 Round 1A, 還有很順路地revisit了 hamming problem一次, 我也知道很雜食, 證明在公司開始忙了, 不能很有系統地學/看我計劃好的東西

.這2件事我看看如果歸納以後再分開寫一篇吧...(還有說好的String Searching沒寫...)

Codeforces Round #293 (Div. 2)

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

A: (Greedy)

題目給了2條string s跟t,  長度都 <= 100, 求任意一條 比s 大又比t 小的string

就Greedy地construct就好了...

B: (Ad-hoc, Greedy)

也是給了2條string s跟t, 然後如果s的某一個字母跟t 的完全一樣, 那麼把counter1 加1, 要是他們只有大小楷不同則把counter2 加1, 求最大的counter1, tie break是求最大的counter2

有點煩膠的一題, 但也只是Implementation的問題, 沒什麼特別的算法~ 

就是Greedy地先把counter1 加到最大, 然後對counter2同樣處理~

C: (Ad-hoc,  Data Structure Usage)

我認為是最煩膠的一題, 也很難分類

題目本身是很簡單的...我想主要是靠他的煩膠度使玩家們WA吧

由於題目太煩膠了, 我就不詳寫了

但Solution是 利用 2個array,  array A 儲存的是 array B 的 index, array B相對的也儲存了array A相對應的index, 然後在For loop 中每次用O(1) manipulate 這2個array 的其中一個element

所以總共是O(N)

D: (Probability, DP)

開始有難度的一題, 主要是因為出現了我很怕的probability.

題目本身倒是很簡單的:

現在有一條queue有n 個人, 每一秒第一個人有p 的機會離開隊伍(不再回來), 有1-p的機會不動

求 t 秒後已離開人數的expected value

E(X) =  p(0)*0 + p(1)*1 + .... + p(n)*n,  p(i) 是在 t 秒後有 i 個人已經離開的機會率

這個(些)機會率我們可以先用DP求出, 然後就能計到E(X)

設DP(i, x) 為第 i 秒, 有x 個人已經離開的機會率

那麼DP(i ,x ) = DP(i-1, x) * C +  DP(i-1, x-1)*p ,  C = { 1  if  x >= n , 1-p otherwise}

注意上面粗體的部分, 是當 x > 0的時候才有的, 不然不用加

(physical meaning是: 如果一個人都還沒有離開, 根本就沒有這個transition)

就這樣 O(N^2) 算完機率 就基本做完了

Code在這: http://codeforces.com/contest/518/submission/10483943

E: (Ad-hoc, Greedy)

可以說是這場最難想的一題, 也很難code,  總結是比F更難, F是難code而已

題目說給了一個SEQUENCE 和一個長度L
然後這個sequence 每個連續長L的subsequence sum會形式strictly increasing sequence

例子: {1,2,3,4,5,} L=3,   那麼1+2+3 = 6,  2+3+4  = 9, 3+4+5 = 12 --> {6,9,12}是strictly increasing

現在這個SEQUENCE有某些位置(可以無) 是 ?  

求一個填法such that SEQUENCE符合上面所說的條件

如果有數個Solution, 則取 sum( absolute value of a_i) 最小的 <--這句是令題目變很難的東東

這條真的是很麻煩很麻煩, 一步一步來看

首先連續長度L的sum, 其實有很多overlap的位置對吧, 那些位置反正都一樣

eg:  {1,2,3} 跟 {2,3,4}  那麼這些位置根本是什麼都沒關係 反正他們的sum一樣

所以其實連續L長度的Sum是increasing, 等於每相隔 L 的數字形成的sequence本身就要strictly increasing

那麼我們可以把原本的SEQUENCE拆成 L 條List,  它們形成原Sequence的Partition

由於這L 條List 是disjoint, 各自擊破就好了

集中看一條List吧:  {-2,?,5,7,?,?,10,?} 可能是這個樣子  我們的問題變成要把 ? (如果有的話)填上數字, 使這條List 

1. Strictly Increasing
2. Sum of absolute a_i  最小

當然可以的話當然很想全都填上0吧...

理想跟現實, 而且由於有負數的出現令問題更難

需要多一些觀察:

首先每堆連續的 ? 其實也各自不相關, 他們的value已經被前後非 ? 的value bound住了

所以也是可以分開分析

會發現有3個Cases

1. 前後都是non-negative (>= 0)
2. 前後都是non-positive (<= 0)
3. 前面negative, 後面positive

Case 1跟2是對稱的也很易明白: 如果是正數的話 我們就直接由前面+1, +1的填起就好了

因為這樣的absolute sum是最小的, 也肯定是strictly increasing; 如果負數的話則由後面-1,-1的填起, 總之我們想盡量填靠近 0 的數字

Case 3就很麻煩了, 不難發現Case 3 肯定有一個位置是0了

然後就很直觀地把0 放在區間的中間, 前後 +1 -1 的填就好了對嗎

錯!! 因為前後非? value的問題, 這樣填可能會變成no solution, 但其實是有solution的, 只是 0 不能放中間

這步令我很想哭, 寫得很辛苦也很難看, 但也想不到什麼更方便的方法

就是計算由左面 (負數那面) 開始算起, 最遠可以放0的位置, 對稱的, 也計算由右面(正數那面)最遠可以放0的位置,  要是有solution的話他們一定會overlap, 放在overlap同時最近區間中間的位置就好了, 然後就是左右開始填起 (一面+1 一面-1的)

用文字說就已經很煩了, 寫起上來更是辛酸...老實說如果真的在比賽, 很有可能根本放棄這題了, 又或者根本不能很肯定地在時間內提交...

Code: http://codeforces.com/contest/518/submission/10556877

F: (Combinatorics, Binary Indexed Tree, Data Structure Usage)

最後最後的一題了, 老實說最後能過這題還是很有成功感的

其中一個原因是自前陣子再了解BIT的用法和寫法後 

在這題可以用上並且AC了 !

其實這題所有難度在於Coding...算法(如果是我想的那個寫法)

是很易很易想到的

先來說說題目

給了一個2D grid (1000*1000), 當然也是有些格子不能走的,  現在要開始畫一條線

           ....#            ....#            .*..#
           *****            ****.            .***.
           ..#..            ..#*.            ..#*.
           #...#            #..*#            #..*#
           .....            ...*.            ...*.

借用了題目的例子: 上面 . 是空格, # 是不能走的, * 是你要畫的線

這條線有些條件:

1. 一定要在邊開始和完結, 不能在角
2. 只有頭尾兩點可以在邊上, 其它都要在更中間的位置
3. 邊上不能有連續2點或以上的線
4. 線可以90度轉, 最多轉2次
5. 線,當然是連續的

就這樣吧 (題目還說了很多, 歸納起上來也只有這些)

題目很簡單, 給了一個grid, 問有多少種不同合法的線?

我再強調算法很簡單的, 就是直接做=.=

首先把答案分成 3 種去數會更易數: 沒有轉向(直線), 轉了一次向(L型), 轉了2次向(U型或閃電型)

基本上前兩種是很直接的吧?
我們用Partial Sum precompute了從4條邊各自可以最長向中間伸展的長度

例如partialLR[i] 就是 第 i row,  由左至右, 可以最遠的距離

同理partialRL[i], partialTB[i], partialBT[i]也是這樣

那麼直線的就直接O(N^2)數好了,  L型的就是O(N^2), 每一row 看看vertial 那個partial sum能否達到這個row 這樣

當然, 最難的一定是轉向2次的了

但還是很直觀的: 我們再precompute另一些array, 我叫他們做lengthLR[i][j] (還有另外3個)
代表 (i,j) 向某個方向最遠的長度 (其實可以用上面的partial sum array同時間做這件事)

eg:  .....#...#   -->  12345#123#  左面的數字就是lengthLR[i][j] 在該格的value, 代表由左至右, (i,j)距離上一格牆的距離

好了 考慮以下U型的情況(閃電型同理, 還有另外3個方向也同理=.=)

........

...#...

......#.

.....#..

.........    

.....#..

我知道很不明顯, 但上面有一點紅色的, 假設現在我在這一點 (我會O(N^2)暴試所有點

現在我想數以左邊那條BORDER為依歸的U型數目 (就是反轉的C型), 而紅點是這個倒"C"型的下面那條橫線, 這樣我們數的時候不會重覆

我要數的很簡單: 是這一點向上直到有牆 (用我們的length array可以直接算出),  在這一個Range入面有多少個左面開始partial sum 比紅點遠的 (或者一樣)?

上面的例子來說, 有2個, 這樣理論上就有2個 倒C型成了, 但留意其中一個是會在左BORDER連續佔了2格, 不合法的, 簡單說, 不能選紅點鄰住那些格, 因為這些格做了U TURN, 那條邊永遠都佔了邊上連續2格

 

話雖如此, 其實也只是RANGE的選擇而已

閃電型也類似, 簡單地說,  用我們precompute的partial sum + length array, 我們可以O(1)的就選好了我們的Range, 問題是我們要query, query的是這個range來,  # of 大於某個數的partial sum
這是赤裸裸的Range統計問題, 這時就是BIT出場的機會了!

log (1000) ~ 10, 所以其實O(N^2 lg(N) 也是很快的, 這使我更有信心是用BIT了

設bitLR(i, v) 代表由第0 row 至第 i row,  (左至右的partial sum where >= v)的數目

其它方向也類似, 這樣, 我們在precompute partial sum時也可以順路update 這些 BIT

剩下的只是按RULES, 暴試所有點O(N^2),  找出Range, 執行Query  O(lg N)

這樣就能數出轉向2次的合法線總數

把3個答案加起來就好了

Code很長, 超過200行=.=

其實有某些array 不用開的, 根本用不上

但看到有人幾十行做完, 那根本不是這個算法吧?
但我看Editorial也是這樣做的說 ...

Code(慎入): http://codeforces.com/contest/518/submission/10706126