Codeforces Education Round 1

經過N個月, 公司的Project 終於見到尾聲...趁住扮工時間的空閑, 隨便找了一下CF的比賽來玩

很久之前看到CF推出的Education Round 系列已經感到興趣, 決定玩下 Round 1

看名字覺得是for 新手學習用, 所以很想玩, 但竟然...此Round 無Editorial...

究竟無Editorial 點樣可以Educate到人呢 ?

Anyway 這場有A-F共6題, 難度我覺得也是D2至D1尾吧? 最後AC了5題, 最後一題有點想法但Code不出來

要說學習了什麼, 倒不如說溫故知新, 特別是問了Peter神及GG 一些埋藏多年的白痴問題

Codeforces Education Round 1

題目: http://www.codeforces.com/contest/598/problems

A: (Math)

題目就不詳說了。
數據很小, 題目也很直觀, 基本有bitwise operation的底子可以直接code出來。
要是沒有的話其實暴試, repeat squaring之類的 怎樣也能AC。

B: (String, Ad-hoc, STL)

這題是Given 一條 string S, 然後 有一堆range query [l_i, r_i] 及T , 代表在這個range (inclusive) 內的substring 要向右rotate (shift ) T 次.

老實說這條應該是想最久的吧...因為比題目結構嚇倒了, 直接想到什麼range query什麼segment tree都出來了。

結果第二天扮工時間再看題目, 發現數據根本很小, 直接暴力做就可以了...

當然T 可以很大, 但由於 rotate 多過range的長度等於重置一次, 直接T%L (L = r_i - l_i + 1) 就好了。

我是用最慢但應該最易看的白痴寫法: C++的 STL, substr() 了很多次, 左拆右拆的, 一樣能AC。

只是看了Peter神跟 Gary神的 Code, 他們都不需要用C++的東西, 有點慚愧...

D: (Graph: DFS)

容我先跳過C, 因為題C數據上是最少人AC的, 我也最後才做, 也是相對學習得較多的一題。

題目很有趣, Given 一個2D Grid,  每格可以是路, 可以是牆。 如果是牆的話上面會有名畫一張。 然後Given m 個起始位置, 問如果你由該位置開始一直行, 怎樣行都可以 (除了穿牆), 你總共能看到多少名畫。

這樣想吧, 其實連續起來的路是一個component, Grid入面就有數個disjoint 既 components, 每個component入面不論那點作為開始, 看到的數量也是一樣的。

每個component 就像是圍棋內的一塊棋, 他們的「氣」就是名畫的數量

扯遠了...其實沒什麼關係XD

所以做法很簡單, 直接DFS, 把每個位置都歸入某個component內, 順便計算該component能看到的名畫數量。如果某點已經知道屬於那個component, 那便不用再花時間DFS了, 直接output 答案便可。 每個格子能看到的名畫數量可以在DFS前先計算好。

思路不難想, 算是鬥快寫DFS吧?

AC Code: http://www.codeforces.com/contest/598/submission/18879479

E: (DP)

這題老實說, 對我來講算是開始有難度了...雖然我知還是很簡單的題目。

題目是這樣的:  有朱古力一條, 有N*M 格,  現在你可以拆斷它, 但一定要直線或橫線, 整數地拆。每拆一次 cost 為該線的square, 問如果你想要exactly k 格朱古力, 最少cost 的拆法要多少

這類題目我有陰影, 總是想起從前有條POJ 好像叫Stick的題目, 當年覺得完全沒有思路, 不可能做得出, 然後Leo好像淡淡說了句: 呢條唔係Search ja咩? 

自那時起我都以為Search是一類特別的題目Category...
其實到現在也不太清楚他講乜春, 但這條的確是Searching, 雖然實作上是用DP做啦 (可以這樣說吧?)

數據很小, 其實也明顯是要你直接用DP做的了, 數據小到DP的方法也很直接

DP(N, M, K) :=  Minimum Cost to get K chocolates out of N*M one

DP(N, M, K)  = Min ( DP(N_1, M, K_1) + DP(N_2, M, K_2) + M*M,   DP(N, M_1, K_1) + DP(N, M_2, K_2) + N*N) for all N_1+N_2 = N, M_1+M_2 = M, K_1+K_2 = K

說白了, 就是每條邊, 和K的每種可能性 (K=4的話, 左邊0粒, 右邊4粒 / 左邊1粒, 右邊3粒...)都試掉, 看那種最優。

Code是不難寫的, base case小心點處理就好了。我是用Top-Down的寫法, Peter 神是用Bottom-Up的, 分別也不太大。

唯一WA了一棍...是被白痴位陰掉了...他有很大量的Query數目...但其實DP State pre-compute一次就行了, 第一棍把DP 放進 Input Query 的loop 裡了, 吃了TLE。

要說這條的學習, 我總是在想要是數據再大一點, 不能直接DP時, 會不會有其它做法, 這個還未有答案。

另外就是我對於分析這種Recursion + Memorization 的Complexity 很弱, 完全不知怎樣分析, master theorem好像也不能apply, 當然靠經驗感覺我知道肯定不會TLE, 但從來不知道正確及General的分析方法, 究竟是Big-O of 什麼。

有關這個, 我在Stack Overflow上問了一下, 好像也沒什麼特別的答案
http://stackoverflow.com/questions/38215549/how-to-analysis-the-time-complexity-of-this-code/38240874?noredirect=1#comment63937690_38240874

倒是Peter神的想法是把DP state的tree 做一次DFS, 所以是O(|V|+|E|), 然後看題目決定|V|和|E|是什麼, 這個想法當然好, 但我不肯定是不是General所有DP 的solution都可以這樣想, anyway仿然要#Adore#一下

C: (Geom)

最後解到的這題, 只有63個人AC了的這題, 其實不難理解。

題目本身不算難...但是一碰到Geom, 就一定會弄到精度問題, WA也不為過 

我沒有為自己WA了 13棍而開脫。

好吧先說題目 :)

題目是Given 10^5 個 vector, 全部連住Origin的。問那兩支vector的角是最小的, 這裡說的角沒有方向, 總之是該兩支vector的+角或-角magnitude 最小的 就ok。可以print出任何答案。

