TLE是Online Judge上很常见的一种错误：Time Limit Exceeded。它也是一年一度的趣味在线编程比赛，今年是首届，印度学生主办的（Link）。 说它“趣味”是因为它的题目别具一格，要求和评分标准也和普通的算法竞赛不一样，比如有比谁的代码最短的，有要把代码写成回文串的，不准代码中有空格的等等。

这次比赛的时间正好是寒假末期，我正好有时间参加，就注册了一个帐号去试了一下，发现果然是高手云集啊。

官方公布有解题报告，所有参赛代码也都在比赛完后开放。我本来也不想说最佳解法，只记一下我自己的流水账就好。其实这篇日志被我拖了很长时间了，就从“小结” 变成了“回忆录”

CODEHASH

2月10日晚上，我开始看题目，一眼看过去，标题”#ed”挺有吸引力的，实际上就是CODEHASH那道题了，要求是用程序输出自己的Hash，Hash函数是

string IPsec_v9(string a) {
        while (a.size() % 32 != 0)
                a += "IPsecV9";
        string ret = "";
        for (int i = 0; i < 32; i++) {
                unsigned v = 0;
                for (int j = i; j < a.size(); j += 32)
                        v = (v * 7 + a[j]) % 26;
                ret += v + 'A';
        }
        reverse(ret.begin(),ret.end());
        return ret;
}

程序越短越好，很容易想到用C来写这个程序：

main(){puts("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");}

应该是最短的了，但是构造puts里面的hash字符串却不容易。hash函数中有一句reverse()，就让构造这个字符串的难度又加大了。我稍微试验了一下，觉得必须要在程序中把字符串倒过来才能完成任务。下面这行是我想到的C语言中把字符串倒过来的最短的代码：

b=32;main(){while(b--)putchar("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"[b]);}

成功构造出这里的hash字符串要比上面的那段要高许多许多倍。构造出上面那段程序的hash的成功率大约是这里的十六次方（具体是什么原因，自己分析看看吧 :P）。

我自己开始很粗心，把b=32写成了b=33，多输出一个’\0’。这个错误在调试的时候观察不到，交上去总是错误，怀疑是对方的评测系统有问题，我就给TLE管理员发了一个消息，管理员很热情，让我把程序输出重定向到文件里和预期结果比较一下，我这才发现了问题。交上去的时候已经有五个人的代码比我短了，而自己一直坚持必须要有把字符串倒过来输出这个过程，又想不到更短的写法，对这题只好郁郁而终了。

PENGUIN

在我寻思着下面该做哪道题时，突然看到了我的一个好友刚交了PENGUIN这题，于是我就跟风去看那题。

这题是要输出一个字符拼成的企鹅。这个企鹅中有制表符、空格、点、下划线等11种字符，中间有连续的相同字符，很容易想到RLE压缩。这里就看谁可以压缩得更多些了，我在调试的时候发现代码中的ASCII字符超过127就很容易被编译器判错，最后我只用了安全的从空格到127的ASCII字符：

char s[]="$!(#f#(%{{q(zR(%{{g#zp#(%{{](zz4#%{{S#zzH#%{{SzzR)#%{{S47fAp#%{{I(*#5-H#I#f%{{I#*+ (+>#+*(+f%{{I#*!4+>#!>+#\\%{{I$*!$*+>#(!*$+f%{{S*!U*K(5f%{{S*K(A(_f%{{S# $A$A$K$#p(%{{S#*(}-$5z%{{S#*#!$i$I#z(%{{I(*I$A$g$z(%{{5(>{{!$p(%{{!(>{{I$p(%{q(H#{{Sz(%{g(H#${{Sz (%{](R7({!(]27'z #(%{S(\\.S$7.{+.-z*(%{SR{+#{g$-z*%{I#>#${+#{{$z*#%{?(H{?#{{!-z*%{?>#${{{S-z*%{?>{I({{+-z*(%{(#R{I#{{+-z*-%{f{I#{{+-z4#%{f{I#{{+-z4#%{$#R{I${{+-z*#$%{+(#(!*#({{{I(#z4$%{U($*#({+#{g(-!z $#%+(}K($>({{gA$f$7(%+}i($H{{SK($(*($U(%+}}($>#({{5_(.s%+$}}#($*#${{!($}}2%?}}#($*{{(-!}}7%+(}}7(!*{I(->!}}7%+}}K($42g(-\\!}}$%+$}}K!zz4!}_$%?$}}7!zz4!}K$%g$}s'R-8-z!$}-$%{5.#(}${{?\"('$U.%",b[]="x `:'\n  _.X";i,t;main(){for(;i<640;s[++i]-=32)for(t=s[i]/10;t--+1;)putchar(b[s[i]%10]);}

