MSBOP 2015 Qualification Round & Round 1A (Updated 2015-05-03)

親愛的Peter神得知我想有一件T-shirt後介紹的一個新比賽
由M$主辦 確實條件很簡單 只要在能advance到Round 2就有T-Shirt了

這個比賽的流程是 Q-Round-->Round 1A / B (各500名advance)--> Round 2 --> Final
先來說結果吧 我Round 1A 不打算玩的, 所以遲了一小時多開始玩, 結果AC了 3題中最多分的一題, 但因為太遲玩 + 錯了一個白痴錯誤, 只有504名
今天全力玩Round 1B, 狀態卻奇差, 也進級失敗, Round 1止步了

然後是一些我對這個比賽 / 平台的comment
每場比賽跟GCJ一樣只有3題, 題目也有趣的
但我還是很不滿

首先, 這個平台沒有練習模式, 賽後想再submit試試看也沒有機會
也沒有Solution 跟Editorial, 有幾題真的我認為pattern很常見卻不會做的題目
我真心很想知道思路啊...

就結果來說, Qround我就不特別寫了...沒什麼好寫的, 打得也不特別好
A跟B應該都會做的, B-Large自己白痴交了個TLE的solution, 之後其實改好了
但正如我所說的賽後根本不能submit試試看能不能過...唉

C是完全沒想法, 開頭以為是那個簡單的分開 x 跟y axis來算optimal value的技巧
卻完全不是, 問了GG 也說有點難做就不了了之, 這是一題我很想知道思路的題目

來到沒認真打的Round 1A, 遺憾是有的, 要是認真打的話應該advance = 有T-Shirt了..
Round 1A的3題:

A 我真心認為是語癌, 它的sub-tree跟我認識的好像完全不同意思, 題目也沒特別說明它的sub-tree是不是common說的sub-tree..總之是語癌題, 果斷跳過
感過要不是語癌的話, 應該是中等易一點的dp on tree...

B 我認為是最難的一題...也是另一題我很想知道思路的題目
給了 n (< 1000) 個直角等邊三角形, 斜邊都在x-axis上面, 三角形可以overlap
你可以決定要build那一些三角形
build一個三角形的收入 = w_i  -  它的area
要是某部分有overlap的話, 那部分只需要算上一次就ok
問最大可能的收入是多少

感覺很像knapsack類的dp, 但overlap area 背後的trick 完全沒想通
總之就沒多少想法就是了...真的很難

C 是我唯一過了的一題...竟然small + large有45分, 根本沒多難的...
但這題是唯一我想記下的, 因為還是很有成功感的說

MSBOP 2015 Qualification Round

(2015-05-03) 先更正下對這個平台的看法, 過了數日後終於能夠賽後Submit了

結果還算是合格的平台吧...

至於比賽的Editorial 還是沒出...看來這堆題目要成為遺憾了

之前 (上面) 所講的 Qround B-Large 雖然是白痴開錯了array size

但即使不開錯也不算是太易過的,,,終歸還是在運氣+摸魚的情況下過了...

至於C-Large, 還是沒想法, GG也沒更進, 果斷把它從腦中丟掉比較好

A: (Ad-hoc)

找潤年的基本題目...就按住題目給的定義判定下就好了...

B: (DP)

Q-Round來說重點是這題吧...找Peter神試了一下, 他也認為不算是容易的,,.

所以就記一下吧

DP來說我認為也是有趣的一題...思路可以學習一下 (原來可以這樣DP的啊)

題目是這樣的 (以Large來說), 給了string S 一條 (|S| <= 1000)

問有多少Subsequence 是palindromes...

注意是subsequence 不是substring, 所以也不算太直接

由數據來說, 應該是O(n^2)的DP
(好像做過palindrome相關的題目不是DP就是Greedy?)

問題是怎樣dp 才能不超時...

由於O(n^2), 又是palindrome

狀態應該是近於 DP(x,y), x跟y 是S 內的range這樣...

我是用Top-down的做法的 (bottom up不太會code那個順序...這些事其實也不用強求)

Top-down內不能有for loop吧, 不然就不是O(n^2)了...

然後在紙上畫兩畫, 發現了一個有趣的Observation:

首先設DP(x,y) 為position x 到 y (inclusive)之間所有palindrome subsequences的總數

