2015年3月12日 星期四

Codeforces Round #290 (Div. 2)

又一場在公司Virtual Participate 的round
可能題目較易, 這次也較少同事的打擾
成績也算不錯







第5題看了Editorial後 了解是Flow的題目
Flow在計劃中還沒打算詳細學習 所以就沒深究了
也就是說這場4題都是即場AC的 算是很有運氣的一場


Codeforces Round #290 (Div. 2)


A: (頹題)

就考你寫 for loop的題目...

B: (Graph)

在很小的圖內找有沒有長度 >= 4 的cycle, 就暴力的用DFS

C: (String, Graph, Topological Sort)

這題有點有趣...不過也是很直觀的Topological Sort就是了

給了 n 條string, 它說明了"這些String是按lexicographical order"來排列的
這當然是指 a<b<c.... <z 了,  但題目也說了情況有點改變,  字母的rank並不是原本的rank
而是另一個新的食物鏈, 例如  e<d<a<z<x<g<h... 而input的lexicographical order是以這個新的rank來說的

現在求一個permutation of  [a-z]  such that 按這個permutation來比較字母大小
input的string 的而且確是順序排列的, 如果沒有答案則print impossible, 否則隨便print 一個合理答案就ok

由於 n 很小, 建圖不會像上一場那麼有難度了...直接考慮建圖後要做的事
這個有向圖求序, 根本是裸跑的Topological Sort, 有cycle 就是沒答案了

建圖比較有伏, 所以說一下:
我們用O(n^2) 來比較pair-wise strings, 找出它們第一個不同的字母, 這2個字母之間就可以加一條edge了
問題是要是完全沒不同呢?  那麼就直接看長度, 要是較短的排更前就對了, 不然就直接print impossible

這樣建了一個有向圖後, 就做Topological Sort吧
好吧,...我承認我出Cheat, 我抄演算法筆記的寫法, 我不害羞, 反正一棍過就好
好吧 其實也不難理解, 也就是一個DFS, 用post-order 記錄 ordering,  跟上一場Euler-Path的道理也是一樣的...post-order時機的確很有用

D: (DP, Math, STL)

最後也最有成功感...也最有運氣的一題
我是用數學的方法做的  事後發現題解是用DP?
這題的靈感也來自於Facebook Hacker Cup 2015 Round 1的Problem D

題目給了 n 張card ( n <= 300)
每張card有自己的費用c 跟 距離 l 
買了一張卡之後, 便可無限次使用, 功能是向前/向後跳 l 格  (由x 變成 (x+l) 或 (x-l))
你現在在第0格, 問如何用最少的費用, 令你能去"所有"的格子
如果不可能則print -1


老實說我是不知官方如何DP的,  我跟很多參賽者也是更低級的DP手法過的
而且題目是說要用某幾張卡鋪滿整條NUMBER LINE
就是無限的距離, 所以更像數學題的feel

我最初想到的是只要我有兩張卡, 它們的difference是1 那就一定行了
然後進一步發現, 好像是只要有兩張卡, 它們的GCD 是1 也可以的說

GCD啊...互質...我直接就去wiki找 Extended Euclidean 了, 但好像沒什麼關係.. (這個Extended什麼的學了這麼多年都不懂, 太神奇了)

然後我轉個角度想其它東西, 如果是多過2個數字的情況怎辦呢?
2個數字可以是因為 GCD(x,y) = 1 iff   ax + by = 1 for some integer a,b
但如果多過2張卡的情況 我是想要

a_0 x  + a_1 y + ... a_n  z = 1

而我所知的只有 x,y...z ,     我當然希望有這麼一個定律
gcd(x,y,...z ) = 1  iff a_0 x  + a_1 y + ... a_n  z = 1
但印象中沒學過這樣的東西?  
運氣這兒就派上用場了, 我在紙上想了幾個case, 剛好都好像match這個rule
我就猜想是這樣了, 就這樣做下去吧, 那兒來的膽啊...

要是這樣, 問題就要改寫一下了, 改寫成數學一點的形式吧
given set {a,b,c....}  求 non-empty subset X such that GCD(x0, x1...) = 1, 而且是最平的

這兒說一下, 每個數字(就是原題目中的距離) 可以是 10^9 那麼大

那麼....可以怎麼做呢?
這時Facebook Hacker Cup的慘痛經驗又派上用場了
我再猜想不論怎樣, 不同的GCD數量很少
(還記得FB Cup 那題的Color其實也很少嗎...凸)

要是這樣的話就好辦了, 用DP!
設DP(g) := 任意set 的gcd 為g , 最低的cost

DP的方法嘛...很抱歉的說, 我不能很好地寫出來
我當時是邊code邊想 也覺得很對就做完了  發現跟普通的DP有點不同 很難把transition好好的寫出來

總之思路就是用STL的set 儲下所有gcd (因為我猜想數量不多)
然後iterate 所有卡, 每張卡都去改動這個set, loop這個set 同時update DP state
  st.insert(a[0]); mp[a[0]] = c[0];
    for(int i=1; i<n;i++){
        if(mp[a[i]]<= 0 || mp[a[i]] > c[i]) mp[a[i]] = c[i];
        for(set<int>::iterator it = st.begin(); it!=st.end(); it++){
            int x = *it, g = gcd(x, a[i]);
            st.insert(g);
            if(mp[g] <= 0 || mp[g] > mp[x]+c[i]) mp[g] = mp[x]+c[i];
        }
        st.insert(a[i]);
    }

也就是每次有一張新卡, 我都做以下的事:
  1. 跟暫時所有得到的gcd 跟它都算一下gcd, 並且把新算出來的gcd 加進set內
  2. 跟暫時所有得到的gcd 跟它算一下gcd g, 然後看要不要update DP(g)
  3. 就直接一張卡自己去看能不能update DP(), 還有把它自己加進set內    這主要是應付有一張卡本身已經是 1 的情況
實作如上面貼的, 用了STL的Map 做DP的容器, 用Set 儲下gcd....
很亂來吧

時間我不懂分析, 因為大部分都是猜想的, 我也沒想到過了...(雖然很勉強)

那麼當然就要看Editorial跟Comment了

首先,,,猜想1...有神人果然貼了這條rule
Bézout's identity (看Generalization 的部分)

For three or more integers

Bézout's identity can be extended to more than two integers: if
\gcd(a_1, a_2, \ldots, a_n) = d
then there are integers x_1, x_2, \ldots, x_n
such that
d = a_1 x_1 + a_2 x_2 + \cdots + a_n x_n,
has the following properties:
  1. d is smallest positive integer of this form
  2. every number of this form is a multiple of d
  3. d is a greatest common divisor of a1, ..., an, meaning that every common divisor of a1, ..., an divides d
所以基本就是說 [a-z]的gcd 是 1 的話, 就會有它們的multiple的sum = 1 ....好可怕

至於猜想2 就要看這兒

In fact, 735134400 has 1344 divisors, so a safe guess would be 1500.
看吧!! 人家都是Guess來的...只是有很好的理由  他們總是有很好的理由去guess一點很重要的hint


至於官方解法...我也沒深究了, 因為被大部分User屌到上天花板, 說"不用那麼複雜啦" , "就暴試所有gcd啊" 之類的

張貼者： 於
標籤： , , , , , ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)