Codeforces Round #277 (Div. 2)

轉左新公司, 雖然工作和興趣已經慢慢轉移到.NET技術及Unity Game Design,
閑時仍然會做下題目, 發現斷斷續續做左唔少, 年代久遠完全沒印象
只好挑近幾日做的兩場...

話說已經無認真做 (2小時內完成)既態度, 有d題目甚至分開幾日做
我諗做到就好了,  近黎都保持div 2 做到4-5題, 算唔錯了...

Codeforces Round #277 (Div. 2)

http://codeforces.com/contest/486/problems

A:
頹題, 如題意所示, 計一個簡單function 的instance f(n)

B:
出奇的略有煩膠的題目...solution倒是很直接的
AC後略略看過別人的code和editorial, 發現好像不能避免煩膠的寫法

題意如下:
Given 一個 m x n matrix A, 每格either 0 或者 1, 求reverse engine 一個matrix B,
s.t. A_i,j  = BITWISE_AND( B_i,x ,  B_y,j) for 1<= x <=n,  1<= y <= m

因為m , n 都很少 (< 100) 根本brute force就做完了  但很難避免3-4個loop的寫法...嗯

C: (Greedy)
真正既第一題, 題意如下:
Given 一條string s (length <= 10^5) 和 一個指針的位置 p,
每步可以做2種操作, 問minimum # steps
s.t.  s 變成一條palindrome

操作 1 是指針向左或向右移動一格, 然後這兒的移動是wrapping的,
即最左再左就是最右; 最右再左就最左

操作 2 是指針位置的字母加一或減一, 也是wrapping的,
即a 再減一變z ; z 加一變a

s 確定所有都為lowercase

題意很有趣, 但看完有嚇到...
諗真d 又唔係咁複雜, 首先不難發現操作1 跟操作2 是沒有關係的

