出了一道好题目却不知道该怎样投递到各大OJ上？现在不用担心这个问题了，因为你可以直接把自己的Blog变成一个OJ。Scarky是一个建立在SPOJ系统上的OJ平台。所不同的是，任何人无需注册便可以编写自己的题目并发在自己的网站上与网友分享，并且网友们提交答案时也不需要进行注册。这个网站的功能还在不断扩充中，但目前就Programming Challenge模块看来，这个网站已经很强大了。以后我有了好题目就用这种方式和大家分享了，这里先试用一下，题目来源好像是某次USACO月赛。

在网上偶然看到这篇文章，决定把之前创作排序算法内存状态演示图所用的Mathematica程序修改一下，于是搞出来5个midi音乐。这些midi文件用音高来表示内存状态，初始时的音都是乱的，然后声音渐渐变得有序，最后就成了从低到高的一串音符。

http://www.matrix67.com/data/bubble_8_elements.mid
http://www.matrix67.com/data/insert_8_elements.mid
http://www.matrix67.com/data/select_8_elements.mid
http://www.matrix67.com/data/quick_12_elements.mid
http://www.matrix67.com/data/bogo_6_elements.mid

哪位兄弟能推荐一个在线放midi文件的好方法？

    大学生活混起来很快，不知不觉又是一年过去了。去年5月10日的ACM校内赛给我留下了许多美好的回忆，因此今年我主动去报了名（上次是被人给拖去的）。今年有点装怪，题目数量不变，但时间缩短为4个小时。原计划是从8:00做到12:00，结果可能是因为我们所在的7号机房迟迟没有开门，时间临时改成了8:15到12:15。总的来说，今年的题目比去年要糟糕得多，但也不乏一些精彩的题目。

    和去年一样，第一题依旧是所有题目中最科学的一道。题目给定一个不超过2000*2000的网格，你在最左下角的位置（即(0,0)点），你的目的地在(x,y)。要求你的路线不得经过同一个交叉点两次，且不允许左转（题目背景让这个条件顺理成章：街道靠右行，左转不方便），问合法的路线共有多少种。题目难点就是你不一定要走最近的路，完全允许你绕上一大圈；这破坏了有序性，很难构造出递推公式或动态规划模型。稍微画一下图，我们发现了一些显然但很有启发性的规律：每一次右转后，你左手边方向的所有区域都不能再走了，这很可能产生出规模更小的子问题来。另外，所有合法路线必然是有如螺旋线一样的一圈一圈绕着终点走，这种隐藏的有序性也为动态规划提供了可能。但顺着这个思路想下去屡屡碰壁，我猜不少队伍都卡在这儿了吧。

    后来我完全打翻前面的全部思路，猛然想到了一个具有决定意义的想法：街道的选取唯一地决定了整个路线。例如，假设我想计算转弯恰好11次的路线有多少条。这样的路线一定含有三条向上走的路、三条向右走的路、三条向下走的路和三条向左走的路。除去第一条路和最后一条路的位置都是确定的，其它的路选在哪一行或者哪一列唯一地决定了整个路线。因此，我们可以用排列组合直接计算出答案来。向上走的路是五选二，向右走的路是七选三，向下走的路是四选三，向左走的路是三选二。把它们各自的选取方案数乘起来就得到了拐弯11次的合法路径。于是，计算所有的路线数只需要从小到大枚举拐弯的次数，每一次计算都是常数的，总复杂度是O(n)的；整个算法的瓶颈反倒是O(n^2)的组合数预处理，不过这个复杂度完全可以承受。

查看更多 »

    昨天和老朋友BY一起吃饭时又一次不可避免地谈到了算法问题。一个有趣的话题是：提起那些最巧妙的、最离奇的牛B算法时，你想到的第一个算法题是什么？

    我第一想到的算法题是那道经典问题：n个数中有且仅有一个数出现了奇数次（其它数都出现了偶数次），如何用线性时间常数空间找出这个数。解法也只有一句话：从头到尾异或一遍，结果就是要求的那个数。该问题的加强版也异常牛B，我曾经在这里介绍过。不过，这个算法我在茶余饭后已经聊过无数次了……

    脑海中出现的另一个牛B算法题则是POJ3318：给你三个n*n的矩阵A、B、C，问你A*B是不是等于C。数据保证O(n^3)铁定超时，因此你需要想一个不用把A和B乘起来就可以验证的算法。一个基于概率的算法是随机生成一个n乘1的矩阵R，然后判断A*B*R是否等于C*R，而前者相当于A*(B*R)，与后者一样都可以在O(n^2)的时间里算出来。如果算出来的结果相等，几乎可以肯定A*B和C也是相等的。

