Wenbin Dai's Space

For Ubuntu 9.04 (Jaunty) Users use the following procedures

sudo wget http://www.medibuntu.org/sources.list.d/jaunty.list --output-document=/etc/apt/sources.list.d/medibuntu.list

Then, add the GPG Key using the following commands

sudo apt-get update

sudo apt-get install medibuntu-keyring

sudo apt-get update

For i386 Users install Codecs using the following command

sudo apt-get install w32codecs libdvdcss2

For amd64 Users install Codecs using the following command

sudo apt-get install w64codecs libdvdcss2

http://www.topcoder.com/stat?c=problem_statement&pm=6017&rd=8083

一道很好的题目，有几个tricky的地方需要注意：

1）对于[0,k][0,k]内的任一点(x,y)，该ray等同于(0,0)到(x%r,y%c)的ray。如果用brute-force枚举，即便用了KMP也会超时。

2）对于水平和竖直方向的ray，不要hard-code加到要考虑的list里面（考虑grid为{"a"}这样的情况），还是用gcd来判断。

3）用KMP而不是brute-force做string-match。

int gcd(int a, int b) {
    while (b != 0) {
        a %= b;
        a ^= b ^= a ^= b;
    }
    return a;
}

vector<vector<int> > suffixes;

vector<int> BuildSuffix(string pattern) {
    int lp = pattern.length();
    vector<int> pi(lp, -1);
    int k = -1;
    FOR(q,1,lp-1) {
        while (k >= 0 && pattern[k + 1] != pattern[q]) k = pi[k];
        if (pattern[k + 1] == pattern[q]) ++k;
        pi[q] = k;
    }
    return pi;
}

bool StringMatchKMP(string text, string pattern, vector<int> suffix) {
    int lt = text.length(), lp = pattern.length();
    int k = -1;
    REP(i,lt) {
        while (k >= 0 && pattern[k + 1] != text[i]) k = suffix[k];
        if (pattern[k + 1] == text[i]) ++k;
        if (k == lp - 1) return true;
    }
    return false;
}

int cnt[40][40];

class InfiniteSoup {
public:
    vector <int> countRays(vector <string> g, vector <string> words, int k) {
        int r = g.size(), c = g[0].length();

        suffixes.clear();
        REP(i,words.size()) suffixes.push_back(BuildSuffix(words[i]));

        memset(cnt, 0, sizeof(cnt));
        FOR(i,0,k) {
            FOR(j,0,k) {
                if (gcd(i, j) == 1) ++cnt[i % r][j % c];
            }
        }

        vector <int> res(words.size(), 0);

        REP(i,r) {
            REP(j,c) {
                if (cnt[i][j] > 0) {
                    string str = "";
                    int tr = 0, tc = 0;
                    do {
                        str += g[tr][tc];
                        tr = (tr + i) % r, tc = (tc + j) % c;
                    } while (tr || tc);

                    string t = str;
                    REP(k,50) t += str[k % str.length()];

                    REP(k,words.size()) {
                        if (StringMatchKMP(t, words[k], suffixes[k])) res[k] += cnt[i][j];
                    }
                }
            }
        }

        return res;
    }
};

1. My heroism and idealism.

2. It's a simple world, good is good, bad is bad.

3. Even if we're so small to understand why, we can change the world.

4. Love, courage, loyalty, faith.

下面的代码计算Euler's Totient function。

#define MAXN 10000000

int mm[MAXN + 5];

void run() {
  FOR(i,2,MAXN-1) mm[i] = i;
  REP(i,pcount) {
    int p = plist[i];
    for (int s = p; s < MAXN; s += p) {
      mm[s] = mm[s] * (p - 1) / p;
    }
  }
}

其中pcount表示小于MAXN的素数的个数，plist则存储了这些素数。

代码looks good，但是仔细一看就会发现，虽然单个Int32的phi值是小于它自己的（这里的最大值是10^7所以看起来没问题），但是中间那一步计算

mm[s] = mm[s] * (p - 1) / p;

却有可能中间值溢出，导致最后的结果错误，改成下面酱紫就okay了

mm[s] = (LL) mm[s] * (p - 1) / p;

阿森纳球迷可以容忍球队一年只赢两场球：一场是主场对曼联，一场是客场对曼联。

今天的比赛可以说是困难重重，阿德巴约、范佩西都不能上。不过窃以为范佩西不上反而倒是好事。

开场阿穆尼亚就手接回传球违例，被罚禁区内间接任意球，还好曼联射的也不咋的。然后第8分钟又几乎被曼联搞进去，幸好贝托越位进球无效。被打了两拳，厂队终于站稳脚跟，开始提出华丽的传接球。也亏的是曼联这种级别的对手，不会缩在后场打铁桶阵，大家放开了手脚踢对攻，厂队是不惧任何对手滴。于是有了两次极有威胁的边路传中，可惜小本子虽然很努力，还是与进球差之毫厘。不过此时就看出，纳斯里今天状态极佳，在曼联后场突来突去，游刃有余啊。

