Archive: 七月, 2011

HDOJ的提交记录抓取与初步分析

突然萌生一个有意思的想法,如果抓取一个Online Judge的全部提交记录,是不是能从中分析出什么有用的信息。我昨天开始抓取HDOJ(http://acm.hdu.edu.cn)的所有提交记录,挂了一个晚上,截至今天下午终于抓完了HDOJ从第一个提交到昨天下午1点多的所有提交记录。共计4131493条,抓取并格式化存储花了大约十几个小时。

Continue reading »

为什么很多网络流问题总有整数解——全单模矩阵的性质

以前在Online Judge上遇到过很多问题需要转化为网络流模型,原问题一般是要求有整数解的。但是转化为网络流问题后虽然边上的最大流上限都是整数,其实并没有要求最大流也是整数,可求出来的最大流就是整数。我以前一直迷茫这个现象,并且我是很懒的人,一直没有严谨的想过这个问题或者查过这个问题。我们课题组平时很少讨论整数规划的问题,所以这个其实比较基本的问题我一直都不知道。其实你可以从直观感觉如果有非整数的流,那总应该能再怎么样多流一点变成整数,不过这显然是直观感觉,什么也说明不了。昨天看书看到有讲这些,终于理解了,在这总结一下。

Continue reading »

The Art of Lemon队的KDD CUP 2011 Track 2解决方案大致思路

随着KDD CUP 2011的结束,需要开始总结我们的解决方案了。我们在最终测试集Test2中排名第二,和在排行榜中测试集Test1上的排名是一致的。我先发一篇Blog大致总结一下我们的方案,一来自己回顾和理清整个过程便于后面详细的写Solution Paper,二来与大家分享我们队的成果。

Continue reading »