來看看操作 2:
因為現在不同edit distance之類的設定, 不能加減字母, 而只能將現有字母一步步改變
然後按住palindrome的特性, 如果位置 x 跟 位置 x_reflection 的字母不同, 你一定要隨便
轉變一個令他們一樣, 轉那個都沒所謂, 反正你轉字母的cost (# of steps) 是定好的
跟移動的cost (操作 1)完全無關, 也就是可以分開precompute的意思

再來看操作 1:
不難想像, 根本不會出現wrapping的情況, 來看看其中一個情況:

_ y p _ x | x' _ p' y' _

p 為現在指針的位置,  x,y 跟x' , y' 是相對的字母位置,  | 沒特別意思, 是字串中間的分格線而已
想做的是, x 要變成跟x' 一樣, y 要變成跟y' 一樣, 這是操作2的cost, 但移動的cost 又怎算呢?

腦內生成一下可能的移動方法, 不難發現指針根本不會以任何方式移動到另一半
不然移動的cost會增大, 不去另一半就是最好的了, 這是greedy的思路
(這應該是能證明的, 實際上在公司裡我感覺能行就做了, 沒詳細證明...)

小總結: 操作1 跟 操作2 直接分開算, 實作的時候只要考慮指針是先向左走還是先向右走比較優就好了, 時間複雜度為 O(N)

D: (Graph, DP, Combinatorics)
這題有點興奮, 以前應該做不到吧...
雖然思路不知怎的突然走出來, 說是運氣都不為過就是了...

先來說說題目:

Given 一個 node數為 n (<= 2000) 的tree, 一個數字d (<= 2000)
每個node有一個value (<= 2000)

定義valid set 為一棵sub-tree, such that 該tree內的max. node value - min. node value <= d
求 valid set 的總數 (再mod 一個大數)

有點黃有點暴力, 開頭真的有點頭痛...
以前看見tree都有不好的感覺, 話說這次當然也是第一時間跑去想dp...
想想想, 好像不太能想到一個好的state

然後在紙上畫畫畫...又好像簡單的DFS能解決的樣子?
又怕會double count...

double count?? 突然靈光一閃, 運氣到了, 如果我先fix死一個node,
然後先找所有包括該node 的valid set...然後每個node都做一次, 不就不會double count了嗎?

然後..然後...不如直接把該node定為最大的node, 啊我是說
Fix 一個node n, 然後找出所有包括node n, 而且 node n 的value就是最大的valid set!

這個好像DFS能行...只要我search到一個node的value大於 root 的value, 或者 abs. difference > d
就return, 不然就一路search下去..

<1999>
假設一個root 有3個children, A,B,C;
# Combinations就是 (DFS(A)+1)*(DFS(B)+1)*(DFS(C)+1)了
要+1 是因為可以整個children (sub-tree)都不要, 只要current node自己
</1999>

試一點test case都過了, submit!

WA!!!!!! WHY!

原來...忘了處理value 一樣的問題...
就是仍會double count的意思...
例如
我以value為10的node A開始做DFS, 他其中一個child B也是value 10, DFS會一直走下去
這是第一次DFS

第二次DFS我用這個child B為root做DFS, 也一樣會數包括了A的sub-tree, 那些我已經數過了, 我只想數一些不包括A的sub-tree...

這樣解決了double count的問題, 也AC了...
時間複雜度是 n 次DFS就是O(n^2)
糾結的是problem tag是寫DP的...怎用DP做呀??

LL dfs(int c, int p, int root){
    if(a[c] > a[root] || (a[root]-a[c]) > d) return 0;
    if(a[c] == a[root] && v[c]) return 0; 
    //這就是處理double count的問題的一句
    LL ret = 1;
    FER(i,1,n) if(g[c][i] && i != p)
        ret = (ret * (1 + dfs(i,c,root)))%C;
    return ret;
}

 FER(i,1,n) {
        ans = (ans + dfs(i,-1,i))%C;
        v[i] = 1;
    }

E: (DP, Greedy)

好吧, 這條我思路是完全錯誤的, 我是看了editorial 也不想code這題的廢物
(因為它說要segment tree / BIT...)

幸好我去看人家紅字User的comment, 很多User也有一些純logic的做法, 

完全不用什麼特別的data structure啦...

先來看萬惡的題意:
LIS, 大家都知道, 而現在Given 一條sequence (長度 n <= 10^5)

把每一個數字歸類為:
1. 不屬於任何LIS

2. 屬於某些(但不全部)LIS
3. 屬於全部LIS

就是這樣...很邪惡

LIS加上這個數據量, 我自作聰明的就把思路轉去那個binary search O(n lg n)的

做法, 看看再加工會不會做到...

後來想得好複雜, 還真的code了出來, 還WA了 哈哈 = =

好吧, 我要承認, 如果不懂binary search 找LIS的做法也是做不到這題的

為此我還故意找我以前的post來回憶一下 =.=

以下為睇完某紅字User comment既解法, 

基本上code是很易的...

話說第一步就已經想不到了...
設A[i] 為 以 第 i個數字(一定要包括它) 為結尾的LIS 長度

設B[i] 為 以 第 i個數字(一定要包括它) 為開首的LIS 長度

Editorial的話, 就要用segment tree / BIT 數它們的總數之類..

紅字User的高明得多...
首先A[i] + B[i] - 1就是包括第 i 個數字的LIS

如果這個數字不等於整條sequence的LIS, 那麼第 i 個數字一定是屬於第 1類了

然後剩下的數字, 要分類為2或3

重點來了!  (紅字User曰) 若 A[i] 跟A[j] 是一樣的, 他們2個數字, 可以於任何LIS中互相取代
所以他們2個都一定都不是屬於所有LIS, 即類別 2

剩下的(就是A[i]是unique的) 就是類別3...

而以上所有步驟都可以用類似binary search找LIS的方法去實作...

所以基本上時間複雜度也是O(n lg n)...

實作上由於I/O的關係, 不能用STL:SET做, 要人肉binary search...很煩的說..

這些紅字User只能說

太聰明了, 太強大了!