TLE比赛结束 经典题目回顾

    创意C/C++编程挑战赛Time Limit Exceeded结束,题目果然非常有创意。大家可以在这里看到比赛题目和获胜选手的代码。其中两道题很有意思,我特别喜欢。

    一道叫做Compile Error的题目要求你写一个叫做multiply的类,里面包含一个mult(int a,int b)的函数,该函数用于打印出a和b的乘积。代码中不允许出现空格、“/”和“#define”。

    第一个问题就是,定义一个类的语句是class multiply{…},这个空格要怎么避免?只要你知道typedef int foo也可以写成int typedef foo,我们就可以利用typedef来消除空格,把类的定义写成class{…}typedef multiply。但这下后面又冒出一个空格来,这个空格怎么消呢?一个巧妙的方法就是利用int typedef foo,bar的语句,把类定义语句写成class{…}typedef*foo,multiply,其中*foo是一个不会用到的类型,但是它帮助我们奇迹般地消除了一个空格。巧妙利用星号可以消除很多空格,例如我们在定义mult函数时就可以写成void*mult(…){…}。最后一个难题就是,定义函数mult(int a,int b),参数表里面的两个空格怎么办?其实办法依然很多。不少网友都用到了typeof,这样便可以把int a写成typeof(int)a了。完整的类定义如下:

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

    在gcc下,即使警告全开,下面这个程序编译时也一声不吱。

#include <iostream>
using namespace std;
 
class{public:void*mult(typeof(int)a,typeof(int)b){cout<<a*b<<endl;return(0);}}typedef*m,multiply;
 
int main()
{
    multiply foo;
    foo.mult(23,67);
}

Read more…

比比谁的代码短:TLE测试赛结束

    上次提到,我非常关注一个即将举办的另类编程挑战赛Time Limit Exceeded,这个比赛的得分算法很另类,它将根据你代码的总长度和特定字符的多少而定。在刚刚结束的测试赛中,有几个题目非常具有挑战性,参赛者提交的代码也是牛气冲天。

 
Power of 2
问题:
    输入数据含有多行,每行一个正整数。对每个数,检查看它是否是2的幂,是则输出yes,不是则输出no。
    你的程序不允许使用分号。
    规定0也是2的幂。

得分:
    S= length of code + number of whitespaces;
    score = (250000)/(S^2);

Read more…

预告:几个有趣的编程比赛

刚过完年回到家,也跟大家说一声新年快乐。
今天莫名其妙地收到一封邮件,邀请我参加felicity.iiit.ac.in举办的几个编程比赛。我看了一下介绍,这些比赛还是挺有意思的,这里向大家推荐一下。

http://felicity.iiit.ac.in/codecraft/
CodeCraft,举办了两三年了,一个传统方式的编程比赛。
测试赛:14th Feb, 6pm – 8pm IST (GMT +5:30).
正式比赛:15th Feb, 2pm – 10pm IST (GMT +5:30).

http://felicity.iiit.ac.in/~math/
MathematiKa,已经举办过一年了,这是第二年的比赛。比赛共12道数学题,你只需要提交答案即可。例如,去年的第四题叫你计算前30个正整数x使得F(x) = 5x^2 + 14x + 1是一个完全平方数。提交时,把所有30个数从小到大连接在一起即可。最大的那个x有十几位,因此这题硬算是不行的。
测试赛:12th Feb, 6pm – 9pm IST (GMT +5:30).
正式比赛:13th Feb, 2pm – 10pm IST (GMT +5:30)

Read more…

趣题:理想模型下的排序算法(上)

    当我们研究复杂度时,我们往往会将现实机器进行理想化。例如,我们说冒泡排序是O(n^2)的,这其实是不准确的。这个论断假设整数之间的比较运算是O(1)的,而事实上它们是O(log(min(|a|,|b|)))的。多数时候我们都认为这种机器模型的理想化是合理的,毕竟这让问题简化了不少,并且也能反映出算法的本质。但大家有想过吗,这个“大整数随便算”的假设其实是一个超级大漏洞,我们可以利用理想模型中的这一漏洞来作弊,获得时间复杂度更低的算法。上个月,Michael Brand在他的UyHiP里就提出了这样一个问题:假设计算机对任意大整数的赋值、四则运算、取余运算、比较运算、位运算(包括左移右移)的复杂度都是常数级别,你能否设计出一个O(n)的排序算法来?

    我非常喜欢这个题目。月初的时候我就提交了一个正确的算法。我们将用左移和加法运算把整数序列编码成一个超大整数,然后利用排序网络进行并行排序。这个算法比较复杂,你可以按照下面的思路一步一步得到这个算法。

1. 如何用位运算来取绝对值

2. 给出两个正整数a, b,不用比较运算和判断语句如何把小数赋给a,大数赋给b?
    提示:和加差除以2等于大数,和减差除以2等于小数

3. 如何利用位运算把整数序列编码成一个超大整数?
    例如把(二进制数)11, 1011, 1110, 1编码为一个数00011 01011 01110 00001

4. 如何用位运算给超大整数中的所有数同时取绝对值?

5. 给出两个超大整数a, b,不用比较运算和判断语句如何把对应位置上的小数赋给a的对应位置,大数赋给b的对应位置? 例如把
      a = 000010 000111 000100 001001
      b = 000001 001011 000011 011111
    变成
      a = 000001 000111 000011 001001
      b = 000010 001011 000100 011111

6. 如何实现奇偶移项排序

    最后,由于奇偶移项排序只有O(n)层,因此整个算法是O(n)的。

    但是,这个算法太繁琐了,不具有美观性。虽然这个算法是我自己想出来的,但我仍然很不满意。待我看了这个月Michael Brand发布的答案后,我一拍大腿,哎呀,还有一个如此简单巧妙的算法我没想到!相比之下,我的算法太复杂了,原因就在于我还没有充分挖掘到“大整数的常数级运算”的潜力。这个理想模型的假设太强大了。打开思路,放宽思维,大胆想象,从更大的尺度上来思考,我们可以得到一个简单得出奇的线性排序算法来。

Read more…

趣题:用正则表达式判断一个二进制数是否能被3整除

    我们之前已经见过了正则表达式的一些很特殊的用法。这里我们再来看一个:用正则表达式判断数的整除性。例如,下面这个表达式可以匹配01串S当且仅当S是一个可以被3整除的二进制数。

^1((10*1)|(01*0))*10*$

    如果你不信的话,不妨把下面这段代码粘贴进浏览器的地址栏,然后回车运行一下:

javascript:alert(/^1((10*1)|(01*0))*10*$/.test("1000000100"))

    被test的是516的二进制表达。516可以被3整除,因此程序返回true。你可以自己把1000000100换成其它的二进制数试试。
    但是呢,从这个正则表达式里我们竟看不出任何端倪。奇怪了,为什么这个正则表达式可以用于判断整除性?能被3整除的二进制数究竟有何规律?

Read more…