然後大約是 S[x] 跟S[y]慢慢拆走再看DP(x+1, y-1) 是常識吧....

那麼會出現S[x] == S[y] 或 S[x] != S[y]兩個情況

先看 S[x] != S[y]的情況

由上圖能發現, 

DP(x,y) = A+B+C-2C, 要 -2C 是因為 A+B的子狀態時會重覆算了C的子狀態2次...

所以 DP(x,y) = A+B-C = DP(x+1, y) + DP(x, y-1) - DP(x+1, y-1)

再看 S[x] == S[y]的情況

首先, 要explicitly 加上 1, 因為S[x]S[y] 自己已經是一個palindrome, 而這個palindrome不能由任何子狀態 (A,B OR C) 算出, 所以要自己把答案 + 1

然後就跟上面差不多了

DP(x,y) = A+B+C-2C+C, 要 -2C 是同樣原因, 要+C 是因為 C跟 S[x]CS[y] 是兩個狀態分別數了兩個 disjoint set of palindrome subsequences, 兩個disjoint set 的size 跟都是 C 那個狀態的Size...

所以 DP(x,y) = 1+A+B+C-2C+C = 1+A+B = 1 + DP(x+1,y) + DP(x,y-1)

就是這樣了...combine 兩個case 一下可以很簡單一行code就完成

至於時間複雜度嘛...Recursion的complexity我從來都不太懂算

但由於沒有for loop, 而每個狀態都會把 [x,y] 的range縮少至少 1

x跟y 只有O(1000) 也就是最多只會有O(n^2)個狀態, 每個狀態算一次這樣 (with memorization)

MSBOP 2015 Round 1A

C: (Math, Bipartite Matching)

這題簡單來說, 是Math + Maximum Bipartite Matching
有成功感的原因是, 除了它高分以外, 是以為不多久前學的Maximum Bipartite Matching
終於派上用場了, 果然如我當時所說的, 性價比真的很高
而且思路也是從當時某一題題目引申出來的, 再從這一題學到了另一個 fact
(詳情請自己找回之前Bipartite Matching那篇文)

我直接以large的數據來說一下

題目給了 n (< 1000) 個數字, 2個數字 a, b  (a<b) 叫prime dependent iff  a*p = b for some prime p

問這n 個數字 最大的subset where subset內任何2個數字都是prime independent的subset size
這些數字 < 500,000

直覺認為跟prime factorization脫不了關係, 打質數表也是必需的, 500,000內的質數還是很少的(5000個左右)

然後就在紙上畫了畫 把sample case都畫了一下
畫的方法是把 n 個數字內 prime dependent 的都連上一條線, 這樣就得出一個graph

然後不難發現, 答案就是這個graph的 Maximum Independent Set!
這個問題我也知道是NP-Complete的, 而在題目中有NP-Complete的情況只有幾種:
要不是 n 很小, 可以用某些dp 暴試之,
便是這個NP-Complete的題目在某些條件下不是NP-Complete的, 例如General Graph下的問題在Bipartite Graph下通常都很易解的

這也是一樣! 這樣就引至我逆轉去懷疑, 題目給出的這些Graph其實是不是 Bipartite Graph呢?

這個要prove也不算難, 基本上證明graph中沒有"三角形"就好了...

Case 1: 假設 a, b < c,  然後 a跟c 有edge, b跟c也有edge, 證明 a跟b之間不能有edge
--> Given a*p1 = b*p2 = c
assume a跟b 有edge , then a*p3 = b
-->  a*p1 = a*p3*p2 = c
--> p1 = p3*p2
--> contradiction as p1 is not prime now!

Case 2: 假設 a < b,c,  然後 a跟b 有edge, a跟c也有edge, 證明 b跟c之間不能有edge
--> Given a*p1 = b,  a*p2 = c
assume b 跟c 有edge, then b*p3 = c
--> a*p1 = b, a*p2 = b*p3
--> a*p1 = a*p2/p3
--> p1 = p2/p3
--> contradiction as p2 is not prime now!

--> 這個Graph 是bipartite的!!

好了, 接下來, 我記憶中 Bipartite Graph中的independent set 好似有解的
...好吧, google了一大輪, 原來我記錯了

其實...Bipartite Graph 的Minimum Vertex Cover 才是有解
Min Vertex Cover =  Max Bipartite Matching