后来我发现大部分人都使用了我认为不安全的字符，也许他们是用gcc3.x编译的（提交时可以选择gcc3.x或者是4.x）？不过在本地没有这版本的编译器的情况下，这样提交起来调试总会不方便吧。这道题我第一次提交的时候排在第四，最后一次提交时排在第三，比赛结束时就排到十几了，看来大家都非常努力呢。

KEY

之后我就开始看第一题，KEY，是要判断一个数字的二进制形式是否回文，越短越好，同时要尽量少用C语言关键字，如果程序本身是回文的话，有额外奖励。

很容易想到循环地除以二取余数，把结果放到数组里，再用for循环从头到尾比较一下，但是这样的话程序就比较长了。循环除以二取余数的时候，可以把余数结果用不同的方向写回一个整数中，写回去的这个整数就是原数二进制倒过来的样子，和原数相等就是回文了。

为了避免for关键字， 我把所有的for都改成了函数，递归调用的形式：

c,n,m,s;
q(){n&&q(n/=2,s+=(n&1)+s);}
p(){c--&&p(puts(s^m?"NO":"YES"),q(),s=0,m=n,scanf("%d",&n));}
main(){scanf("%d",&c),p();}

让程序代码本身是回文的比较容易，把上面的程序写在了一行，然后加了双斜杠注释，把程序倒过来再写一遍就行了。上面的代码已经基本没有可读性了，但总体看来，还有很大的缩短余地。这里是得分最高的程序。

SHORTEN

按照顺序，下一个处理的是SHORTEN这道题。题目要求把一段不知道做什么的很长的程序改短，并要保证和源程序对同一输入有一样的输出。这道题给的源代码我没看明白，只是在表面上改一改，最后得分很低。很多人都在这里拿到了超过1000分，这相当于我做的五题，十分可怕 :neutral:

INPOUT

接下来是INPOUT这题，要求写程序读入固定的输入，然后给出固定的输出，当然，程序越短越好。观察一下就知道输出是把输入的字符打乱顺序，然后把某些字符替换掉，比如b换成d，p换成q等等，然后程序就写出来啦：

char s[120],n[120],r[]="dbbdwmmwpq2569WM";
l,i,t,c,k;
main() {
  while(gets(s)) {
    n[l=strlen(s)]=0;
    for(t=i=0;t<l;i=++t*2){
      c=s[t];
      for(k=0;!(k&1)&&k<15;k+=2)
        c=(c==r[k]?r[++k]:c);
      n[i<=l?i-l|1:i]=c;
    }
    puts(n);
  }
}

CLASS

再下面就是CLASS这道题了，题目要求很简单，不用空白字符、不用除号、不用#define声明一个class multiply，要求这个class含有一个mult(int a, int b)的方法，能输出a和b的乘积。裁判程序会创建一个这个类的实例，然后调用这个方法测试。

正常的程序许多地方要用到空格，比如int a，这个不难办，可以用int*a绕过去，或者可以用__typeof(int)a这样来声明。输出可以用cout<<a*b<<endl;，没有空格。问题是如何不用空白字符定义这个class，由于class不是一个确定的类型，所以不能用__typeof(class)，同样地，也不能__typeof(struct)。

在TLE讨论区官方提示说可以试试typedef，可我在查阅了typedef的各种文档，尝试了模板、匿名类等之后还不能消除typedef后面的空格。最后我发现评测系统只检查了空格、制表符和换行这三种常见的空白字符，我就把空格换成了’\f'(form feed)这个空白字符，居然侥幸地通过了 :D 最后发现还有很多人也用了这种方法通过的。尽管这样，这道题通过的也只有二十几个人，看来大家普遍玩不转C语言语法啊。

官方解答是把typedef这样用：

class{public:void*mult(int(a),int(b)){cout<<a*b<<endl;}}typedef(multiply);

其实还有一些不常用的宏可以帮忙，在sys/cdefs.h里面有这样一行：

#define __CONCAT(x,y)   x ## y

有人就用了__CONCAT(c,lass)multiply这样的写法，也能越过class后面的空格，没有用到typedef。

PRINT

这道题比较经典，要求输出程序源代码，还要根据输入数字的奇偶来选择正序或者倒序来输出程序，程序越短越好。如果程序是回文的，有额外奖励。

我想，这个要求看来是一定要把程序写成回文的了。 以前做过这样的题目，所以写出来也不是很难。要实现回文，同KEY一样，加两个除号再把程序倒过来写一遍就行了。

THINK

这里开始就是我在学校时做的题目了，这道题的名字是“Give it a try.”，于是我就先来试试吧。题目很有趣，是三段密文，需要动动脑筋猜出题目是什么才可以做。

第一段很简单，把大写字母提取出来就看到是什么了。按照第一段提示，把第二段每行的奇数位置的字符取出来，看到这样的二进制串：

1010111110001011
1000100100001001
0110100111010001
0111100111110001
0110100100111001
0110100111010001
1011000101111001
1111000111111011
......

