2015年5月31日 星期日

2015 Google Code Jam Round 2 參賽紀錄

  這是我打 Code Jam 的第七年了,至從參加的第三年打進 Round 3 以後,已經連續四年都有打進 Round 3,但也都在 Round 3 止步。而今年,我差點以為我在 Round 2 就要結束了。

  這場我按照順序開題,先看了第一題,題目有點長,嗯...其實向來 Code Jam 題目都很長,所以這題算短的吧 Orz,理解題意後瞬間理解這題的解法,只要 check 每個 arrow 的四個方向是否至少有一個方向也有 arrow 就行了。馬上寫完了 code, 沒有 bug Sample 一次 AC,我要不要仔細重新檢查一次 code 呢?但是 Round 2 開始 若不是拼全部小測資,penalty 並不重要,所以我就直接下載 small 的測資了。 small 的測資 correct 以後,幾乎可以相信我的 code 沒有 bug ( 除非我耍蠢陣列開太小...?) 於是我就直接下在大測資了。寫完第一題時我排第 29 名,台灣比我快上傳的只有皮皮 (peter50216) 和 shik。

  接著看 pB,乍看之下就只是個特殊的線性規劃題,這時我心裡想:這題該不會去抄個 simplex 的 codebook 就能 AC了吧... ? 但我還是乖乖走正道好了,出題者應該不希望我們使用普通的線性規劃 tool (賽後證實有人是使用 simplex AC 的)。這次我學乖了馬上在紙上列出式子,線性規劃題往往可以轉成網路流問題或是計算幾何問題,但這題的式子看起來比較向計算幾何,直覺的想法是:先使用 binary search,然後再判斷某些係數在時數區間的二維向量的線性組合是否可以組成特定向量。似乎就只是個經點問題,但我對解法沒有印象。我先想想兩個向量的 case,感覺上挺簡單的啊,若有向量和目標向量方向一樣,就直接使用該向量組成目標,否則可以決定出兩個向量使用的係數比,也不難算出至少需要多少係數。甚至連 binary search 都不用。

  之後我在想想 $n > 2$ 的 case,就是再這裡我想歪了 Orz,我想成至多只需要使用兩個向量就行了...(再次強調,這個結論是錯的)。當比賽當時我並不覺得我有想歪,於是就直接 coding,並 WA 在最後一筆 Sample,當時我這樣想:可能只是 $n > 2$ 的某些 case 我 code 有 bug,於是決定還是先傳傳看小測資。但小測資竟然 WA 掉了 @@

  之後我左看右看,都不覺得我 code 哪裡有錯,就算我 $n > 2$ 的版本有錯, $n = 2$ 的應該沒道理錯吧!!!過程中我也把 code 改成純粹的 $n = 2$ 的版本,自己測了不少測資,也還是不知道哪裡出了問題,這時心裡好焦躁。

  debug了一個小時左右,眼看比賽一個小時,我看了一下 score board,我已經落到 1500 名外了... 看起來就算我 現在去 AC 了 pC 和 pD 的小測資,也不可能進 Round 3,如果放棄 pB的話,就要在剩下的一個小時完整解決 pC 或 pD 其中一題,但看了一下目前上傳人數,似乎後面兩題都不簡單耶...,要繼續在 pB 掙扎嗎?還是要換題呢?

  我現在可是處 pB 在連小測資都過不了的狀態,但以經有 $1/3$ 以上的人都 AC 小測資了。以前幾乎不會在個人賽那麼多人 AC的題目上,毫無一點進展那麼久...,但是任何時候都沒有最蠢,只有更蠢吧?所以這時候大概放棄會比較好,於是我開始閱讀 pC。

  讀完題就覺得 flow 感很重,只有兩種語言,許多 flow 問題都是建立在只有兩種區隔上。可是我沒辦法立刻感受到它的模型建出來長怎樣。想了一分鐘以上後還是感受不出來...,嗚 QQ 我可是 ioicamp曾經的 flow講師啊 OAQ 怎麼可以敗在 flow 題上 OAQ,自從我當 flow 講師以後幾乎所有 flow 題都可以分殺 (秒殺有點太超過,所以使用分殺這個詞) 啊!好吧,重新想想我當時是怎麼教 flow 的,如果我自己教的東西都無法幫助我解題,那我算什麼講師啊!!!!

  從頭來!首先,通常題目中都會有看起來就像是可以當做網路中的點的物件,這題可以當做點的有:句子、單字。其次,列出所有限制條件,再跟據限制條件建出網路的弧,有時會為了使限制能表現出來而增加點(ex:點容量) (粗體字是當初我在上課投影片上出現的文字),這題的限制有:同一個句子是同一個語言、前兩個句子已知是兩種不同語言、若一個字被當成兩種語言會有 1 的 cost。由於 cost是在點上,所以可以相信我們建出來的 flow 模型,有必要把每個 word 拆成兩個點:入點和出點。

  接著想想 min-cut 問題的模型代表意義。「我挑完後,剩下的給你」。聽起來好蠢 = =,可是這就是我當初講義上所列的子標題,真實意義為:「min-cut 所分成的兩個點集 ,包含源點的點集是所有原點所能流到的點,而那些點所代表的東西會被歸為一類,剩下的東西會被歸為另一類」。所以我必須建出一個模型,使得除了被 cut 掉的點外,是英文的單字都會被source 連到。由於同一個 sentence 裡都是同一國語言,於是我就把有出現在相同 sentece 的 word pairs 也在當中建一條 cost 無限大的邊。

  於是我最後建出的模型由以下兩個 model 組成:


   比較特別的地方是我把建了 source -> sentence -> sink 這樣的關係,如此建邊可以確保這兩個弧恰有一個在cut裡。除此之外,第一個 sentence 我沒有把它連到 sink,同時我也沒有把 source 連到第二個句子。這樣建出來的模型,min cut 值減去 INF*(句子數-2)就是答案了。可以檢驗看看,求出來的 min cut 的確能把屬於英文的單字和句子都和 source 相連。

  這是憑我的直覺建出來的圖,實際上似乎可以不存在代表 sentence的點,取而代之的是直接把 source 連到第一個句子出現的 words,以及把第二個句子出現的 words 都連到 sink。

  submit 完這題後排名就衝進了前 500 名,我的做法正確的話那麼 Round 3 就穩住了,可是還剩下一些時間,還是繼續回來幫 pB debug 吧 Orz。再重新想想只有兩個向量的 case ... 啊!!!若兩個向量都和目標向量相同,可以兩個向量都使用哇,這麼說來... 三個向量以上的 case 我完全想錯了啦!!!再仔細想一下,發現我原本的 code 可以很容易改成讓小測資 AC,所以在最後的一些時間順手改了一下並 submit。呼 ... AC 了。看來當同一個 bug 卡太久的時候還是讓頭腦先去做點別的事後再來 debug 才會比較有效果 @@,比賽比了那麼多年還是學不了這個教訓@@
  
  比賽 ending 了,我傳的兩題大測資都有確實 AC,有真的進了 Round 3,真是好險...,差點以為我的人生要倒退走了@@

