参加2017华为软件精英挑战赛是怎样一种体验?

利益相关,作为大赛组织者之一,希望听到大家真实的声音,有利于我们更好地组织软件精英挑战赛,让学生拥有更好的参赛体验。
关注者
203
被浏览
81,244

----------2017.5.20初次编辑,最后修改于2018.2.14----------

最近回顾一年的生活经历,发现知乎还有草稿没写完,还是半年前的......^_^''(拖延.jpg

(大家情人节 & 新年快乐!)

写在前面 由于主题是参赛体验的分享,对赛题本身的评价不再多展开,感兴趣的读者可以参考本人在这个问题下的回答: 如何评价2017华为软件精英挑战赛赛题? - 知乎 。当然,参赛体验不能完全脱离赛题而言,所以对于赛题还将不吝必要的笔墨,只是不再讨论技术细节。下面的行文,将首先从整体上描述这项比赛,并将其与其他主流算法竞赛做比较,然后对CodeCraft2017的参赛体验做局部简述,体验的「好坏」都将予以直言。作者保留对本文的所有权利。

独树一帜的高水平算法竞赛

CodeCraft2017历时72天,总决赛于2017.5.15谢幕,参赛学生2w+,规模盛大。今年是第三届,没记错的话,去年共有11409支队伍参加了比赛。

在众多的算法竞赛中,CodeCraft无疑是极具特点的一个。它提供了一个全新的平台让参赛选手去做非常有挑战性的问题。目前的算法竞赛主要分为两大类:

  1. 着重考察选手对经典算法掌握的熟练度、对问题的分析建模能力、压力下思考和编码的能力,比如OI、ACM-ICPC、Google Code Jam等。正式的比赛基本都是现场赛,选手们需要利用主办方提供的电脑,在规定的时间内(5小时)提交可编译运行的代码,通过OJ(Online Judge)的所有测试用例才能得分,像体育/电子竞技,是智力和手速的比拼。参加 ACM-ICPC World Final 是怎样一种体验? 这个问题下有很多美妙的回答。OI/ACM的赛题对算法的时空复杂度有严格的要求,仅仅知道怎么做而不能快速地实现是不行的。虽然偶尔也会出现NP-hard问题,但大多用例规模不大。参加这类比赛的选手(主要是中学生、本科生),从学习编程语言(C/C++为主)、基本的数据结构与算法开始,往往要经过长时间的训练,如果是OI/ACM的比赛,获得参赛资格还要先经过校内/省市的预选。
  2. 着重考察选手分析与挖掘数据、建立数据模型的能力,比如Kaggle、天池、DC等。这类比赛时间跨度往往较大,短则十天半月,长则三四个月。参考参加kaggle竞赛是怎样一种体验以及参加天池大数据竞赛是怎样一种体验。比赛对选手使用的工具(计算机、编程语言、框架等)往往不作限制,大多是网络赛形式,选手线下做题,然后提交结果到线上。问题的定义大多来自于实际的生产环境,并经过一定的脱敏和简化,要求参赛者根据平台所提供的数据,挖掘有价值的信息,对赛题提供方所关心的对象/指标进行分类或预测。

CodeCraft与上述两类比赛有着显著的不同,主要特点总结如下:

  • 问题是对生产环境中所遇到的某个具体问题的抽象,且是具有挑战性的难题(目前来看涉及的领域主要是离散优化、博弈)
  • 主办方提供开发算法的基本SDK,要求选手提交源代码,代码在平台上编译、运行、评测
  • 编程语言被限制在C/C++/Java,且不允许直接使用任何开源库/框架,对算法的时间限制严格,空间限制较宽松
  • 比赛时间跨度大,类似于上述第二类比赛,是马拉松式的

其实CodeCraft说是“软件”比赛并不恰当,“算法”比赛更合适,因为既不是开发产品比如网站/移动应用,也不是做数据挖掘。更像是考察选手的科研/创新能力、对高阶算法的设计与实现能力。在CodeCraft的赛场上,许多选手第一次用C/C++/Java动手实现了那些听起来牛逼哄哄的算法:线性规划、整数规划(分支定界、割平面)、遗传算法、模拟退火、蚁群/粒子群优化、元启发式、以及神秘莫测的XJBS算法:);第一次实现了教科书里少有提及的算法;永远猜不透那个稳居榜首的队到底用了什么算法;为了解决一个问题写出了过去从未写过的代码量;对整数规划、各种启发式搜索算法的性能有了更真切的理解;感觉到「NP-hard」属性是一个多么难以逾越的鸿沟......

世界上最遥远的距离,是知道你就存在于高维解空间里,但是我却无法在多项式时间内找到你