然後...經由推理 (這個其實已經足夠肯定)
再加上google wiki, 就肯定了以後事實:
For Any Graph
Max Independent Set = # of vertex - Min Vertex Cover 

在Bipartite Graph的情況下, 
Max Independent Set = # of vertex - Max Bipartite Matching

這就出現算法了!

先打質數表
再用 O(n^2) 建圖
然後在圖上找Max Bipartite Matching...

咦?
Maximum Bipartite Matching 可是要 O(V^3) 或者O(VE)啊...
前者是用matrix來儲圖, 這個題目一定不行了
只有O(VE)可行... (用adj, list來儲圖)

但...這不是等於要 E = O(V)嗎?
這下又要證明一下了...(其實真正比賽時可以直接去了...感覺根本就是正確做法, 不用懷疑)

這個證明比賽時沒很全做完...事後再試試嚴謹一點的

我想證明這個Bipartite Graph不能有cycle ( i.e. even cycle)
也是用contradiction來證明:

證cycle存在, cycle中最小的數字叫a, 最大的叫z
則
a*p1*p2*...p_n = z  (一直按最長的path由a走到z)
同時
a*p_x = z (a跟z 直接連起來的edge)

則p1*p2*...p_n = p_x
-->contradiction as p_x not prime!

由於不能有cycle, 所以最多只能有 V-1條Edge了
QED!

Code起, AC了
遺憾的是Code仍是要出cheat的...concept是記得, code卻沒有上手呢...

結語: 這題真的會比題B難嗎...

結語2: 今天認真玩的Round 1B比1A更加強差人意, 就不特別記下了...倒是很想有賽後submit作practise用的機制呢...還有solution啊....M$ Why you suck so much

結語3: 有開始在看KMP / String相關的算法了, 我沒有忘記要寫一篇String Searching的詳細文, 這才是原本的步調...但看來要在Code Jam Round 1B後再說了...希望1B別比1A難吧..

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 #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

Google Code Jam 2015 Qualification Round