2015年5月25日 星期一

Problem Zero --- 出題是種態度

出題是種態度

出題是種態度

Description

「過去的小月是個常常寫假解 AC 後還暗自竊喜的小廢物,直到小月和球球相遇,小月才知道何謂 演算法的正義 」– 小月

大家好,我是小月,正在辛苦的出題中唷!大家可能會想「出一個 debug 的比賽不是很簡單嘛?」去 Codeforces 或一些競賽網站上找一些簡單題,看看有哪些人在短時間內從 WA 變成 AC,把那些程式碼抓下來,再複製一下測試資料,最後把題目翻譯成中文,就完成了!

這樣子就輕鬆出完一場比賽不是?過去的小月或許會這麼做,但直到了小月與球球相遇。

記得小月和球球第一次相遇是在國中二年級的暑假。那時小月匆匆忙忙地上了火車,準備遠赴台北這個大都市參加一個學術活動。 火車的門關上後不久卻又重新打開,只見一個全身散發出霸氣的人走了進來,大家都因為他帥氣的身影吸走了目光。這次是小月第一次體會到,英雄總是在最後一刻登場的涵義。

相信認識球球的人一定都心有戚戚焉,小月很高興那時有鼓起勇氣去和球球交談,在那之後也從球球身上學到許多東西。 時隔好多年的今日,和球球分開已久,但小月相信球球一定還是在世界某個角落發光發熱。