终于22分钟打破僵局，小法任意球被贝托解围，纳斯里禁区左路施舍，打中加里内维尔折射入网，1：0。但之后形式倒有点危险，加拉斯和萨尼亚先后吃到黄牌，C罗禁区左侧任意球又险些造成克里希乌龙。终于好不容易挺过上半场。

下半场开场纳斯里又给大家一个惊喜，小法中路妙传，纳斯里赶在维迪奇封铲前暴射入网，看得那叫一个爽啊。以后我厂都这么打就好了，不要老是想的要把球带进球门才作数。后面就开始处于守势了，但是反击也打得曼联很头疼，解说说的好，小法传球的那不是脚，是刀。中间阿穆尼亚英勇负伤，法比安斯基粉末登场，不过90分钟时被曼联小将拉斐尔打进一记漂亮进球。

然后裁判给出6分钟补时！不是不能超过5分钟的么！不过好歹挺过去了，继续保留夺冠希望。

纵观全场，纳斯里攻防有度，而且心理素质极佳，号称齐达内接班人并非浪得虚名啊。小法一如既往的组织全队，送出威胁球。小本子很努力，头球也有一定威胁，但脚下功夫确实糙了点，几个门前的准单刀换成大帝都不知道打进几个了。迪亚比给人眼前一亮的感觉，控球很好很稳啊，我还一直以为是糙哥呢。小老虎今天踢得一般，不过也至少保持对对方的冲击。阿穆开场脑子迟钝了，而且丫确实太小心了，不敢出击，不过英勇负伤了，大家还是给点掌声吧。还有要说的是萨尼亚的边路传中太烂了吧，换成埃布可以提两个档次了。

PS: This game began in incessant rain and ended in bright, brilliant sunlight.

http://www.topcoder.com/stat?c=problem_statement&pm=10123&rd=13513&rm=299010&cr=8347577