愈來愈忙了, 弄得我計劃好的事(很多)都要先放下了...
6月前看來都要忙死了 :(

但既然我都跟Peter 神說了我自小的夢想, 就是有一件比賽T-Shirt
所以還是擠了時間第一次 (還是第二次?) 打了一年一度的Code Jam

就結果來說, 雖然過了Qualification Round, 分數卻很難看
果然比賽T-Shirt基本實力就是有Div. 1 中上級的實力吧...

話說我一直以為Qualification Round都是很易的
起碼是沒精神的情況下還是能輕鬆過的程度
沒想到這場對我來說這麼難...

比賽有4題, 每題分大小case
即場我交了A1, A2,  C1,C2  而只有前3個AC了, C2 因一個白痴錯誤搞至WA....
至於B, 我知道Solution後才發現自己腦閉塞了, 怎麼我感覺比C難
D是完全沒頭緒, 連小的Case也沒有, 後來問GG 好像是人手找Pattern再Code的樣子

Google Code Jam 2015 Qualification Round

題目: https://code.google.com/codejam/contest/6224486/dashboard

Google的題意大都很有趣, 這點我覺得比FB Hackson Cup好, 雖然很長就是了...

所以寧遠晚點睡還是打長一點

A: (Greedy)

題意是這樣的

有n個人看表演, 每個人都有個毒撚程度叫 a_i,  代表在他之前要有 a_i 個人站起拍手, 他才敢站起拍手。現在要你請五毛, 每個五毛面皮極厚, 不論有多少人已經拍手, 他們都可以拍手, 請五毛要花五毛, 所以求最少請多少位五毛才能使所有人都拍手呢?

基本思路就是, 一位五毛反正何時都能拍手, 不如一開始就拍手, 把他們作為其它毒撚的觸發點。然後假設有毒撚a_i 跟b_i,  a_i < b_i , 則 b_i 比 a_i需要更多人, 而a_i 肯定在其中, 這樣的話, 用for loop 計算所有毒撚還需要多少人才會站起 (假設毒撚度比他低的人都已經站起了, 所以可以扣除他們), 拿個maximum, 就是我們求的五毛總數, 可以把他們全部放在一開始時就拍手, 那麼好像骨牌一樣, 之後所有人都肯定會輪住站起拍手了。

B: (Greedy)

這題很糾結, 主要是....不知道為什麼自己卡了

其實核心思路一早就發現了才對

雖然現實中是因為要上街所以沒時間想很詳細...

直接說一下題目:

有一間餐廳, 裡面竟然有無限人,  但只有1000位人客是在吃東西的

這些人客每個人在吃a_i 樣東西

1秒之間, 可以發生以下任意一件事:

1. 所有有東西吃的人都吃一件東西
2. 所有人都不吃東西, 服務員把其中一位人客的食物, 拿走任意數目, 然後分給另一位人客

求最少時間令所有人把東西都吃完~

首先很直接的, 如果把人客的東西分給別人, 一定是分給沒有食物的人吧 (有無限人啊...)

然後假設有一堆人, 其中最多食物的人客有 k 樣食物, 那麼答案最多也只是 k

廢話說完, 開始說點有用的:

1. 假設有 a 秒 執行動作 1, b 秒執行動作 2,  答案是a+b秒, 肯定先執行完全部動作2
2. 因為順序不影響答案, 所以就可以分開求, 也就是先把 1 或者 2 都執行完了, 才執行另一種

再看看數據, 1000*1000, 其實也很明顯叫你用O(n^2)的算法了

首先 動作 1 (全部人吃東西) 這個可以暴試的, 問題在於動作 2, 好似有點煩

這兒其實是有點logic的,  假設現在 有 a 秒執行動作 1, 執行完就完了, 全部人都吃完了

那麼在執行第一個動作 1之前, 所有人的食物數都不得超過a, 不然就矛盾了...換句話說, 在執行第一個動作 1之前, 我們要執行動作 2 k次使所有人的食物數都不得超過a

所以問題就變成 給了一個數字 a, 求最小的k 使 k次動作2之後, 所有人的食物都 <= a

留意動作2只影響到一個人, 所以其實又可以獨自求...用一個for loop 把所有食物數 > a 的獨立求出最小的k, 這些最小的k 加起來, 再加上a 就是當用上 a次 動作1時的最優答案 用一個for loop 暴試所有a,  總共就是 1000*1000 = O(n^2)了

至於求出最小的k 那一步, 我們要用O(1)來求了

這步才是最難證明的!!

設 a = 5, k = 12,  正解的方法是簡單直接的一直減5減5這樣, 所以是 ceil(12/5) - 1

但怎樣證明其它分解不會更好? eg: 12-->{6,6} --> {1,5,6} .... 

其實我也是事後AC了才回頭想...好像不是那麼直接 (可能我想多了?)

最後我用這樣的步驟說服自己:

設k = X+Y = a + Y'  , X>a, Y>a

然後我們再做多一步
X+Y--> X1+X2+Y ,  a+Y' --> a+a+Y''

Case 1: 如果X1 跟 X2都比a 大, 則繼續, 這時RHS <= a 的數目更多

Case 1: 如果X1或者X2 > a的話, 這樣跟原先的狀態一樣(兩邊扣除一個 <= a 的話), 這是還是RHS比較多 <= a的數字

Case 2: 如果X1跟X2都 <= a,  則LHS跟RHS一樣多 <= a 的數字而已

一個不正式的induction 說服了我自己其它拆法不會比單純地 k 減a,再減a...這樣更好

所以...很簡單地暴試a時, 發現有 數字比a大, 則 k = ceil(b/a) - 1

就是簡單的除法, 真的很直觀的....= =

我還是認為這題不易, 為什麼那麼多人做到=.=

起碼我一開始是想都沒想就認為拆法一定是除2除2 地拆....唉

C: (Math)

這題題意有點複雜, 就不重覆說了, 題目名倒是很有趣, 叫Dijkstra, 但題目自己也說了, 跟Dijkstra Algorithm完全無關 (o:

給了一個類似cross product的matrix,  i.e  i*j = k,  j*k = i,  j*i = -k
然後給一條string, 這條string只有 i, j, k 這 3個alphabet, 這條string 重覆 L 次

問能否把這條重L次後的string 分成3段, 分別的product是"i", "j", "k"

這條反倒我認為是很直觀的說, 麻煩在於有1 和-1的存在, 但基本思路如下:

首先, product 為 i 的string 其實是prefix,  為k 的string 是suffix
然後中間那段肯定要是 j, 要是符合這3個條件的就算是成功了

想到會有數個 product 為 i 的prefix, 好像有點複雜
但其實留意到 自己*自己是-1 這個特性, 可以寫下以下的算式

設 整條 string 的product 為C, 

假設存在某prefix product為i, 某suffix product 為k, 但我不知道中間那段的product, 叫它x
那麼  i * x * k = C

然後做一件中學時常做的事!
i*i * x * k*k  = i*C*k

--> -1 * x * -1  = i*C*k
--> -x * -1  = i*C*k

--> x = i*C*k

看! 這個結果, 代表很多事

首先, 有多少個 頭i 尾k 根本不重要, 因為中間那段肯定一樣, 都是 i*C*k !
所以最重要的是存在頭i 尾k
然後 i*C*k 要是 j 的話, 就成功了, C可以O(N)直接求出來的 :)

這樣就輕鬆過C1了...

至於C2, 不同的是在於數據大很多

根本不可能用直接做, 連O(N)都不行....

這時要用上多點觀察:

由於string S會重覆 L次,

我們現在不能直接求  S*L 的product了...

但我們可以先求S的product

然後發現一個事實(for i, j, k):
i = i
i*i = -1
i*i*i  =  -1*i = -i
i*i*i*i = -i*i = 1
i*i*i*i*i = i ....

看! 一個字母, cycle length 為 4! 第5次開始又等於自己了..可以利用這個來算出S*L的product!

-i, -j, -k 的cycle 也是大同小異, 小心處理即可

這樣求出S*L的Product後, 同樣道理, 我們找頭 i 尾 k 時, 只需要在S*4 裡面找就行了, 因為再重覆就真的重覆了... 注意尾k 的位置可能比頭i 前, 這樣也要當成失敗

很簡單吧? WA了!!!為什麼...

靠, Debug了半天...原來...

S的product除了是 i,j,k, -i, -j, -k, 1 之外 (這些我比賽時都處理了)
還可以是 -1 !!!!

-1的cycle是有不同的....這個處理後...就AC了 (在練習模式)

這個也是急住上街的後果啊...我不後悔就是了

看來我果然還是不太合適那些要一棍過定生死的玩法

難怪我喜歡自己跑去CF打練習賽 (O:

但總結來說這題比B絕對來得易...

D: (???)

看圖識字, 這種俄羅斯方塊類的題目, 看見就不想做, 也不懂做....看看幾年後有沒有興趣學習吧, 反正還有太多基本功要學了= =

總的來說, Qualification Round已經這麼難了...根本不能想像怎樣打Round 1, 要T-Shirt還要Round 2 前幾百名, 根本不太可能實現了

Codeforces Round #292 (Div. 1)

果然人一個不能兼顧太多事

增強其它方面時就荒廢coding的事了

趁還有記憶還是先寫1-2篇

這次是標題黨...因為其實我只是做了Div. 2 的C跟D,  而沒有做A跟B...

所以等於做了Div. 1的A跟B吧

(其實是Virtual Participate時按錯了...CF把Div. 2 跟Div. 1 的順序換了=.=)

這場的E,,,哦我是說Div. 1的C  我最後還是沒做到, 因為要用一個我還沒深究, 倒是發現了一個常用的技巧...等等再說一下吧

Codeforces Round #292 (Div. 1)

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

A: (Math, Greedy)

起初不知道選了Div. 1看了題目想了想已經覺得怎麼這場D2 的A好像難了點

才發現其實是D1的A...倒也不是真的很難, 如果只是要做到的話

但要證明就有點難...

題目是說有一個Function F(X), 是把X的每一個digit 作factorial 再相乘

例如 F(135) = 1! * 3! * 5! = 720

求最大的Y使F(Y) = F(X) , X為input

Y不能有0或者1作為digit

細心研究一下sample, 不難發現 4! = 4*3! = 2!*2!*3!....

所以一個"4" 就可以變成"322" 了

這樣想來, 每一個digit應該都可以這樣變成另一堆數字吧?

然後只要Greedily 地由大到小的排就ok了
比較中伏的是 9!,  開頭直覺地單數不能再拆了...但其實是"質數"不能再拆, 9是可以拆的

9! = 9*8*7! = 9 * 2! *2! *2! * 7! = 3 * 3 * 2! * 2! * 2! * 7!= 3! * 3! * 2! * 7!

所以"9"是能變為"7332"的

基本就這樣replace input的每一個digit就ok了

反倒是證明可以這樣拆是有點難 (以上都是直感就做了, 我想大部分人都是這樣過的吧)

看看Editorial 

We can prove the following lemma:

For any positive integer x, if it can be written as the form (2!)c2 * (3!)c3 * (5!)c5 * (7!)c7, there will be only one unique way.

Suppose that there exists two ways to write down x in this form, we can assume that the two ways are (2!)a2 * (3!)a3 * (5!)a5 * (7!)a7and (2!)b2 * (3!)b3 * (5!)b5 * (7!)b7.

We find the largest i such that ai ≠ bi, Then we know there exists at least one prime number whose factor is different in the two ways.

But according to the Fundamental Theorem of Arithmetic, there is only one prime factorization of each integer. So we get a contradiction.

所以簡單地說, 由於Prime Factorization 是unique的關係, 由2!, 3!, 5!, 7!組成的合成方法只有一種, 所以不用想它是否最大的問題

 B: (Graph, Greedy)

這題真是傷心的一題...看到tile cover相關的題目, 又由於近來在重看Discrete Math的notes
自然就想到去tile coverage的invariant...誰知完全沒有關係...
(其實也是有的, 但就只有知道tile coverage是一個perfect bipartite matching就可以了)

題目很直接, 問能不能UNIQUELY cover board by tiles, 如果不能cover或多於一種方法則print no solution, 不然就直接print solution

本身的想法是想先用invariant判定input的狀態能否cover
但發現糾結的問題是在於不能判定是否unique的情況...
開頭以為是一種detect cycle的變型題, 但怎想也有點問題...

所以就把思想逆轉一下, 反正unique solution的話就只有一種方法cover吧(不是廢話)
那麼就直接simulate cover的過程, greedy的cover吧

詳細地說就是以degree為BFS順序的key, degree 為1的才push進queue
不然的話就把degree減1, 這是O(E)可以完成的事
一路BFS就一路順著方向排tile

完成BFS要是沒有空位的話就是有SOLUTION了, 不然就是沒有SOLUTION
但還是不肯定是否UNIQUE的SOLUTION

這時Editorial又再次有一個想法:
要是圖不止一個solution的話, 那麼肯定有一個sub-graph是全部node的degree >= 2
這個其實跟自己開頭想的有cycle的情況很接近...
但經過幾場的Codeforces發現, 其實很多時候注意degree會方便很多...
回到題目上, 由於全部node 都 >= 2 這些node在BFS時根本不會進queue, 就是說根本不會cover到, 所以已經包括這個case了...

這題算是有點難...我自己是完全想錯方向去了...

C: (RMQ)

再利申, 這題沒做到, 做法倒是想過一下
這題要用上傳說中的Range Minimum Query!
一直都沒詳細研究這個東西, 也搞不清楚它跟Segment Tree, BIT之間的關係...
經過這題後, 好像明白多了一點...RMQ重點應該在於找出Index (位置)
不像Segment Tree或BIT都是在找Value (值)
兩者像的地方都是在於執行在"Segment"上的...但各自想找的東西好像不同...
遲點再研究下

話說這題也是optimize一些東西的題目
這兒發現了一個好像很多題目都會隱藏的一個特性...

假設題目要Maximize F(x)吧
要是可以把F(x) 寫成 G(x)+P(x),
那麼其實可以逐個擊破!
Maximize F(x) = Max(G(x)) + Max(P(x))

這個其實不是什麼難懂的東西, 就是經常沒留意...
以前中學物理也是X跟Y分開算這樣子的吧
聽Marcus說過以前他幫中大ACM中過一道題目, 好像在2D Grid找最近的廁所之類的
也是用這個技巧: X跟Y的方向是互不相干的

回來說CF的這一題, 題目要求的是
Minimize (d1 + d2 + ... + dy - 1 + 2 * hy) + (2 * hx - (d1 + d2 + ... + dx - 1))
看到了吧, 這根本是G(x)跟P(x)的樣式, 可以分開各自找Minimal的
而且這題只是在這個基礎上, 在找每一部分的Minimal時要用上RMQ而已...好像是

這個技巧我不太記得了, 但真的有印象不少題目也有隱藏, 記起來好了