球球有一個座右銘:「演算法即正義」這同時也是球球的生活態度,小月想要把他的態度,傳達給在座的每一位。請大家原諒小月,在出題過程塞了那麼多話在題目敘述裡,小月只是希望大家能想想看球球說過的話有什麼涵義。請大家在思考題目的同時也看看小月與球球的故事吧!

在故事開始前,先給大家看看球球給小月的第一個教訓:「若平常習慣靠些偷吃步 AC,在關鍵時刻遇到擁有演算法的正義的出題者時,一定會後悔莫及。」例如小月以前在寫最遠點對的問題時,都會先使用凸包模版刷掉一些不須要考慮的點,之後直接枚舉所有點對計算距離。因為小月在還未與球球相遇前,總是相信大多數出題者測資大概都隨便亂生吧。球球在知道這件事後,立刻給小月一個當頭棒喝,生出了一個讓小月 TLE 的測資。

請大家重現球球當初對小月做的事吧!

Original Description

給 $N$ 個平面座標上的點,請求出當中相距最遠的兩個點的距離。為了方便起見,請輸出距離的平方。

Original Input Format

測試資料共有 $N + 1$ 行。第一行有一個正整數 $N$,代表平面上點的個數。 接下來的 $N$ 行,每行有兩個整數 $x_i$, $y_i$,代表第 $i$ 個點的座標是 $(x_i, y_i)$。

  • $2 \le N \le 1,000,000$
  • $−10^9 \le x_i,y_i \le 10^9$

Original Output Format

 對於每組測資輸出一行答案,最遠點距離的平方。

Sample Input

範例 1

2 
0 0 
10 0

範例 2

4
-1000000000 -1000000000 
-1000000000 1000000000
1000000000 -1000000000
1000000000 1000000000

Sample Output

範例 1

100

範例 2

8000000000000000000

Hacked Program

//bcw0x1bd2 {{{
#include<bits/stdc++.h>
using namespace std;
#define FZ(n) memset((n),0,sizeof(n))
#define FMO(n) memset((n),-1,sizeof(n))
#define MC(n,m) memcpy((n),(m),sizeof(n))
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define FOR(x,y) for(__typeof(y.begin())x=y.begin();x!=y.end();x++)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
// Let's Fight! }}}

const int MXN = 1000005;

struct Point{
  typedef long long T;
  T x, y;

  Point() : x(0), y(0) {}
  Point(T _x, T _y) : x(_x), y(_y) {}

  bool operator < (const Point &b) const{
    return tie(x,y) < tie(b.x,b.y);
  }
  bool operator == (const Point &b) const{
    return tie(x,y) == tie(b.x,b.y);
  }
  Point operator + (const Point &b) const{
    return Point(x+b.x, y+b.y);
  }
  Point operator - (const Point &b) const{
    return Point(x-b.x, y-b.y);
  }
  T operator * (const Point &b) const{
    return x*b.x + y*b.y;
  }
  T operator % (const Point &b) const{
    return x*b.y - y*b.x;
  }
  Point operator * (const T &b) const{
    return Point(x*b, y*b);
  }
  double abs(){
    return sqrt(abs2());
  }
  T abs2(){
    return x*x + y*y;
  }
};

long long cross(Point o, Point a, Point b){
  return (a-o) % (b-o);
}
vector<Point> convex_hull(vector<Point> pt){
  sort(pt.begin(),pt.end());
  int top=0;
  vector<Point> stk(2*pt.size());
  for (int i=0; i<(int)pt.size(); i++){
    while (top >= 2 && cross(stk[top-2],stk[top-1],pt[i]) <= 0)
      top--;
    stk[top++] = pt[i];
  }
  for (int i=pt.size()-2, t=top+1; i>=0; i--){
    while (top >= t && cross(stk[top-2],stk[top-1],pt[i]) <= 0)
      top--;
    stk[top++] = pt[i];
  }
  stk.resize(top-1);
  return stk;
}