查看更多 »

    今天我又干牛B事情了……听说三教有Google的实习生招聘笔试，再想到传说中Google笔试里的牛题，我毫不犹豫地就杀去了。说实话，我倒真没想认真做题，只是过去看一看传说中的Google笔试题是什么样子的。由于我什么都没准备，连事前是否要报名都不知道，因此呢，与其说是“处女笔”，倒不如说是一次“霸王笔”。BBS上说要带简历和成绩单，于是打印了一份巨牛无比的“简历”和很不像话的成绩单。
    考试时间19:00-20:30，来自各个学校的人几乎坐满了整整一层楼的教室。两个挂着工作牌的MM进来，给每个人发了一张质量巨好的草稿纸和一个用来把试卷、简历、成绩单固定在一起的曲别针。试卷很厚一叠。选择题很简单。编程题没看（最讨厌在纸上写代码了）。算法题很有意思，和大家分享一下。

    说有一台机器，上面有m个储存空间。然后有n个请求，第i个请求计算时需要占R[i]个空间，储存计算结果则需要占据O[i]个空间（其中O[i]<R[i]）。问怎么安排这n个请求的顺序，使得所有请求都能完成。你的算法也应该能够判断出无论如何都不能处理完的情况。
    比方说，m=14，n=2，R[1]=10，O[1]=5，R[2]=8，O[2]=6。在这个例子中，我们可以先运行第一个任务，剩余9个单位的空间足够执行第二个任务；但如果先走第二个任务，第一个任务执行时空间就不够了，因为10>14-6。

    这个题到底该怎么整呢？我当时花了全部的时间去想各种网络流、费用流、图的分层思想等等，最后写了一个铁定错误的贪心上去。直到考试结束4个小时以后我才想到了正确的算法——只需要按照R值和O值之差（即释放空间的大小）从大到小排序，然后依次做就是了……想到这里开始暴汗，有时候最简单的算法往往是最后才考虑到的。
    好了，不多说了。最近期中，可能更新慢一些。明天一早考数理逻辑，赶紧抱佛脚。

查看更多 »

    上次我们谈到，我们考虑时间复杂度时往往假设任意大的整数运算（赋值、四则运算、取余运算、比较运算、位运算包括左移右移）都可以在常数时间内完成，殊不知这留下了一个非常具有研究价值的漏洞：能否利用计算机理想模型中的整数运算，把问题打包成超大整数后并行计算，从而办到一些在普通计算机上无法办到的事情？我们在上一次的文章中介绍了利用“大整数随便算”的漏洞“耍赖”得到了一个线性时间的排序算法。这个漏洞真的已经被充分利用了吗？我们还能从里面榨出多少汁水来？令人无法想象的是，线性时间的排序算法远远没有挖掘到理想大整数运算的巨大潜力，事实上我们能做到常数时间的排序！问题和解答仍然来自Using your Head is Permitted，在这里向Michael Brand表示深深的膜拜。
    自然，说“常数时间排序”是有前提条件的，否则即使读入输出也得耗费线性的时间。不过，我们可以假设所有待排序的数都已经打包进一个大整数里，输出时也无需解包，直接返回另一个大整数即可。在这样的情况下，我们完全可以用常数时间完成排序。换句话说，我可以用O(1)的时间，“一下子”就把0100 0111 0001 0010变成0001 0010 0100 0111，不管这个大整数里面装了多少个数。为了方便大家阅读和思考，我们再取一些名字，方便描述。我们把由多个数构成的大整数叫做“整数串”。整数串中所含的数都是二进制，它们用空格隔开。整数串中每个数的位数都必须相等，位数不够用零补足。我们把这个位数叫做“定宽”，本文例子的定宽都是4。

查看更多 »

    今天学到一个好玩的东西。仿照停机问题的研究方法，我们可以想出很多有趣的不可解问题。Gregory Chaitin曾经提出过下面这个问题。如果两段代码运行之后能够输出相同的结果，我们就称较短的代码比长一点的那个更简洁（注意，如果程序需要读入数据，读入的数据也算进代码长度）。对于一个指定的输出，一定存在一个“最简的”代码，它是所有能输出此内容的程序代码中最短的一个。在刚刚结束的TLE比赛中，参数选手拼了命地缩减每一个字符，写出来的代码一个比一个短。有人或许在想，这些代码究竟能短到什么程度？你如何才能知道你的代码已经不再有改进的空间了？受此启发，我们的问题出来了：你能否编写一个程序，使得该程序能够判断任意一段代码是否是最简的？
    Chaitin定理指出，上述问题是一个不可解问题，再牛的人也不可能编写出这样的程序。证明方式与大多数此类问题一样，都是采用反证加构造的方法证明的。你能想到这个证明方法吗？

查看更多 »