Codeforces Round #285 (Div. 2)

終於開始追上完成了的題目了..
還差說好的Facebook Hacker Cup 2015 還有我又走了數的Rockethon@Codeforces...

話說這場#285, 雖然是Div 2...
可是題目難度不一樣...(是指C開始的題目)

C很快想到算法可惜在實作上碰釘碰死了
D到現在我還是覺得不可能現場即時做到的...除非那個人即時Google 看了Wiki 再秒速理解+實作那個Algorithm...
E的AC人數太可怕了, 我連題目也沒看...

那麼開始吧

Codeforces Round #285 (Div. 2)

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

A: (頹題)

就是代數入公式做一些比較之類的...

B: (String, STL)

String 與Map (背後思路也有DFS的份兒) 的基本應用實作...

C: (Graph, STL)

開始有趣的一題...

Given n (<= 2^16) 個node 的 degree 跟 XOR sum of its neighbors' ID

node的 ID 是由0 到n-1

求符合該條件的圖, print 出該圖的 edges (任意次序)

題目不算很直接的...倒也不算很難

首先 答案的圖不一定connected, 可能有node 是完全沒edge的也不奇怪 (雖然對算法沒影響)

然後很自然地就會注意到題目設定的 2^16 跟XOR sum..

完全指向bit operation嘛...

由於XOR的Associativity ( (A^B)^C = A^(B^C) ), 然後 A^A = 0 即 A^0 = A

所以它是可以"Reverse"的 (可以這樣說嗎..)

(A^B)^B = A^(B^B) = A^0 = A

那麼注意到, 我們已知題目內每一個node 的XOR sum  A1^A2^A3^...^A_n
假設我們肯定了它其中一個neighbor 是A3

那麼我把可以把  XOR sum 去走A3 的部分:

(A1^A2^A3^...^A_n) ^ A3 =  (A1^A2^A4^...^A_n)^(A3^A3) =  A1^A2^A4^...^A_n

如此類推 最後該node的XOR sum只剩一個A_i,  那麼A_i 就是它最後的neighbor

問題是怎樣找出它第一個neighbor呢?? 其實答案已經出來了, 只是要逆轉思維

我們把題目的Input 排好序, 以degree少的優先處理

degree = 0 就跳過吧, 根本沒有neighbor...

degree = 1 才是我們要的!

degree = 1就是說該node 只有一個neighbor, 那麼它的"XOR sum" 不就剛剛是它唯一的neighbor id嗎??

然後我們把它這一個neighbor的XOR sum 除去自己的id (用上面 xor 一次的方法)

同時把它的degree - 1

repeat 直至 所有node 的degree 都少於1就完成了

時間複雜度呢? 由於每個node只會選擇一次, 但是每次處理完一個node都要把update完degree的nodes 重新排序...也不可能每次都sort 一次吧??? 考慮上只剩下每次都自動以 O(lg N) 排好序的方法了.... 有點像Dijkstra Algorithm的影子呢

所以自然! 就是想起heap 這個神奇的data structure, 實作用的就是STL的 priority_queue了吧

老實說, 想到這個做法的時間還是很短的...實作起來才是痛苦的開始

應該是我太久沒用過STL的priority_queue吧, 我發現我是不懂實作customize 的 compare function的...google了一大輪, 無限試驗後, 才有一個像樣點的寫了出來

bool compare(int x, int y){
    return deg[x] > deg[y];
}

priority_queue<int, vector<int>, decltype(&compare)> w(&compare);

當然我印象中是絕對沒那麼複雜的...看了Gary神與Peter神的實作也沒那麼複雜, 這題真的感受到除了思路之外, coding的技巧還是太嫩了=.=

來學習神人Gary的寫法:

struct node{
 int id,deg,s;

 node(){}
 node(int id,int deg,int s):id(id),deg(deg),s(s){}

 bool operator<(const node &d)const{
  return deg > d.deg;
 }
} ss[100000];

priority_queue<node> q;

人家輕鬆寫個struct再override operator就行了, 寫反了的原因是STL priority_queue好像default是Max. Heap來的, 所以要人手把degree少的當成較高priority讓它們排在前

還有一件事也是煩了我很久的....可能我中了幻術, 

我總以為這個priority_queue是online auto sort的...也就是說每次裡面的element有update也會自動再sort一次...當然這是不可能的, 太理想了...