int main(){
    int N;
    while (~scanf("%d", &N) && N){
        vector<Point> ip, ret;
        for (int i=0,x,y; i<N; i++){
            scanf("%d%d", &x, &y);
            ip.PB(Point(x,y));
        }
        ret = convex_hull(ip);
        long long ans = 0;
        for (auto p1 : ret)
            for (auto p2: ret)
                ans = max(ans, (p1-p2).abs2());
        printf("%lld\n", ans);
    }
    return 0;
}

Judge Method

請構造出一組測試資料,使得使用上述程式碼凸包後,點數仍至少有 $1,000,000$ 個點。

Sample Program

以下程式碼能產生本題合法但不一定 AC 的測試資料

#include<cstdio>
#include<cstdlib>
#define LL long long
const int MAX = 1000000000;
LL myrand(){
    LL res = ((LL)rand()<<48)^((LL)rand()<<32)^((LL)rand()<<16)^rand();
    if(res<0)res=-(res+1);
    return res;
}
int main(){
    int N = 1000000;
    printf("%d\n",N);
    for(int i=0;i<N;i++){
        printf("%d %d\n",(int)(myrand()%(2*MAX+1)-MAX),(int)(myrand()%(2*MAX+1)-MAX));
    }
    return 0;
}

2015年5月14日 星期四

Kirino in Google Code Jam

最近有種一直在測試各種比賽題目的感覺。而就在今天,我幫忙了一個學長辦一場私人比賽,也就是只前某篇 BLOG 裡提到的飲料盃

在飲料盃裡,我幫忙提供了其中兩個題目,這兩題和一般的競賽題目不同,是屬於 challenge 類型的,也就是題目裡會告訴你某個題目以及給你該題目的 code,你要想辦法生出一組該 code 會 fail 的測資。這很類似在比 Codeforces 和 SRM 時,使用generator 升測資 hack/challenge 別人。

在這裡我放上兩題中的一題,要 challenge 的 code 是我今年 code jam AC 了大小測資的 code。

題目連結

這裡說說這題目出現的來由:

今年 code jam 1A 結束不久後,我在別人的網誌上看到對方閱讀了我的 code 覺得不錯,對此我感到驚恐,因為我有些地方並沒有寫的很確定,深怕別人看了我的 code 後會有所誤會。在仔細思考後,確認了我的 code 確實有誤,於是決定把他出成題目,警惕大家不要看著 id 就隨隨便便相信其他人的 code,也不要太輕易的相信在別人 BLOG 裡看到的解法,請務必自己認真想過一遍 >_<

網路上的資源實在是太多了,但究竟有多少東西是可以相信的呢?我從今從網路看過很多人把自己的在某 Judge 或某比賽的 AC code 貼出來,發現其實錯誤率還蠻高的,真心覺得這件事很恐怖 @@

現在這場比賽還在進行中,等比賽結束我在聊聊這題的解答吧 XD

2015年5月7日 星期四

Codeforces Round #302 參賽紀錄