我想,算法竞赛能吸引那么多学子参加的最重要原因应该就是公平性吧——对问题求解好坏的唯一依据是选手提交的代码以及代码运行的结果,平台提供了一个相对公平的环境来验证算法的性能,而不依赖于人为因素。你说你的方法好,ok,代码拿出来放到平台上一起跑一跑就知道孰优孰劣。

CodeCraft2017参赛体验小记

从第一届开始,CodeCraft就给参赛选手留下了非常不错的参赛体验。新颖且极具挑战性的赛题、技术人员的热情配合、丰厚的物质奖励,到了决赛就更是「燃烧的经费」,比如为选手提供绝佳的住宿环境,强大的后期保障,等等,这些都无不体现出了华为对这项赛事的重视和投入。

下面是对CodeCraft2017更具体的主观体(tu)验(cao):

  • 初赛和复赛赛题延续了去年的命题风格,初赛一道NP-hard问题,复赛在初赛基础上叠加难度,渐进式的难度升级,让选手不至于感觉突兀,且可以基于之前的努力继续设计算法。初赛和复赛的赛题都是很不错的设计,问题本身也非常具有科研价值。
  • 判题服务器问题多多。判题服务器性能优化做得不好,初赛和复赛选手往往需要耗费大量的时间在赛题的提交上。由于判题服务器的问题,直接导致各个赛区的复赛现场赛不得不延期举行(我不认为复赛的延期举办成功就是复赛的成功)。因为复赛的延期,各个赛区努力组织的活动都没有得到很好的展现。
  • 决赛赛题性质的突变。个人观点,这是CodeCraft2017最大的败笔。命题组为了让比赛具有所谓的「观赏性」和「趣味性」,强行将赛题由「优化」调整为「博弈」。但是本人并没有体会到这两点,观赏性甚至做得不如去年,所谓比赛复盘,仅仅是呈现结果,而没有中间过程。
  • 数据万年不换。相信参加过比赛的选手能体会这一点,到了决赛依然如此。
  • 点评的不专业。每年都会有对选手算法的总结和点评。我把CodeCraft2016和CodeCraft2017对选手算法的总结贴出来,大家感受一下(上面一张是16年的,下面一张是17年的):
CodeCraft2016
CodeCraft2017

今年对选手算法的总结,似乎就是把去年的幻灯片拿过来贴了一遍,连顺序都没变...这让我不得不怀疑这份幻灯片的制作者是否真的清楚选手们都用了什么算法。就算直接把去年的拿来用,无论如何也不能少了针对17年比赛的费用流这个最最基础的算法吧...

  • 经费的缩减。当然这是我主观的体验,事实如何我就不得而知了。
  • 赛区的HR们永远都是那么可爱。在参赛过程中,我感受到最多的温暖几乎都是来自于他们。

其他

关于做比赛。我们队明确方向后的分工主要是这样的:队长设计核心搜索算法,另一个队友负责费用流的高效实现,比如原始对偶/cost scaling/网络单纯形,我负责求解赛题各用例的最优解,顺便打打酱油。至于怎么求,当然是建整数规划模型,然后用你能找到的各种工具求解了,反正线下暴力搞出来即可,一开始我用lpsolve,等到花儿也谢了,然后改用Gurobi,性能相当不错,初级用例10s内,高级用例最多等他个几小时也能出结果,再不济设合理的gap也能得到近似度非常好的近似解。By the way,求解整数规划模型,LocalSolver也相当强大。根据我的经验,只要你能建出合理的整数线性规划模型,先上Gurobi,不行再上LocalSolver,就没有得不到高质量解的。提醒:Gurobi和LocalSolver都是商业软件,嗯,学生邮箱你值得拥有。(发现学生时代最有价值的就是学校买的各种数据库以及以.edu.cn结尾的个人邮箱了

有人要问了:你求出最优解也不能交上去,有什么用?好问题。我们拿到最优解的目的是:为设计启发式算法提供依据。我算出最优解之后,就给队长,然后队长就开始分析最优解,看能不能找到一点规律。最优解往往都具有较为特殊的结构,虽然直接发现这些结构肯定是比较困难的,但是不断观察,想办法抽象成规则,得到近似的最优结构也是很有帮助的。就算不作核心算法,用来算个质量可以的初始解也是极好的。

那些榜上前几的队用的是什么算法?我没具体调研过,但大多应该是meta-heuristic / local search,也就是所谓的「元启发式算法」。当然,这不是一个具体的算法,而是一种求解组合优化问题的「方法」或「思想」。在不允许用开源库/给的time limit又很短的条件下,这类方法大概是开发效率最高的吧。所谓启发式算法,就是根据问题的具体性质和结构定制合适的优化规则,引导算法寻优的方向;所谓元启发式算法,就是用全局搜索+局部优化的方法避免陷入局部最优。

最后,真心希望CodeCraft能够一直办下去,并且越办越好。

(完)