所以要完成上面的算法, 實際上是每次update degree後, 看看degree變成1了沒有, 

如果沒有就別管了, 完全不處理, 反正最後一定會有它的一個neighbor把它的degree降成1 的時候, 而那時候我們再push 一個新的degree 為1的node進去priority_queue (O(lg N)的時間)

就好了, 這樣說的話,實際上每個node就不止access一次了, 更可能是2次 (第1次發現degree還沒變成1, 可是又已經到了heap的頂了, 直接拿走; 直到我們再push它進heap底, 這時它必定是degree 1了)

總的來說還是O(N*lg(N))

D: (Math, Binary Indexed Tree)

我就直說了吧, 這題根本不可能做到的...要不是我即場做的時候有點眉目, 不甘心下跑去看Editorial, 根本不會發現這題所需要用的冷知識...

當然還是很感謝它的, 令我又再跑去學了Binary Indexed Tree (BIT)一次...

先來說說題目吧, 題目是很簡單易明的

Given length N 的permutation 兩個 p,q.

然後每個permutation 都有各自的Order, 代表它們lexicographical 的排名, 由0到N!-1

定義permutation的sum為  (Order(p) + Order(q))%N! 

找出排名為 sum 的permutation

這題的變態位在於 N <= 200,000    (O:*2036

先不說別的, 只是要執行 mod N! 這一步已經不知怎做了...

第一次做的時候我還是沒放棄的, 我姑且去解Order()這個function

這個還是勉強靠一些combinatorics 可以count出來的~

設p = (3,4,2,1,5)
我數的是有多少個permutation比它少對吧?
那麼第一個數字比3少的肯定要數了...(1,?,?,?,?) 跟 (2,?,?,?,?), 各自都是 4! 個可能性

然後即使第一個數是3, 也有可能第2個數比4少的, 注意比4少的卻不能是3, 因為3已經在第1個位, 那麼有(3,1,?,?,?) 跟(3,2,?,?,?) 各自都是3!可能性...

注意到了嗎??  其實比一個permutation少的permutations數目, 就是Editorial說的

    (應該是(k-1)! 才對?)

當中 d_k 是比第k 個數字少,而且還沒出現的數字的可能性, 換句話說,

是比第k個數字少, 又在第k個數字右面的數字 數目

然後乘上 (k-1)!  

我找了些N很少的permutation來算, 也是對的...算是可以開心吧

問題是...這個方法去找Order, 也是避免不了要算 N!  , 你媽啊...

我也有想過會不會 mod N! 有些我不懂的方法是不用直接算出N!的...

可是連Order()這個function也已經要用上N!了啊...

Peter神的指引下, 還是跑去看Editorial了...一看之下可真是嚇呆了

Factorial Number System

這個奇特的Number System竟然存在的啊...而且它跟permutation還有一種奇妙的關係...

而這條題目就是要利用那個關係啊啊啊啊啊啊.......

誰會懂這個非主流的東西啊....

好吧...我只能說這個Number System 我也沒看完, 但由於也是一個Number System,

還不算難理解的

正常的Number System, 例如十進制跟二進制

每個位數也是 10的次方, 或者2的次方,    第 i 個位 (0 <= i) 就是 coefficient 乘以 10^i  或者2^i
其它進制也是這樣

而Factorial Number System則把"次方" 改為 Factorial...

就是 第 i 個位 是coefficient 乘以 i ! .....  

然後談進位的問題,  十進制每個位置不能大於9,   二進制不能大於1...

又Factorial 進制則是 每個位置都不同,  第 i 個位不能大於 i 

舉個合法的例子  341010_!  = 3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0! = 463₁₀

十進制轉換Factorial進制就跟轉二進制差不多, 也是通過連續的除法取其餘數

詳情wiki 很清楚

好了, 要完成題目, 必需要用到的是Permutation那一節, 原來這個Number System跟Permutation有個神奇的關係, 就是它可以直接找出lexicographical = 該number 的permutation!

看例子最實際了: 4041000_! (equal to 2982₁₀) 

(0,1,2,3,4,5,6) 的第 2982 個 permutation 是什麼呢? 

Factorial 進制的每一個數字, 都代表 (0,1,2,3,4,5,6) 剩下未用的數字位置!
例如4, 就是第4 個數字 4,  然後我們把4 踢走:  (0,1,2,3,5,6),  答案: (4,?,?,?,?,?,?)
再來是0, 就是第0個數字0, 加入答案, 然後踢走: (1,2,3,5,6) 答案: (4,0,?,?,?,?,?)

再來是4, 就是第4個數字6, 加入答案, 然後踢走: (1,2,3,5) 答案: (4,0,6,?,?,?,?)

如此類推....

竟然可以這樣真直接找出來了....!

那麼是咁的, 把這個轉換逆轉,  就可以把一個 permutation 直接轉成 Order了 !(以Factorial Number的形式)

事實上, 不論由Permutation 換成Factorial Number還是掉轉,  也是要用到BIT的...詳情再說

假設我們成功獲得了Input p跟q的 Order了, 就是有兩個Factorial的數字了

如何算出它們的Sum???
加法是沒問題的...我要再強調, 它也算是一個Number System, 照樣理解的話, 

就可以linear地手動進位去算加法了

問題是 modular N! ....

首先要發現, 兩個數加起來, 肯定不會超過2N! , 就如十進制的 9+9 也不會比20大吧..

對了...十進制的十, 就等於 Factorial 進制的N!, 這樣理解很好

所以modular N! 跟減N! 在這裡是一樣的..

然後! 事實上由於N! 不可能以 N 個位數表示的, 想一想就知道了, 剛好要進位的嘛!!

所以N! 根本就一定是  10000....000 的形式存在啊! (跟二進制的 2^x 一樣, 10,100,1000000...)

所以....modular N!  = 減N! = 其實就是兩個Order加起來 ignore 第N 個位就好了....

這是何其聰明的做法啊...

最後把這個SUM 再換成permutation就好了...

太淫賤了, 正常人根本不可能懂的嘛...

我們最後來看一下最重要的部分: 

1. Permutation --> Order (Factorial Ssytem)
2. Order (Factorial Ssytem) --> Permutation

首先要先溫習一下BIT....

以我最新的理解...BIT跟Segment Tree最大不同之處, 是簡單易code

同時也很多限制, 好像只能作一些 accumulative sum的工作 (借此可以達成 range add x 的效果)

例如Permutation 換成Order, 其實我們每看一個數字時, 我們要知道比它少的數字已經出現了多少次 (踢走了多少個)
用同一個例子 (4,0,6,2,1,3,5):
看4時,  我們把BIT[4..N] 都加上 -1, 看0時也把 BIT[0..N]加上-1

看6時, 我們其實Query了 BIT[6], 發現是-2了, 所以我們實際儲存6-2 = 4, 當然也要BIT[6..N] 加上-1  如此類推

int sum(int x){
    int ret = 0;
    for(x;x; x-=x&-x) ret += bit[x]; // 找出[0, X] 的accumulative sum
    return ret;
}

void update(int v, int x){
    for(x;x<=n; x+= x&-x) bit[x] += v; // 把包含 x 在內的樹加上v
}

void toFac(int *arr){
    memset(bit,0,sizeof(bit));
    for(int i=1; i<=n;i++){
        int tmp = arr[i]  + sum(arr[i]+1);  // eg: 位置6 加上 [0,6]的accumulative sum(-2)  = 4
        update(-1, arr[i]+1);  // 不忘update, 把現今位置及包含現今位置的樹加上-1
        arr[i] = tmp;
    }
}

最後了, 把Order 算出Permutation來

這個反而有點tricky, 是要用上Binary Search 加BIT的

思路是找出第一個 位置+BIT[]  = Search Value 的位置

要強調第一個是因為可能有多個出現, 例如

( 0, 1,  2, 3,  4, 5, 6)

(-1,-1,-1,-2,-2,-2,-2)

如果我們要找 "1"的話 (現今Factorial Number的數字)

(2-1) 跟(3-2)都是 1, 我們要取2還是3?
答案是肯定取最前的,  因為後面那個(那些) 會減至跟前面一樣只有一個可能性: 它們已經先被取掉了, 然後update了, 所以才會減那麼多次變成跟前面那些一樣

但由於它們不論怎樣減, 也不會被前面位置+BIT少, 就是說  (位置+BIT) 是長期處於Sorted狀態

所以才能用Binary Search
老實說, 在看了wiki之後, 獲得算法之後, 這部分算是最難搞的 (腦內清楚卻很難表達...)

這題的感受是...什麼Factorial Number System, 不打算詳細記下...倒是BIT的用法跟實作

可能要找個時間做一下啊...可能是個很強大又性價比高的武器