這場的配分比較奇怪:500-1000-1750-1750-2500
看來這場的難度配置不單純 0.0

  開場先看了 pA,把他列成式子會是一個多元一次不等式的整數解個數的問題,這類的問題一般來說都是使用 dp 做,於是就很直覺的寫了一個 dp。寫到一半發現不對,照感覺寫下去會是 $O(n^4)$,稍微多想了幾秒後,發現他是個另類前綴和類型的 dp,所以複雜度可以少一個 $n$。唔... 這樣的題目在 Div. 1 A 裡面算難吧... ?

  接下來看了 pB,題目包裝的有點隱晦,題目說到要破壞盡量多的路...,立即閃過去的概念是 min-cut 問題,可是明顯不對 = =。馬上把他反過來想,破壞盡量多的路 = 保留盡量少的路,保留盡量少的路...其實就是求兩組點對的最短度?不對不對他們可能會有共用的路,所以要分兩個 case:兩組點對的最短路沒有相交,以及兩組點對的最短路交纏在一起。交纏在一起的話... 根本就是四個點的 steiner tree 問題吧...,三個點或四個點的 steiner tree 問題我看過好幾次了,所以這題和那些題目的差別就只在於多了點對間的路徑還有不能超過某個長度的限制,但這個條件還挺好判掉的。 這題的 code 感覺上有點長唉 ...,思考了幾秒要不要先看其他題,但最後還是決定先把這題寫完。

  寫完 pB,我 lock 了 pA,大略的看了一下大家的 code,感覺都很正常,本來還以為說不定有人會寫 O(n^4)的做法 0.0 看來 pretest 大概有擋調。

  接著看到 pD submit 的人比較多,所以我就先看了 pD。pD 題目很好理解,而且他看起來就很像常見的 dfs 兩次的 tree dp 問題(第一次只 dp 出每個 node 的 subtree 的某些性質,第二次在 dp初以每個點當 root的題目要求的性質),我就靠直覺寫下去了。

  寫完 pD 後, pC 還是只有少量的人 submit,難道說他不簡單嗎>_<,於是我先 lock了一下 pB,先 cha 一下看看,因為這題一副就很容易寫錯的樣子。開了幾份 code 後看到有人漏了一個 case (很容易看出來,因為他 code 比別人少了一部分),賺了 100 分!

  讀了 pC,第一個想到的是,每個字串一定可以靠著改變任一字母來達到題目要求,但,之後呢?這是 min-cost 類 flow 題嗎?感覺不像,要不然 $n、m$ 要更大才對?先想一下還有什麼 case 會讓某些字串滿足條件。若有某個位置,有 $k$ 個字串在該位置有相同字元,那我們就可以改變當中 cost 最小的 $k-1$ 個字元,使得這 $k$ 個字元都變的不一樣!於是,我們可以掃過 input 後得到好多 $1 \sim n$ 的 subset 以及對應的 cost,代表我要讓這個 subset 編號的字串們都滿足條件至少要多少 cost。到這裡,以經可以確信這題是位元 dp 問題了,但實際上究竟要怎麼 dp?好為難喔...,回憶眾多記憶中的位元 dp 方式都不對,如果對於每個 set 子集,都還要枚舉該子集的子集,複雜度太高了。但沒必要枚舉到子集的子集吧?只要枚舉一些重要的子集就好了。這部份我想的有點久 ... 最後總算注意到,所有的 (子集, cost ) 的對數至多才 400 對!$400 * 2^{20}$ 約為 $4*10^8$,常數小小的,以 Codeforces 的主機來說應該輕鬆 AC 吧 XD 許久以前也看過類似的題目,不過記憶模糊了 0.0。

  在寫 pC 快寫完的時候, pD 竟然被 cha 掉了!?為什麼?我哪裡忘記 mod 了嘛?但後來看到 scoreboard 上大家被 cha成一片,可以相信這不是 mod 的問題,我暫時先把 pC 擱著,想了一陣子 pD 到底發生了什麼事。最後注意到,我 dfs 第二次時,有用到模逆的操作,難道說被構造了運算中會有 0 的模逆而造成不可預期的事態?唔...想到這裡,就決定暫時放棄解決這個 bug,先把 pC 寫完。

  submit 完 pC 後,在認真回來想想 pD,先試著想想要構造出能 hack 這樣的 bug 的測資是否很困難,但腦袋有點鈍鈍的,無法清楚思考要怎麼構造。不管啦,先回來看看我要怎麼修掉這個 bug,然後才發現我原本的 dp寫法並不太好 ...,超難修 bug的啊!後來就把整個 dp 的部分重寫了 ... 由於要修的部分太多,所以我沒有在時限內修正完成  OAQ

   賽後問了一下學弟,pD cha 了那麼多份 code 確實是依靠我賽中想到的那個 bug cha 的,賽後我大概又花了約五分鐘把這個 bug 修補完成並 AC。最後 rank 37,以目前我的 rating rank,這樣的名次還是足以讓 rating 增加 84,若能維持這樣的 rating 增加率,要回到至高點還需要三場!