一道挺有意思的题目，也蛮tricky的，我在写的时候就想偏了一点，虽然过了sample数据，最后还是被人cha了 :(

题目从经典的过桥问题派生过来，只是限制更多了：

• 只有一张地图，所以全部人过去之前每次要有若干人把图带回来
• 桥的承受重量有上限
• 每次过桥的一个小组里面，每个组员至少信赖一个其他组员（一个人过桥时不受这个限制）、
• 求最短的过桥时间（一组人过桥时间按最慢的那个人算）

我第一眼看去就是一个Bit DP，给的人数上限（13）也基本符合TC的习惯。但是写的时候想偏了。我假设除了最后一次，每次至少有两个人过桥，然后从中选一个人回来。这里有一个致命的逻辑错误。考虑3个人，相互之间都互相信赖的情况。3个人体重分别为3、3、6，而桥承受重量的上限为6。那么必须是首先两个体重3的人过去，一个人拿地图回来，然后体重6的人单独过去，另一个体重3的人回来，最后再两个体重3的人一起过桥。昨天晚上我还以为自己是超时挂了，和magicpig讨论时也没有发现自己逻辑上的错误。

因为可以出现一人过桥再一人回来的情况，DP在这里按我理解就不太适用了，因为情况会变得复杂（考虑一个人过桥然后又自己跑回来的情况）。这个和前几周在组里做的一个token nested replacement的情况有点类似，但那个显然要简单许多了。在这种情况下，BFS应该是一个合适的解法。

人的状态总共是2^13，考虑地图在左边还是右边再乘以2，总的时间复杂度是2^14。magicpig昨天提到的2^26的复杂度应该是可以简化的。因为知道了桥左边人头的情况，右边的可以相应的算出来。

对于每一个状态，有3个东西需要记录，地图在左还是在右，当前桥左边的人头状况，该状态与目标状态（人全在桥右，地图也在右）的距离。每次过桥时都是枚举可以过桥的人的所有组合。后面就是一个典型的BFS的PQ实现了。

附代码如下：

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define MAXN 13
#define INF 1000000000

class state {
public:
    int mp, mask, dist;
    state(int _mp, int _mask, int _dist) : mp(_mp), mask(_mask), dist(_dist) {};
    bool operator<(const state &rhs) const {
        return dist > rhs.dist;
    }
};

int n, bs, full, gt[1 << MAXN], mm[2][1 << MAXN];
vector<int> weight, tt;
vector<string> trust;
priority_queue <state> pq;

void init() {
    memset(gt, 0, sizeof(gt));
    gt[0] = INF;
    FOR(m,1,full) {
        int wtot = 0;
        REP(i,n) if (m & 1 << i) {
            wtot += weight[i];
            gt[m] = max(gt[m], tt[i]);
        }
        if (wtot > bs) gt[m] = INF;
        if (m & (m - 1)) {
            bool fl = true;
            REP(i,n) if (m & 1 << i) {
                int mk = false;
                REP(j,n) if ((m & 1 << j) && i != j && trust[i][j] == 'Y') {
                    mk = true;
                    break;
                }
                if (!mk) {
                    fl = false;
                    break;
                }
            }
            if (!fl) gt[m] = INF;
        }
    }
}

int doit() {
    memset(mm, 127, sizeof(mm));
    mm[0][full] = 0;
    pq.push(state(0, full, 0));
    while (!pq.empty()) {
        state cur = pq.top(); pq.pop();
        int dist = cur.dist, mp = cur.mp, mask = cur.mask;
        if (dist > mm[mp][mask]) continue;
        int s = mp == 0 ? mask : (mask ^ full);
        for (int m = s; m > 0; m = m - 1 & s) {
            if (dist + gt[m] < mm[1 - mp][mask ^ m]) {
                mm[1 - mp][mask ^ m] = dist + gt[m];
                pq.push(state(1 - mp, mask ^ m, mm[1 - mp][mask ^ m]));
            }
        }
    }
    return mm[1][0] < INF ? mm [1][0] : -1;
}

class CavePassage {
public:
    int minimalTime(vector<int> travelersWeights, vector<int> travelersTimes, vector<string> trustTable, int bridgeStrength)
    {
        n = travelersWeights.size();
        full = (1 << n) - 1;
        bs = bridgeStrength;
        weight = travelersWeights;
        tt = travelersTimes;
        trust = trustTable;

        init();
        return doit();
    }
};

早上起来，背了三本书（C++标准程序库、LRJ黑书、具体数学）就直奔G公司在清华科技园的大楼。

偶遇开复

在G公司一层领了狗牌后，坐电梯到6层。结果发现要门禁卡才能进到里边。这时两边也没有人，等了一会，终于有人上来了，发现竟然是开复，就让他帮我刷开了门，HAHA。

准备活动

到了比赛场地先setup机器。每人一个24寸的大液晶还是挺爽的，强烈呼吁MS也升级到24寸宽屏啊。旁边一人惊呼，3G内存啊，好爽。偶组里用的都是18G内存的server，没感觉。。。现场见到很多老朋友，坐在我对面的清华的OpenGL大牛，06年San Diego后又见了，看来作为是按名字字母序排的，两个“文彬”又放在了一起。旁边的是skatou，还是老样子，穿了个拖鞋就来了。。。过了一会又来了两个浙大的师弟，又是拖鞋。。。过了一会，ob、沈老师、lyt也出现了，都是作为工作人员。于是准备活动变成了大家聊天叙旧。同时还瞻仰到了ACRush、Savior、熊猫教主等偶像。

BT的xReborner

早就耳闻复旦的CSX很怪，非常BT。问skatou，盖头说，那哥们进来后，开了个浏览器，然后就敲上baidu主页，放在那。。。-_-

赛前花絮

11点半比赛，就要开始的时候，两阿姨推了一车饭过来，停在我的座位前不远。我想这下郁闷了，平常这都是吃饭的点，没的吃也就罢了，还要被诱惑，郁闷。

还有机器的摆放非常搞笑，每个人身边的主机其实是对面选手的。所以插U盘啥的都得让对面的人帮忙。组委会还特别提醒：大家重启时一定要注意啊，别把别人机器的电源给摁了。。。

比赛过程

这次题目的区分度还是不是太好。我先做的A，刚开始状态不行，繁琐的做法想了很久。后来还是清醒了下，换了一种思路，才搞定。这时看ranklist，D的小数据过的人挺多，一看，小数据permutation一下就可以，于是先把这个搞定。不过大数据就想不出来了。转看C，概率题，呵呵，后半程比赛全耗在这了，不过也没搞出来。亚洲区180人吧，1/5就是36个紧急名额。结束时排在56（最后跑完全部测试后升到51），实力确实有差距，也没啥遗憾的。

杂

然后和skatou、ob、沈老师、lyt一起午饭。饭后后三位就嚷着要去午觉了，汗。我就和skatou在G公司楼里到处转了下，找到如下qs：xuchuan、金帅哥，miss掉如下qs：bm、mp、smell。不得不说，G公司内部的办公环境还是很棒的，期望俺们新盖的大楼。

结束

参观完毕，听了某人机器学习讲座一个，听组委会宣布了晋级名单，马上匆匆赶回公司（还好就两步路），去赶偶的commitment啊。。。

Find the sum of all eleven primes that are both truncatable from left to right and right to left.

DFS搜即可，但是其实搜之前是不确定所有的值一定在Int32的范围内，所以先是用long long 来判断（当然如果有值超出了long long的范围就得用另外的做法了）。从左往右搜，所有的值都只可能由2、3、5、7之一开始，后面的值可以跟1、3、7、9 （其他的数都会制造出合数）。然后一边搜一边判断就可以了。

/**
 * Problem: Find the sum of all eleven primes that are both truncatable from left to right and right to left.
 * Algorithm: DFS
 * Author: daiwb
 * Date: 2008/08/31
 */

#include <iostream>
#include <sstream>
#include <set>
#include <cmath>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
typedef long long LL;

int res;
int num[4] = {1, 3, 7, 9};

int string2int(string str) {
  stringstream ss;
  ss << str;
  int res;
  ss >> res;
  return res;
}

bool isprime(int val) {
  if (val == 2 || val == 3 || val == 5 || val == 7) return true;
  if (val == 1) return false;

  int mid = (int)sqrt(val + 0.5);
  if ((val & 1) == 0) return false;
  for (int i = 3; i <= mid; i += 2) {
    if ((val % i) == 0) return false;
  }
  return true;
}

bool isok(string str) {
  if (str.length() == 1) return false;

  REP(len,str.length()) {
    string s = str.substr(len);
    if (!isprime(string2int(s))) return false;
    s = str.substr(0, len + 1);
    if (!isprime(string2int(s))) return false;
  }
  return true;
}

void dfs(string str) {
  stringstream ss;
  ss << str;
  int val;
  ss >> val;
  if (!isprime(val)) return;

  if (isok(str)) {
    res += val;
  }

  REP(i,4) dfs(str + char(num[i] + '0'));
}

void run() {
  res = 0;
  dfs("2");
  dfs("3");
  dfs("5");
  dfs("7");
  cout << res << endl;
}

int main() {
  run();
}

Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.

数据量不是很大（one million以下），暴力做即可。一点小trick就是偶数的二进制表示肯定是类似于1...0，所以必然不是对称的，可以略去。

/**
 * Problem: Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.
 * Algorithm: Brute Force
 * Author: daiwb
 * Date: 2008/08/31
 */

#include <iostream>
#include <sstream>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
typedef long long LL;

bool isPal(string str) {
  int len = str.length();
  REP(i,len >> 1) {
    if (str[i] != str[len - 1 - i]) return false;
  }
  return true;
}

bool isPalDec(int val) {
  stringstream ss;
  ss << val;
  string str;
  ss >> str;
  return isPal(str);
}

bool isPalBin(int val) {
  string str = "";
  do {
    str += char((val & 1) + '0');
    val >>= 1;
  } while (val != 0);
  return isPal(str);
}

void run() {
  int res = 0;
  for (int i = 1; i < 1000000; i += 2) {
    if (isPalDec(i) && isPalBin(i)) res += i;
  }
  cout << res << endl;
}

int main() {
  run();
}

How many circular primes are there below one million?

小于one million的数实际上只有6位，而且考虑到大于9的circular prime number只可能包含1、3、7、9 （如果包含0、2、4、5、6、8那么循环过后就会被2或者5整除）。简单的做法就是判断出one million以内所有的数是否为素数（很快，都不用用+2，+4筛法），然后用dfs搜索所有1、3、7、9组成的数加以判断即可。

/**
 * Problem: How many circular primes are there below one million?
 * Algorithm: DFS
 * Author: daiwb
 * Date: 2008/08/31
 */

#include <iostream>
#include <sstream>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
typedef long long LL;

int plist[80000], pcount = 0;
int mm[1000005];

int prime(int n){
  int i;
  if ((n!=2&&!(n%2))||(n!=3&&!(n%3))||(n!=5&&!(n%5))||(n!=7&&!(n%7)))
    return 0;
  for (i=0;plist[i]*plist[i]<=n;i++)
    if (!(n%plist[i]))
      return 0;
  return n>1;
}

void initprime(){
  memset(mm, 0, sizeof(mm));
  int i;
  mm[2] = 1;
  for (plist[pcount++]=2,i=3;i<1000000;i++)
    if (prime(i)) {
      plist[pcount++]=i;
      mm[i] = 1;
    }
}

int res, len;
int num[4] = {1, 3, 7, 9};

bool isCircularPrime(string str) {
  REP(i,len) {
    stringstream ss;
    ss << str;
    int val;
    ss >> val;
    if (mm[val] == 0) return false;
    str = str.substr(1) + str[0];
  }
  return true;
}

void dfs(int idx, string str) {
  if (idx == len) {
    if (isCircularPrime(str)) {
      ++res;
      cout << str << endl;
    }
    return;
  }

  REP(i,4) {
    dfs(idx + 1, str + char(num[i] + '0'));
  }
}

void run() {
  res = 0;

  // 1-9
  res = 4;

  for (len = 2; len <= 6; ++len) {
    dfs(0, "");
  }

  cout << res << endl;
}

int main() {
  initprime();
  run();
}