我发现有两竖行全是1，就想这可能是ASCII字符吧，把这些二进制数取反后倒过来，再转换成ASCII字符，就看到一些有意义的字符。最后几行是这样的：

ot
e
mo
cl
eW

下面该怎么做就很明显了 第三个密文比较难，我当时没有解出来。

ARBIT

同上面的SHORTEN有点像ARBIT这个题目也是要精简代码，不过要求在同时提高运行效率。

#include<iostream>
using namespace std;
unsigned x;
unsigned f1(unsigned a,unsigned b){
        return !(a&b)?a^b:f1(a^b,(a&b)<<1);
}
unsigned f2(unsigned a,unsigned b){
        return a>=b?((b==0)?a:f2(a-1,b-1)):f2(a,0);
}
unsigned f3(unsigned a,unsigned b){
        return !a?-1:~f2(f1(~(f3(a>>1,b)<<1),-(~a&1)),b);
}
unsigned f4(unsigned a,unsigned b,unsigned c){
        return (!((min(a,b)-c)&1))?(~((!c)?(max(a,b)):((((f3(a,c)&~x)==~x)&((f3(b,c)&~x)==~x))?c:f4(a,b,c-1)))):
((!c)?(max(a,b)):((((f3(a,c)&~x)==~x)&((f3(b,c)&~x)==~x))?c:f4(a,b,c-1)));
}
unsigned f5(unsigned a,unsigned b,unsigned c){
        unsigned x=f4(a,c,c);
        return c?(((x>~x)?~x:x)<=b?f5(a,b,c-1)+1:f5(a,b,c-1)):0;
}
unsigned f6(unsigned a,unsigned b){
        return f5(a,b,a);
}
int main(){
        unsigned a,b;
        while(cin>>a>>b){
                cout<<f6(a,b)<<endl;
        }
}

这个代码就很有趣了，仔细分析化简可以发现，这些函数都可以改成非递归形式，f1(a,b)实际上就是a+b，f2(a,b)就是a<b?a:a-b，f3(a,b)是~(b==0?a:a%b)。

f4(a,b,c)有些麻烦，观察到f5调用f4时b,c是相等的，我最后把f4写成这个样子：( ( ( (b==0?0:b-gcd(a,b))+2 – ((min(a,b)-b)&1) ) /2 )&1)?~gcd(a,b):gcd(a,b)。其中gcd表示最大公约数。再往下看一些，f5中有一句(x>~x) ?~x:x，这样看来分析f4返回数的符号就没有意义了，把f4(a,b,c)直接改成gcd(a,b)就行了。

知道了这些，程序已经可以写得比较短了：

g(a,b){return b?g(b,a%b):a;}
f(a,b,c){return c?f(a,b,c-1)+(g(a,c)<=b):0;}
main(a,b){while(scanf("%d%d",&a,&b)+1)printf("%d\n",f(a,b,a));}

我还尝试着改更短一些：

g(a,b){return b?g(b,a%b):a;}
main(a,b,i,s){while(scanf("%d%d",&a,&b)+1){for(i=a,s=0;i;i--)s+=g(a,i)<=b;printf("%d\n",s);}}

后面一个版本实际上处理完全平方数会给出错误结果，但是测试数据似乎比较弱，这行代码也被通过了。

NP

NP这道题就有一些算法竞赛的味道了，要在一个有向图里面找一个最小点集，使得其他点都有连到这个点集的边。由于不要求最优解，比赛也快结束了，我就决定用贪心法解决，每次找到一个点，这个点加到点集后，可以使剩下的没有连到这个点集的点最少。后来发现结果还不错

TESTGEN

这个题是要生成NP的测试数据，评分标准在比赛时也没有确定下来，但尽可能让别人的程序在自己的测试数据下比不过自己的程序总是正确的。在这里我生成大量的混杂的数据，却保证自己的贪心法一定可以得到最优解。最后结果也挺好，似乎还在官方的解体报告中出现了一下呢。

交完了所有题目之后，我又去尝试改进SHORTEN那一题，遗憾的是学校的网络状况不是很好，比赛快结束的那两个小时，先是超时，后来连接被重置，最后域名解析失败，只好郁郁而终了:sad:

由于NP和TESTGEN的分数衡量方法要后来才能确定，比赛结束后过了好几天才出了最终排名，自己排在了第14/283，还好的位置吧。很多人只是来玩一玩，做了一两题而已，所以正式的参加人数没有283这么多。

虽然比赛时间比较充裕，大概是三天多的时间，但自己写这些程序着实消耗了不少脑细胞，又赶上中间回校的十几个小时的火车和汽车，真的需要仔细体验一下睡眠的感觉了…

总的来说，我和多数参与者一样，觉得这个比赛办得很好，我特别欣赏出题人那些很有创意的鬼点子，不知道下一届的时候能不能再见到这样有创意的题目了。不管如何，让我们拭目以待吧。