話說這樣的數據量, 基本上是要O( N lg(N) )的了, 看完題目基本就是Sort by Angle了吧

印象中Sort by Angle有兩種方法做, 但我只記得一種: 用atan2() 來sort.

當然n年沒有code過 geom題目的我, 一定要google atan2的用法...那些就不說了 :(

題解就是sort 完, 然後每一支vector跟前一支 (或後一支) 計一下角度, 然後找最minimum 那一pair 就好了 (最minimum 那一pair 在sort 完後一定是相鄰的, 對吧?) 

小心最後一支也要跟第一支比較。

問題來了, 一直WA一直WA, 完全不知錯在那裡。看完TEST CASE更加相信是精度問題...

所以這題的99%難度在精度問題。 以往我只知道要用eps, 但怎樣用, 為何要這樣用我也忘光了。所以我發射飛彈, 試了eps 由  e-6 開始到e-18 都試過了, 全部都WA....

終於最後, 忍不住, 隨手打開第一名那個的Code看...根本與我沒分別...唯一的分別, 在於他是用long double, 我是用double!!!!

我改完之後, 果然AC了.....!

究竟何時要用long double, 何時要用double? 我也不知道, 這是一個謎...

另外之後我問了GG, 究竟何時要用eps,  現在有一個更好的concept了....

原來eps的原意是比較2個double variable是否一樣, 而當你想 differentiate 它們的時候, 就要用上eps 來比較 ( <= 或 >= ). 在這題中用不上, 因為我們只考慮角度, 有些題目可能也要考慮長度, 那麼可能就有分別了 (sort by 角度, 角度一樣不等於"一樣")

而eps 通常是set e-8, 是-8,  至於為什麼, 連GG也說不知道 =.=


F: (Geom?)(最後一題的思路有時間後補吧...)

回到家打果然比在公司偷偷打要好得多。

這題的題目光用看的也感受到變態程度, 直到現在更只有 2個人AC...

題目大意是Given 一個 N-Side polygon, 可以Concave, Input格式為N 點, 點可以同線。
然後Given 一堆query, 每個query 是一條線, (可能) intercept with this polygon.
問, 在這條線在polygon 內的總長度是多少?

好吧我的確沒什麼完整的思路, 但腦海中立即出現的是當年CSC326 學的 Ray-Casting Algorithm (好像是叫這名字?)

好像是Given一點, 向住某一條線"射"出去, 看看穿過多少條polygon的邊。按照單雙數, 可以得知該點是否在Polygon內。

或許當中有某些思路可以apply? 沒什麼方向。 結論是為何Education Round沒有Editorial??

---

PS (Bonus)

雖然很慢, 但有感覺自己一直在進步, 可能一些以前沒有學懂的現在都會主動去學而且大約都能學會。但實在是不夠時間用, 在教會也開始要幫忙作鼓手跟導師, 工作上也愈來愈忙 (雖然快將轉工了應該), 加上要做Gym還有一大堆聚會要去, 有種感覺是一天24小時真的太少了....

另外之前在FB 路過看到一條好像是數學Olympic的題目, 對於0數學底的我, 也有些想法, 跟Peter神討論了一下, 可惜還是沒有答案~

以下是完全沒有數學底子 我的想法, 正確答案在Facebook 這幅圖的top comment已經有了 (按照那個like的數目來看)  好像是用一些我看不明白的number theory 的argument

所以這兒的想法只是自己的FF

首先證明 y = x^3 + 37 (mod 3)

By Fermat's Little's Theorem, y^2 = 1 (mod 3), So L.H.S. = y^2 ... y^2 * y (mod 3) =  y (mod 3)
R.H.S. = x^3 + 37 (mod 3),  So  y = x^3 + 37 (mod 3), Q.E.D.

然後下面是一些完全9 up 的東西, 是關於Chinese Remainder Theorem的。
從 Wiki 可以看到,

Suppose n₁, ..., n_k are positive integers that are pairwise coprime. Then, for any given sequence of integers a₁, ..., a_k, there exists an integer x solving the following system of simultaneous congruences.

這兒我重點關注 any sequence of integers a_i 這句。
我想, 這是不是等同說明

Given y = x^3 + 37 (mod 3)
There Exist some a' = x^3 + 37 (mod 5)  such that 
 y = a' (mod 5) 

因為 3 跟 5是co-prime嘛, 然後x^3 + 37 也肯定是integer for any x
同理 其它 prime number 也跟 3 是 co-prime, 所以 y = x^3 + 37 (mod p) 

然後L.H.S 跟R.H.S. 一同自乘 37次 就行了...


但這只是我的狂想, 因為我根本不了解Chinese Remainder Theorem, 特別是我覺得以上的argument 有違

A solution x exists if and only if

${\displaystyle a_{i}\equiv a_{j}{\pmod {\gcd(n_{i},n_{j})}},}$

所以也就沒再深究下去了。(後註: 後來想下去果然還是錯得很離譜XD)

Google Code Jam 2015 Round 1A

就結果來說...沒有參加實在太可惜了...參加了應該就ADVANCE了...

希望1B跟C不要比這場難就好了..

話說這場的時間是星期六的早上9時, 這星期實在太辛苦了..星期六真的要睡很久就沒參加了

事後在Practice看看水平如何...

A是很簡單的一題, B要想一會兒..我覺得B在於我來說有點運氣成分, 就是不一定每次都可以想到

C直接果斷只做了C-small...C-large有空再想吧, 應該很tricky?

現場來說, 只要做到A,BC-small, 基本就1000名內 = 升級了...

Google Code Jam 2015 Round 1A

題目: https://code.google.com/codejam/contest/4224486/dashboard#s=p0

A: (Math, Greedy)

一題直接的數學題...數據也不大, 能過小的基本也能過大的...

就是給了兩個方案, 各自Greedy地計算一個數字, 然後輸出就是了

唯一令我confuse了一會的是那個"rate", 我第一眼以為是以秒算的, 那麼不能整除的話

就要 ceil 了, 但從test case來看, 這個"rate"是每10秒計的...其實也很合理

#include<bits/stdc++.h>
using namespace std;

int T,t1,t2,n,a[1005],r;

int main(){
    scanf("%d", &T);
    for(int qwe=1; qwe <= T;qwe++){
        scanf("%d", &n);
        t1=t2=r=0;
        for(int i=0; i<n;i++) {
            scanf("%d", &a[i]);
            if(i) {
                r = max(r, a[i-1]-a[i]);
                if(a[i-1] > a[i]) t1 += a[i-1]-a[i];
            }
        }
        r = max(r,0);
        for(int i=0; i<n-1;i++) t2 += min(a[i], r);

        printf("Case #%d: %d %d\n", qwe,t1,t2);

    }
    return 0;
}

B: (Binary Search, Math)

這題能腦子一閃想到也算是運氣, 意思是Round 1B或C有這類題目, 我未必能想到

我直接就看大數據來想的, 但要是真的做不到large case, 應該small case有一些簡單暴試的方法

題目給了 B個髮型師 (|B| <= 1000), 每個髮型師要M_i (M_i <= 10^5) 的時間理髮

你是第N位客人 (N<= 10^9), 每一個客人會等到有任意有空的髮型師就找他理髮, 要是有數個有空的就找 ID 最小的髮型師, 問會是那一個髮型師為你理髮呢?

始且順住我的思路盡力寫下:
首先由於 N 太大, (這個N 是small / large case 都一樣的)

連 O(N)都過不了, 所以我估了數個可能的複雜度: O(B lg (N)) , O(B lg( max(M_i))) ...
於是思路就是以 |B| 為重點來開始想

"For 每一個B 做些什麼" 這樣子...好像也沒什麼想法

於是在紙上 visualize test case: 是這樣子的

這是第一個test case, 由於N = 4, 所以答案就是 B = 1

類似這樣的畫法, 另外2個test case也都畫出來了

一些 M_i 不能整除的也都亂畫了幾個

然後靈光一閃的位置到了...

我就這樣打直畫了一筆

然後開始想...這個是代表時間吧

在任意時間, 總共處理 (正在處理中的都算) 了多少位客人?

這個好像能知道的樣子

加上之前估算的複雜度, 一個字: Binary Search

然後開始細想:  最大的時間是多少? 直接想最惡劣的情形(對客人來說): 只有1個髮型師, 他還要用最久的時間處理一個人,  這樣最大的時間就是 10^9 * 10^5 = 10^14!

O(lg (10^14)) 足夠有餘!

而每一個時間, 怎樣算有多少客人已經處理?

設時間是 t ,  由於我們正在處理中的都算, 所以是 Ceil( t / m_i) 

總數就是 Sum (Ceil (t / m_i) ) , 這個可以用O(|B|) 算出

我們要找的是: 最少的時間令這個Sum >= N

這樣, O(B lg (N*max(M_i))) 感覺很像樣了

問題是, 現在我們有一個時間點了 (這個時間作為第N個客人, 你會被處理)

怎樣找出答案要求的髮型師 ID呢?

我的想法是: 把這個時間點再減 1 , 然後再算一下Sum (總共多少位客人在處理)

然後有以下的推論:

這個前一秒的Sum 肯定比我們以Binary Search找的小, 不然我們Binary Search 那一步就錯了 (contradiction)

那麼這一秒可以使Sum增加的原因是, 某些髮型師在這"前一秒"剛好完成手頭上的工作, 空出來了

把這2個Sum 的difference叫offset, 我們要找的髮型師就是 第 offset 個 剛好完成工作空出來的髮型師, 這些髮型師的特點是 : 他們的理髮時間 M_i 能夠整除我們Binary Search的時間-1秒

所以找第offset 個髮型師 (就是答案) 這一步還是可以O(|B|)找的...

算法也完成了

這題還是很有信心的...因為每一步都真的想得很通, 也很說服到自己再code的...

能一棍過太好了, 就是不知現場發揮有沒有這麼好= =

下面用%I64d 是因為我在Codeforces隨便submit再copy的, 我不會其它方法使code那麼好看了(排版上)

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int T;
LL b,n,m[1005];
int main(){
    scanf("%d", &T);
    for(int qwe=1;qwe<=T;qwe++){
        scanf("%I64d%I64d", &b, &n);
        for(int i=0; i<b;i++) scanf("%I64d", &m[i]);

        LL lo = 0, hi = 100000000000005LL, mi, M;
        while(lo <= hi){
            mi = lo + (hi-lo)/2;
            LL sum = 0;
            for(int i=0; i<b;i++){
                sum += (LL)ceil(mi*1.0/m[i]);
            }

            if(sum >= n){ hi = mi-1; M = mi; }
            else lo = mi+1;
        }
        LL psum = 0;
        vector<int> idList;
        for(int i=0; i<b;i++){
            psum += (LL)ceil((M-1)*1.0/m[i]);
            if((M-1)%m[i] == 0) idList.push_back(i+1);
        }
        LL offset = n - psum;
        printf("Case #%d: %d\n", qwe, idList[offset-1]);
    }
    return 0;
}

C-Small: (Brute Force, Geometry)

就 Small來說, 的確比B簡單...

Large還沒想所以就不講了 (想到的話再講吧..= =)

題目是問, 給了 N 點, 求N 個數字, 第 i 個數字代表 最少要刪除多少點才能使第 i 點在convex hull 上面

Small Case 沒什麼好說的, 因為 N<=15, 直接地說是怎樣做都可以, 夠暴力就OK了

我的做法是最直接的 O(2^N  * N) 

實作時不想煩好像寫了 O(2^N * N^2) 的, 反正都能過就沒多想了..

Convex Hull 我用我唯一會的寫法: Monotone Chain

(有出cheat 參考網上寫法)

算法就是 bitwise地決定刪走那些點, 把剩下的點做一次Convex Hull, 

看看第 i 點在不在 hull 裡面...就這樣子

Convex Hull 是O(N)的, 因為sort 那一步可以放在 bitwise brute force外面

這題很好...順路幫助我記回基本的Convex Hull寫法

明天再來看看有沒有精力想 Large吧...

#include<bits/stdc++.h>
#define LL long long
using namespace std;

struct P{
    LL x,y;
    P(LL x, LL y): x(x), y(y){}
    P(){}
    P operator-(P a){
        return P(x-a.x, y-a.y);
    }
    double operator^(P a){
        return x*a.y - y*a.x;
    }
    void eat(){scanf("%I64d%I64d", &x, &y);}
}tree[20],control[20];

int T,n;
vector<P> hull;

bool ss(P a, P b){
    return (a.x < b.x) || (a.x==b.x && a.y < b.y);
}

double ccw(P o, P a, P b){
    return (a-o)^(b-o);
}

bool convexHull(int x, int s){
    vector<P> src;
    hull.clear();

    int m = 0;
    for(int i=0; i<n;i++)
        if(x & (1<<i)) src.push_back(tree[i]);

    for(int i=0; i<src.size(); i++){
        while(m >= 2 && ccw(hull[m-2], hull[m-1], src[i]) < 0){ hull.pop_back(); m--;}
        hull.push_back(src[i]); m++;
    }
    for(int i=src.size()-2, t=m+1; i>=0; i--){
        while(m >= t && ccw(hull[m-2], hull[m-1], src[i]) < 0){hull.pop_back(); m--;}
        hull.push_back(src[i]); m++;
    }

    for(int i=0; i<hull.size(); i++)
        if(hull[i].x == control[s].x && hull[i].y == control[s].y) return true;

    return false;

}

int main(){
    scanf("%d", &T);
    for(int qwe=1; qwe<=T;qwe++){
        scanf("%d", &n);
        for(int i=0; i<n;i++){ tree[i].eat(); control[i] = P(tree[i].x, tree[i].y);}
        sort(tree, tree+n, ss);
        printf("Case #%d:\n", qwe);
        if(n<=2){
            for(int i=0; i<n;i++) printf("0\n");
        }
        else{
            for(int s=0; s<n;s++){
                int ans = 1<<28;
                for(int i=0; i< (1<<n); i++){
                    if(i&(1<<s)==0) continue;
                    if(convexHull(i, s)){
                        int tmp=0;
                        for(int j=0; j<n; j++) tmp += !(i&(1<<j));
                        ans = min(ans, tmp);
                    }
                }
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}

C-Large: (Geometry)

糾纏了幾日, 終於完成了這題

果然是C-Large, 基本上要是即場做的話還是會果斷放棄
算法倒也不算複雜, 但重溫/新學了一些做Geom的技巧 

思路是這樣的...還是先從數據量估算複雜度開始

O(n^2) 是絕對可行的, 但不太可能以n^2 完成...

然後發現O(n^2 lg(n)) 也非常足夠

把這個複雜度Bare in mind, 再想想實際上如何入手

最直接想到的是, 一點要成為convex hull上的一點, 以它跟左右兩個hull點連起來

這一點 "另外一邊"的所有點都要刪去

推而廣之, 一點跟任何另外一點連成一線, 以這條線為分界線

刪除線隨便一邊的點, 另一邊+線上的點就可以成為hull

這樣的話 把全部2點都連起來作分界線試一下, 每條線有2個可能性 (刪去隨便一面的點)

這步至少要O(n^2)

剩下的 O(lg n)...我懂的也只有Binary Search了

說起來, 這種情況下bsearch能起作用的:

假設我們有方法把點排序,  然後用bsearch找出一個連續的範圍, 裡面的點是都要刪去的

這樣的話問題就解決了...

high level 地說:

1. for 每一點 i ,  O(n)
1. 用某種次序把點排序 O(n lg n)
2. for 另一個點 j , i != j  O(n)
1. bsearch 要刪去的點的range O(lg n)
2. 比較2種可能性那種較好 O(1)

總算起來就是O(n^2 lg n)了..

問題是怎樣排序了, 點排序的話不是先x 後y,  就是sort by angle吧..以我認識來說=.=

這題是sort by angle! 可是我沒code過, 也不太了解實作上怎樣做

也不能直接用cross product去排序, 因為 >= 180度的有負數 / 0, 根本sort不了

經Peter神提點, 原來大家都是用atan2()這個function來算角度再sort的...

所以所謂sort by angle (以某點為origin)  就是先O(n) 用atan2() 算一下角度

如果是負數的話要加 2*PI  把角度變回正數, 這樣atan2()的range是 [0, 2*PI)

Sort完後再來想是不是能利用來bsearch了

假設現在是用點 i 作origin, 我們要找最少要刪多少點才能使 點 i 在hull上
那麼 點i 連到點 j 的線, 角度是 angle (j)

但還有另一邊, 另一邊的角度是 angle(j) - PI, 如果是負數的話也一樣加上2*PI

現在有2個角度, 我們分一下大小,  所以我們有了一個range, 這個range 剛好是 PI 度 (一條直線)
我們可以bsearch 在這個range內的點,  要小心的是不包括在線上的點

假設我們bsearch了在這個range內的點是  s, 我們就可以比較2種可能性了:
把這s 個點刪去,  代表 剩下的點作一個hull (點 i 是origin, 肯定在線上=hull上)

或是把 n - s - 線上的點 刪去, 代表用這s點和線上的點作hull (點 i 是origin, 肯定在線上=hull上)

這樣以點 i 作origin, 把所有點 j 的2種可能性都比較完就能知點答案

for 每一個點\i 都這樣做 就好了

然後當然還是WA了, 搞了很久還是不知道為什麼
終於發現原來是精度問題, 太久沒做連精度問題都忘了怎樣處理

找了small case的一個test case試, 發現 在1e-7的位置會出現問題

所以先設eps 為 1e-7, 然後sorting 和bsearch時 (總之要比較2個double的時候)
便要考慮eps:

feq(x,y)  :=  fabs((x)-(y)) <= eps
flt (x,y) :=  ((x)+eps) < (y)

fle(x,y) := ((x)+eps) <= (y)

我大約記得是這樣吧, 也不太肯定, 總之這樣之後就AC了...

然後實作上首先是:
bsearch是如果是用內置的lower_bound / upper_bound

跟sort 一樣, 可以自己寫個bool 的 comp function, 我這次也寫了一個, 裡面就是用上面的flt / feq 等去比較

另外聽GG說好像有不用double的sort法, 就沒有精度問題

方向大概是是找出180度的點. 以它為pivot 把點分成 < 180度和 > 180度

然後2種點內各自用cross product sort
感覺像是 quick sort 那種先fix 死一個pivot 再分2邊處理那樣

可以學習一下

後記:  MS 那邊那個比賽這兩天也進行了 Round 1A / B, 打得很差, 但還是有一題值得記下的, 其實問題很有學習價值, 但平台太差, 沒有practice, 也不能賽後submit, 也沒有solution / editorial....真的很令人生氣, 看看把那唯一值得記下(AC)了的一題怎樣歸類在另外開文寫吧..

Codeforces Round #291 (Div. 2)

這場可真是我近來最想最想記下的一場, 記完這一場後真的要寫說好的Trie跟String Matching的Algorithm了...但在此之前  這場5題都做了
而且學到更多以前聽過卻沒學過的實用技巧!

Codeforces Round #291 (Div. 2)

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

A: (頹題, Greedy)

又一題改digit 令數字變成什麼什麼的題目...我又再重覆上一場的句子: 通常都是Greedy就行了..

B: (Math, Geometry)

略有一點難度的數學題, 問最少要多少條線才能把所有目標都擊破

也不用特別的技巧或用上大家比賽常用的Geom的Class, 只要計Slope, 一樣Slope 的就Lie on 同一條線了...

C: (String, Hashing)

第一題要詳細記下的題目!

這題跟之後會寫的String Searching不無關係!

先來說題意吧:  Given n 條pattern, 和m 條 string (每一條是一個獨立query),  所有string 只會由[a-c] 組成

問是否有任意一個pattern跟 string 只差exactly 一個字母相異?

在學了Trie的基本之後的我, 直接想到的也是用Trie 去解, 事實上看comment也有人說能用

prefix tree (即是Trie)去解...但當時我沒很直接想到怎樣做

String的處理我一向都很弱 (說真的也沒什麼特別強=.=)

我只想到 每個query 可以試住做以下的事:

1. 每個位試試改成其它的2個字母   eg: 原本是'a'的話試試改成'b'或者'c', 每個位都這樣做
2. 跟每個pattern比較一下看是否一樣

這題的時間我也很難分析, 因為它是直接說"所有input 的總長度 L<= 6*10^5"  

所以這樣說吧, 上面的第一步最壞的情況已經是O(L), 第2步要跟每個pattern比較一下這步卻很痛苦, 這是multi-pattern matching, 用KMP好像也不一定夠快? (我也忘了KMP怎寫, 只記得concept...) 實際上我也真的這樣implement, 也真的超時了

結果還是跑去看Editorial, 又掘到金了! 兩大keywords:

Rolling Hash,  Rabin-Karp Algorithm

 前者是一個運用Polynomial Hashing的一個技巧, 後者是活用這個技巧的 Multi-Pattern Matching Algorithm!!
這個Wiki 的解釋也真的很好懂, 沒複雜的分析, 但很有說服力, 而且還說明了它跟其它String Matching算法的分別, 例如它說了 "Rabin-Karp始終是Hashing, 可以有很差的效率, Single-Pattern Matching上還是KMP佔優, 但它的強處是在Multi-Pattern Matching (其它的還有AC自動機)"

所以...基本上這題就是Rabin-Karp Algorithm的變種囉
詳細的自己再看上面的wiki-page吧

Rolling Hash 是一個技巧, 不一定要 "減頭加尾", 像這題, "換一個字母" 這類的事當然也做到
只要你是用Polynomial Hashing就行了

我想這題最難的是要說服自己時間複雜度
官方說是 O(L lg n)  我感到有點奇, 因為我自己AC的版本, 最低限度也是O(L lg n) 但這沒算上Hashing Collision後要做String Comparison 然後fail 這件事
理論上Hashing Function柒的話, 這件事可以發生很多次吧? 那就遠超於 O(L lg n)了, 因為要做很多次String Comparison, 這也是為什麼它用在Single-Pattern Matching時worst case可以跟naive algorithm一樣是O(NM)的原因...不過算了AC了就好了, 也可以這樣想吧: 一直以來所有人都是用Polynomial Hashing去比賽的, 這已經是定式了, 自然不會是一個"柒"的hash function...

以某黃字User的comment做一個結語:

Most hashes are certainly not unique or why do we use hash? If C is in ACM/ICPC, you can simply choose a prime other than 3 because the problem setter does not know which prime you used so he can not construct data against you. He can only guess some contestants will choose 3 and build some data to make them failed. However, in Codeforces, hackers can construct data against a solution. So you have to compare two strings themselves when the hash of them are the same. However the probability of two different strings have same hash is low so only a few strings will be compared. So, the hash helped you to evade TLE.

強烈建議看一下Code, 也是很有機的寫了一些comment
http://codeforces.com/contest/514/submission/10158032

D: (Binary Search, Two-Pointer Algorithm, Segment Tree)
這題有點難搞
原因在於 題意其實很直觀, 就是不斷query 一個range maximum
所以我直接就用Segment Tree上了! 結果也是AC的
(原本有想過能否用BIT可以更易寫出來, 但maximum之類的好像不能用BIT做...只能做統計的工作啊)
http://codeforces.com/contest/514/submission/10172455

正如我的comment上所說,  這是overkill啊,
官方的答案是用一種叫 "Two-Pointer Algorithm" 的方法, 那個方法應用在這條題目上很高明
但實作上我自己是想不出來了, 紅字User們說是用兩個Stack的樣子
總之正解是易寫也很有效率

我反而學到了兩件事: 是否overkill也不要緊, 但起碼concept對, 寫得出來, 就可以AC的, 也不用這麼介意...
然後再來Google了一下什麼是Two-Pointer Algorithm...這東東很多題目都有Tag, 從來都沒認真想過是什麼的一類Algorithm

看了高手們的解說, 就比較清楚了:
這類Algorithm的運作通常是這樣的:
一個pointer指住第一格, 一個pointer 指住最後一格, 然後開始夾三文治
做某些東西或者checking, 然後移動其中一支pointer (不知會否有2支一起動的情況?)
一個pointer只能向單一方向移動, 而每次最少一定要移動其中一支pointer
這樣的話 時間性一定是O(N)了
這類Algorithm好像很強大的樣子, 形象化來想有點像什麼Sliding Window還是 Sweeping Line的? 傻傻搞不清, 總之這種思路還是記一下好

E: (DP, Matrix Repeat Squaring)
另一題很想記下的題目!
因為這道題的重點在於當年聽過的Matrix Repeat Squaring應用
話說當年完全不知 "為何, 何時, 怎樣" 用這個技巧
還是CF的高手們好, 一個Reference就解得清清楚楚的說

先說一下題意:
一棵無限的Tree, 每個node 都一樣有同一set的兒子 (最多有10^5個兒子)
eg:  root 有 3個兒子, 它的每個兒子也一樣有3個兒子....直到無限深度
每個兒子跟它的parent距離 (edge的長度) 最多是100
現在問有多少個node距離root 是 x ( x < 10^9)

這題很直接就能寫下DP的狀態:

dp(i) 為 有多少個node 距離現在的node EXACTLY = i

然後答案就是





但難度在於 dp(x) 的 x 可以有 10^9 那麼大! 即使是 O(N)也超時 (也超MEMORY!)
怎麼辦呢??? 原來....原來....
原來這種情況就是要用Matrix Multiplication的Trick啊
在Editorial 挖金挖到一篇超上乘的tutorial 給我這種新手的
Matrix Exponentiation

But, what will you do if the problem says, given 0 < n < 1000000000, find f(n) % 999983 ? No doubt dynamic programming will fail!

這是它的前言, 說了最簡單的DP例子Fibonacci Sequence, 在 n 好X大的時候也是會吃屎的
而這就是 "Matrix Repeat Squaring" 出場的時候了!
這種加速的技巧只能用於符合某種"形式"的 Recursion Formula, 也就是DP Transition

| f(n) | | f(n+1) |
| f(n-1) | | f(n) |
M x | f(n-2) | = | f(n-1) |
| ...... | | ...... |
| f(n-k) | |f(n-k+1)|

直接引用它的解說, 其實就是先寫下 類似以上的算式, 以他的notation

第一格就是我們想要的答案 而其它的是計算答案時要用上的東東

然後我們逆算出 M 這個 n*n 的matrix, 之後的就簡單了, 把repeat squaring的技巧用在

matrix multiplication 上算出 M^x, 乘上我們的"base case" (最開頭的 n*1 vector)

就能得出我們想要的答案 (右邊的n*1 vector, 的第一格)

例如 Fibonacci Sequence, F(n) 要用上F(n-1) 和F(n-2) 對吧

右邊先寫上 B

| F(N) |

| F(N-1)|

左邊是比它"前一步"的States, 我們叫它A: | F(N-1)|

| F(N-2)|

然後要做的就是人手逆推 M, 使 MA = B

| ? ? | |F(N-1)| | F(N) |

| ? ? | * |F(N-2)| = | F(N-1)|

不難推出 M 是

| 1 1 |

| 1 0 |

那麼當我們要算 F(10^9) 的時候 只要算 M^(10^9) * A , 然後得出的B 的第一格就是我們的 F(10^9)了!

其它詳細的看那個優美的Reference吧, 都說得很清楚了, 通常M 都會很有Pattern 不需要hard code就能generate出來的

由於 是做 lg(x) 次 matrix multiplication, 假設matrix 是 N*N

那麼就是 O(N^3 * lg(x))

很好很強大的DP輔助技巧!

回到原題目上, 基本就是用這個想法, 當然作為Problem E也沒這麼直接

最不同的是我們要求的答案不是單一的 DP(X) , 而是 summation DP(i)

但也是大同小異的

首先注意到我們的A (也就Base Case的vector) 要用上全部DP(100) 個State

所以 X <= 100的時候, 直接用普通的DP就好了

當X > 100的話, 我們就要用上這個技巧了

注意先Update X = X-100, 因為現在我們的"Base"不是 0, 而是100

然後由於我們想要算的是 summation DP(i) 那麼乾脆把它放進我們的A (還有B) 內 加上本來的 DP(1) to DP(100) 總共是一個

101 * 1 的vector

官方的notation是 1* 101的, 思路一樣, 我想我以後還是會跟Reference那個notation

接下來的就是逆推 M了, 這一步是這一題的唯一難度 M 是什麼可以自己看Editorial:
(注意它跟我 / Reference的notation不同, 應該是Transpose了還是怎的)

http://codeforces.com/blog/entry/16398

就是這樣了! 

最後把AC的Code貼一下以作記念: comment應該也算清楚的 日後重溫應該也明白的吧...
http://codeforces.com/contest/514/submission/10218534

Codeforces Round #287 (Div. 2)

2015年大年初一
還是先把要做的做完...就是把解題過程記下..

這場是"回頭"打的#287,  所以上一篇先記下#289...
#286也有做的, 可是該場較特別...下篇再記 (順序什麼的先不管了=.=)

Codeforces Round #287 (Div. 2) 

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

雖然這場也是5題做完..可是這場比較特別, 在於題D我卡了好幾天, 最後的最後才發現自己中伏了...然後也好不容易才AC的...題E相對下還易很多呢..起碼是短時間內自己過的...(雖然是某個圖論的白痴東西弄到錯了很久..)

D跟E也要花點時間說呢 zzz...

A: (Greedy)

一題赤裸裸的Greedy...沒什麼好說的

B: (Math, Geometry)

這題比較令我出奇地覺得原來Div 2的題B也可以這樣啊...然後才發現原來也是很直觀的說

分類上絕對是Geometry, 但Geom也是Math的一部分, 也就標上Math的Tag好了...

上圖就是題B的題目, 就是給定一個圓形, 然後在邊上任意一個點作pivot, 然後該圓形可以繞住pivot轉一圈, 這樣算一步。問要多少步才能使圓心由原本的位置轉到目標的位置?

這類的題目很自然一想就會想到Shortest Path, BFS 之類的東西...

拉上Geom也好像很複雜...

但是只要在紙上畫兩畫, (或者腦子強的空想一下真實的情況)

不難發現一步之後, 圓心的軌跡 (Locus) 很有趣...

(Locus 是不是這裡正確的用語? 我也不太清楚, 只記得中學時老師說過Locus已經不再考了, 但我想一定是個很有用的道具吧...)

看我上面漂亮的小畫家圖...

黑色是原本的圓形, 紅色是繞住pivot 轉動時的圓形位置, 然後籃色虛線就是圓心的"走向"

也就是圓心的Locus

然後這只是假設pivot是定在那個點的情況, 實際上pivot可以在黑色圓形的邊上任意一點

發現到Locus也是一個半徑一樣的圓形, 而圓心剛好就是pivot位置

結論就是在任意選pivot的情況下, 圓心的Locus是以黑色圓形的邊任意一點作圓心來畫圓形的Union

按上圖來想像一下, 就是有很多藍色的圓形, 一個疊一個的, 組成了一個跟原本圓心一樣, 兩倍半徑的圓形

總結一下的話,  就是在一步內, 圓心可以移動到一個兩倍大的圓形範圍內任意位置
這樣的話, 到目標點的最少步數就很易找了....就是拉直線然後Greedy地一直走過去吧

實際上可以寫成公式, 所以是O(1)

C: (Graph, Tree, Ad-hoc)

一題很奇怪地不知怎麼被人Tag為Math的題目, 後來看Editorial才知道我的解法不是官方的

好像是跟某堆User一樣, 是O(h)的解法, 比官方的好一點...

題目有點Counting的意味, 給定了一系列的instruction, 基本就是, 由根點不斷"左右左右..."地向下走, 直到葉就回上一層...然後問, 要到達某一個葉子前, 會先經過多少個nodes?

這題我的解法是很簡單的逆向思路...

首先由終點向上走...會發現一個很單純的事實: 如果終點是 RIGHT CHILD, 那麼在上一層時的instruction一定要是"右" LEFT CHILD的話就是"左"

那麼要是在instruction 必需要是"右" (才能到達終點) 時的instruction, 不巧是"左"的話

很自然地該點的所有左子孫都會經過....關於這點我沒有很詳細的思考過程, 反而是有一個

很人性化的想法說服了自己: 要是該點的左子孫內有點不會經過的話, 那麼要是問題的input是裡面的其中一個葉子怎麼辦? 題目也沒說明沒有solution時要怎麼做...就是說每個葉子都可以自然走遍的....很有說服力吧=.=

回到問題上, 這樣思考的話就是說: 由根點開始走到目標點的路只有一條 (Tree...)

我也清楚知道這條路的走法 (eg: "左左右左右右左右...") 然後我也知道instruction是"左右左右"不斷loop的, 那麼當一個instruction跟我要走的路需要的instruction不同的時候, 就是"走錯路", 而走錯路是必定會經過下面所有子孫, 才會回到該點, 然後就走回正路去下一層...一直到終點

這樣算法就很簡單了: 先找出由根點到終點的路線, 然後以O(h) 的Loop, 試住左右左右的走下去,要是"走錯路"的話, 就把答案加上"錯路"的sub-tree size, 由於是full binary tree, 不用precompute也可以, 最後把答案加上 h-1, 因為根點到終點的路本身就會經過h - 1 個點啊...

D: (DP, Combinatorics)

題目簡單卻陰濕 (其實是我低能...), 答案很難寫...起碼我看過別人的code, 也不是很直接就寫完的DP...

題目是這樣的: 

求符合以下條件的數字總數目 mod m

該數字要有n 個位 (沒有leading zeros)

該數字要有suffix y, y > 0,  y % k = 0

n,k,m 也是input,  n <= 1000, k <= 100, m <= 10^9

要說的話, 這題最直接想到的也是直接的DP做法

State就是這個吧: 

State(L, r) := 長度為L的數字而 mod k 之後剩 r 的數字數量

這樣也只有1000 * 100 個State, 很有DP的樣式

問題在於, 怎樣數呢?  做過一些Combinatorics的題目也會知道, 怎樣去防止repeat counting絕對是重中之重, 只要這個搞定了, 其它也只剩簡單數學 / implementation技巧而已...

然後這個開頭我是難倒了, 甚至完全想錯方向, 不知怎的竟然走去想 inclusion-exclusion principle了...

事實上是很簡單的...在於這題的context上, 不要重覆數的同義解釋是, 用長度為L的suffix數出來的, 跟長度為L' 數出來的要不交集 (L' > L)

就是說在算 State(L', 0) 的時候, 我不可以算一些由 State(L, 0) 來的數目 

也不是直接 State(L'-1, r), r > 0 就可以的, 因為這個state也可以包括來自某些State(L,0), L' -1> L 的數目...

想到這兒, 自然就會想到在算任何的State時, 也不要用上 r = 0的State...這兒會發現這題用bottom-up / iterative 的寫法絕對更易想/寫

以iterative的想法, 一個State(L,x) 轉移去另一個State(L+1, r) (我較喜歡用"生成" 另一些States) 的physical meaning 就是在某一個長度為L, mod k = x 的數字, 加多一個digit [0-9],  變成長度為L+1, mod k = r 的數字,  而上面的說法就是說當x = 0時直接skip, 不要用它來"生成"其它States

去到這兒, 複雜度是 O(N * k * 10) = O(N*k) 還是ok的, 再來看一個完美的圖解

上面代表長度, 下面代表mod k 後的數字...

紅色就是現在iterative的位置, 我們的目標是要加一個數字令到加上 234 mod k = 0

假設我們填了5 吧, 那麼所有 "????5234" 的數字都是答案之一了, 而且我們之後不會再數到suffix = "5234"的數字吧? 所以這兒就要一次過數了

那麼簡單的counting,  我們還有4個位沒有填上, 除了最左的位置之外, 中間所有位置都是任填 [0-9] 就是10 個choice, 最左的位置是9個choice,  所以就是 9*10^(n-3-1-1) * State(4,0)

這樣的想法很對吧? 最後special handle一下 n = 1的case, 因為 suffix不能為0, 而 0 在n = 1時一定會包括的, 那麼 n = 1時把答案減去1 就好了....

然後當然果斷WA了...老實說這樣做連test case #3 也過不了 但確實想不到那兒錯了

看了Editorial, 你他媽的用Top-Down啊...幸好下面comment有人說了bottom-up, 跟我的做法是一樣的說...

連State definition跟公式也都一樣, 細節上例如不用 r = 0 的 state 生成其它state 也都一樣了...

那麼錯什麼呢?

很幸運地, 在昨晚喝了些酒的狀態下終於發現了...我中伏了!

"因為 suffix不能為0, 而 0 在n = 1時一定會包括的, 那麼 n = 1時把答案減去1 就好了...."

這句是bullshit, 完全錯的!

因為不止是n = 1,  事實上不論n是什麼, 要是suffix只有0 mod k = 0, 的話, 不就是 y = 0了嗎?
記得題目條件是 y > 0 的吧....

所以不止是 n = 1時的0 才有問題, 例如k = 3,  n = 2,  那麼10也是不行的, 因為唯一mod k = 0的suffix就是0 啊...同理, 30是可以的, 因為除了0之外, 30也是mod k = 0的suffix

考慮了這個原因, 題目又更複雜了...

我也不想大改我的code / state definition

事實上, 那時我才明白為什麼有很多黃字/紅字user的state有3個甚至4個dimensions,

其中一個是 0-1 flag特別處理這個問題的 (就是有沒有suffix 是全部都是0...)

老實說這樣改了State是一定能過的, 但我不想

我也看到有人跟我一樣用2 dimension就過掉了...

於是我想呀想...想到了一個奇怪的點子

這題正常來說, 是Loop完所有state, 最後一次過把r = 0 的states 加起來做答案

而我發現, for 每一個長度 L,  dp(L, ?) 只會在那個iterative有用, 之後不會再用到了

然後 0 那個問題, 其實可以想成是 "要是suffix mod k = 0, 那麼我再append 一個0 的時候不要算進答案內"...有點難解釋, 看看state transition吧

State(L, r) --> append 一個digit 變成 --> State(L+1, x),  

如果 r 不是0, 那麼沒影響, 原本的算法是正確的

如果 r 是0,  那麼就要看看我append了什麼digit了, 要是digit = 0的話就skip掉吧, 其它digit 就沒影響, 原本算法正確

然後每次iterative完, 直接把答案update! 原因下面解釋

但這樣會把 數個連續是0 的suffix少算了 (eg: ???0000)

但是發現到其實也只是少算了 全部是0 這一個case而已

然後iteration到這一步, r = 0的state已經算進答案了, 該state不會再用到了, 我們直接把dp(L, 0) = 1就好了!

所以其實上述的state transition中,  要是 r = 0, 其實只是代表了suffix全部都是0的數字, 其它令到 r = 0而suffix不是0的, 已經算進答案去了

好吧, 我解釋得很複雜, 因為這題真的很複雜, 很難解釋

我只能說我看到有紅字user 也做了類似的東西, 就是在loop中把state 的value改成1

我說這題不是普通dp是因為, state的意味在中途已經變了...話說這樣的題目, 不論做多少題也沒信心即場一棍過啊...

E: (Graph, Shortest-Path)

一題也是很難, 但不是難在算法, 是難在I/O的問題, 如我說的, 相對題D 真的很易了...

題目給定了一個Graph, 圖中有兩類edge, 一類是完好的路, 一類是破路

求由 s 點到 t 點的最短路的最低cost, cost的算法是: 最短路中"破路數目加上最短路以外的完好路數目"

由於題目很好人的已經告訴你, 最優先條件是最短路, 那找最短路是一定的了

這兒說一下, 由於圖不是weighted, 用BFS也很足夠了 但我心血來潮想用這條題目溫故知新一下Dijkstra Algorithm, 於是寫了兩個version, 兩個都AC了

Dijkstra的確是很易寫也很易明的Algorithm, 不明白為何當年我認為SPFA會更易寫, 比彈性來說Dijkstra絕對較好, 時間也沒很慢 (用Priority Queue的話)

然後..我們來想一下cost 的定義有什麼提示, 隨便寫一下就會發現cost 其實只depends on 完好路的數目 (同理, 其實只depends on 破路的數目, Editorial用前者, 我用後者, 只是Maximize / Minimize的分別)

Dijkstra / BFS的其中一個副作用是, 可以同時找到起點到其它點的最短路

那麼很自然想到可以用一個DFS 作Backtracking, 由終點backtrack到起點, 同時數算(所有)最短路中possible最少破路的數目, 這個Backtrack肯定很快, 因為我們DFS的條件是以該點距離起點的距離 (Dijkstra找出來的)作判定, 要是跟現在的點相差一步才Backtrack的, 基本就是一次DFS的時間吧

去到這兒, 也很順利的, 總共寫了一個Dijkstra/ BFS, 一個DFS, 沒想到 (其實是沒看清楚...)

難處在於I/O...!!!
題目不止要求找出最低Cost...也要找出那些路要修好, 那些路要破壞...!

有見給此, 很自然想到, 在Backtrack時順路把最優最短路整條記下好了

(最優最短路就是令我們有最低cost的最短路)

那麼最優最短路的破路要修好, 最優最短路以外的完好路要破壞!!

這樣問題變成一個最基本的圖論問題了: 如何儲起edge最方便!!!

好吧, 不賣自己關子了, 最好的結論是....溫故知新, 要用上最方便最神的儲圖方法

也就是用 array 做成的adjacency list...

老實說, 溫習後再次發現這個圖的儲法真的很方便, 也很高明

它兼備了adjacency list跟edge list的優點...

int from[200005], to[200005], nxt[200005], adj[200005], w[200005], e = 0;

void add_edge(int a, int b, int type){
    from[e] = a; to[e] = b; w[e] = type;
    nxt[e] = adj[a];
    adj[a] = e++;
}

高明在, 要是edge / vertex有什麼特別的property, 只要再開一條array就可以了..

這題也就這樣了, 但我還是WA了一次

原因也在這個圖的表示方法...!
就是....我開Array開太小了...路是有10^5條, 但是由於是雙向, e 的數目會雙倍啊親...

把array開成2*10^5後就AC了...低級低級錯誤...證明我真的很少用這種表示方式解題啊...

也是一道不錯的題目呢 :)

送上我其中一個用Dijkstra寫的Code
http://codeforces.com/contest/507/submission/9813132