CodeCraft2016区域复赛与全国决赛回顾
作者: 虾米小华
2016年5月30日，我们从深圳安全返回南京。至此，历时近三个月的2016年Code Craft软件精英挑战赛终于圆满结束。
区域复赛，意料之外的惊喜
5月15日，是江山赛区 (即江苏、山东赛区) 的区域复赛，32支队伍在华为南京研究所开战，只为争夺有资格进军全国总决赛的区域四强席位。我们在复赛前的排位赛位居赛区第7，和其他7支种子队被分在8个不同的小组。
比赛的规则类似足球世界杯。第一轮是小组赛，每个小组前两名晋级第二轮，选出16强；之后是淘汰赛，两两PK，16进8，8进4，以及决出冠亚季军。两队PK是9局5胜制，每支队提供两组case，官方提供5组case。PK时在同一组case上，两支队伍的算法首先比拼的是重合边的数量，重边数越少，结果越优；如果重边数一样，就比cost，cost越小则结果越优；如果cost还一样，那就拼算法的运行时间，运行时间越短的队胜出。运行时间通常是不会出现相等的情况，计算机的计时精确到10ms，出现运行时间相等的概率很低。（然而在全国决赛，就出现了这种情况）那要是运行时间真相等怎么办？看最终版代码的提交时间，提交越早胜出。提交时间总不会在同一秒吧。
比赛开始后，我们在小组位居第二。突然发现自己的算法竟然没解出自己设计的case! 赶紧检查源码，发现提交的是较早版本的代码，好在U盘里有备份最新版本。更新了源码以后，提交，升到了小组第一。此后一直到服务器上传通道关闭，我们基本稳定在小组第一。期间我们在赛场内走动，询问其他小组的算法运行情况，因为我们有两个官方case没解出来。了解到几乎所有的队都没解出官方的最后两个case，只有一个队解出来了官方第四组case。
我们给自己定的目标是进8强。后来下午公布每一轮结果时，看到依次进了16强、8强，也舒缓了一口气：目标达成！但是公布4强时，自己心里还是紧张又期待的。其实挺矛盾，一方面止步8强是一个令自己满意的结果，赶紧结束吧，都花了两个月了，之后就可以忙自己手头的许多事情了；另一方面又抱着一丝希望，因为那样的话就能去深圳了，谁不愿意呢？
结果出乎意料——我们真的进了4强。那一刻，我激动地跳了起来，大声欢呼。后来有朋友告诉我，说我那时就像个欣喜若狂的孩子。我自己当时都没意识到，只觉得，那个时刻，世界属于我们。为什么那么激动，因为强队如云，自己从没对4强有过多少期盼，就算没进4强，也能心安理得；进了4强，那就是意料之外的惊喜了。
区域4强的奖励相当丰厚——每人一部华为mate-8手机，加入勇敢星实习计划，以及面试绿卡。
南研所集训，强大的后勤支持
复赛结束后，华为南研所召集了赛区四强队伍，进行决赛前为期一周的集训。
集训的主要内容是对算法进行优化，对代码进行重构。一周的时间相当紧迫，重新设计新的算法时间已经不允许，我们能做的就是对目前代码的一些小改进，或者争取能够解出更多的case，适应更多的输入规模和结构。
在集训期间，南研所给我们提供了强大的后勤支持：四星级宾馆、免费的三餐、宽敞的培训场所，以及在学校和研究所之间往返的车费也全部报销。
我们和其他三支队伍建立了良好的友谊，从初赛复赛的竞争关系，到决赛的并肩作战，这是一种很奇妙的感觉。大家都很乐意分享自己的想法，每天在一起调试程序，晚饭后一起围着南研所的天鹅湖散步的时光短暂而快乐。
耐心的帆神，萌而幽默的冬哥，说话慢条斯理的刚哥，平易近人的凯哥，眼中闪耀着智慧之光的圣博哥，颇有“江南水乡”气质的陆晨哥，学霸+科研大神的俊梅姐……嗯，我竟然有机会和他们谈笑风生（因为其他三支队都是研二或研三的学长学姐，所以这里都称呼“哥”“姐”了）。
全国决赛，我们的算法尽力了
5月27~29日，来自全国八大赛区的四强，共32支队伍齐聚深圳，在福田区丽思卡尔顿酒店展开最后的较量。
由于我们使用的核心算法是遗传算法，所以参数的设定非常重要。在比赛前一天晚上，我们写了脚本持续运行算法，以获得较好的参数，好在比赛现场根据结果反馈进行不断调优。到第二天早上，我写的脚本收集了大约300多组参数，另一名队友的脚本收集了500多组参数，这样我们就有足够的参数来调试。我们的算法是随机算法，其缺点是不稳定，虽然收敛的速度还不错，但每次运行的结果都不是确定的，如果想增加稳定性，就得牺牲时间代价。
了解遗传算法的同学应该知道，遗传算法是模拟达尔文生物进化理论的一种智能优化算法，在组合优化领域有着广泛的应用，至今在科学界还保持着相当高的研究热度。遗传算法的主要算子有选择、交叉和变异。而我们在试验中发现，如果加上选择和交叉算子，将大大降低算法的运行效率，根本不可能在赛题要求的10秒钟限制之内给出结果，于是只采用了变异算子，并且把变异概率提升至1.0，变异算子的设计就相当重要。我们摒弃了常用的变异策略，而用一种邻域搜索算法——3-opt来作为变异算子。这种变异算子很有效，而且复杂度是O(n)级的，可以大大提升遗传算法的速度。所以本质上我们的遗传算法并不是通常的遗传算法，而是一种随机化的3-opt邻域搜索算法，试验发现，这种算法的性能非常好，求解中小规模的非对称TSP(Travelling Salesman Problem)能够得到不错的近似解，而且时间复杂度很低。但是随着规模变大，这种算法的性能就会下降。
为了增加遗传算法的稳定性，我在阅读了一些英文文献后，在我们的遗传算法中加入了一个交叉算子——有向DPX(Distance Preserving Crossover)交叉，经过试验，发现可以显著优化结果。但是会降低算法收敛速度。所以必须小心地引入该算子，比如降低它的调用次数，或者在种群进化到适当的时候开始执行。
上面这段代码就是遗传算法的进化函数，我加入的交叉算子被我命名为”make_love”，你可以理解为程序员的恶趣味。写代码不容易，何不幽默一番:P
决赛的规则和区域复赛的一样，先是小组赛，然后是淘汰赛。我们的目标是希望能够小组出线，晋级16强。
决赛开始后，我们就感觉到了比赛的艰难。有一个队完全把我们碾压，毫无还手之力，于是整个比赛的三个小时，我们都在和另外一个队伍争小组第二的出线名额，和他们不断地交替占据第二的位置。但是每提交一次就得等5-6分钟，距离比赛结束还有10分钟左右时，我们提交了最后一版代码，也是我们那时能够获得最好结果的代码。这版代码再次让我们回到小组第二。但是我们已经不再有调参数的时间，也不打算再提交代码，只能寄希望于对手不要反超。然而墨菲定律还是应验了——对手在最后10分钟逼平了比分。
比分相同就看净胜分，最后我们输在了净胜分。
虽然有遗憾，但是不难过。我觉得我们的算法尽力了。赛后和其他队伍交流，发现我们的算法求解结果也基本是最优解，但是时间就比不上别人了。我们想的是尽可能地利用10s的时间，去求得更好的解，并期望以解的质量战胜对手，区域复赛我们就是这么做的。然而到全国决赛，大家几乎都能解出最优解，在一些case上拼的就是时间。而我们的随机算法在时间上是不占优势的。全国32强的队伍里，也很少有采用随机算法的，基本都是启发式确定算法。
比如，总决赛的冠军“六院八队”的算法是：spfa+指派+LKH（有向3/4/5-opt）；比如，粤港澳的区域第一“中原逐鹿”的算法是：一直跑网络流，整形规划最小必经环，和spfa压缩；比如，我们赛区的”dz”，也是总决赛四强，算法是：基于约束Dijkstra压缩的ATSP近似+指派+分支定界；比如，杭厦赛区四强全部用的约束网络流，平均代码量只有500行。
我们的算法是基于约束Dijkstra压缩的ATSP近似+遗传算法（遗传算法的选择并不是最佳的，随机波动比较大）
冠军的代码量有1万+行，而亚军的代码量只有500行左右。
与顶尖高手之间，还有很大差距。
赢了，更加自信；输了，总结经验，看到和别人的差距，然后继续努力。这是我希望自己能够有的心态。
巾帼不让须眉
这一小节单独拿出来说，因为很重要。
CodeCraft的赛场再次见证了IT界从来都不是为男孩纸量身定制的。虽然就参赛选手的男女比例而言，男生是占据了绝对优势，但是优秀的队伍中不乏女中豪杰。有图为证：
成渝赛区的区域冠军 “LTZ” (电子科技大学)，就有两位女生。（一个队人数不多于3人）；
总决赛冠军队 “六院八队” (国防科技大学)，也有两位女生。
一个队中有一个女生的就更是不胜枚举，她们或作为主力承担算法工程师的职责，或作为辅助协调队内分工合作，或负责后勤保障，肩扛“程序员鼓励师”的艰巨任务。
有男神的队伍所向披靡，有女神的队伍创造奇迹。
深圳之行，梦幻般的体验
另外值得一提的是深圳之行，说它是一场梦幻般的体验并不为过。
第一次坐飞机。 第一次去深圳。 第一次住五星级酒店。 第一次吃海鲜自助。各种零食水果随便吃。 第一次参观华为总部。 …… 而所有的这些，全部由本次竞赛的主办方提供。
当然，最珍贵的，还是见识了那么多非常牛叉的同学，结交了很多志同道合的朋友。他们来自全国8个赛区，各大高校。
深圳之旅，感受的是梦幻，尝到的有苦涩，看到的是差距，收获的是友谊，增加的是动力。
对华为的再认识
参加比赛这两个多月时间的所见所闻，重塑了我之前对华为的许多认识和偏见。
社会上讨论最广泛的，就是华为的加班文化。在南研所的那段时间，我也算见证了加班现象的普遍。比如，华为员工每个月的最后一个周末是要上班的；比如，每天晚餐后，许多华为员工还是像上自习一样回到自己的工作岗位；比如，加班到晚上10点以后是家常便饭。
但是这样是否就意味着华为在压榨员工的血汗，以从中攫取剩余劳动力？我对此不置可否。至少我了解到的是，在华为，一个员工的付出，通常都能得到与之相应的回报，是“一分耕耘，一分收获”的形态。任何企业都要面临残酷的竞争、谋求生存，华为作为一家民营企业，能发展成现在的规模，是非常不容易的。华为给我的感觉，如果用三个词概括就是：专注实干、开拓进取、居安思危。
也许，许多人的理想工作状态是，每天朝九晚五，有双休，不加班，带薪休假，work-balance很舒适，还能年薪20万+奖金20万+分红20万……这当然是一种很好的工作状态。但是要知道，企业面临竞争，求职亦如是，自己没有竞争力，凭什么要求高薪？许多人误解了这种工作状态，他们内心想的其实是：不用辛苦工作，也能财务自由。没有人会轻轻松松就能实现财务自由，包括“精英阶层”。在我所了解的优秀的人中，不论是“大神”，还是“女神”；不论是本科毕业就加入Google总部的算法大牛，还是研二就发表多篇顶级会议论文的科研学霸，没有一个是不努力的，他们都是热爱自己所做，目标明确，并且愿意为了实现目标而能够(在很长一段时间内)克服人性弱点的人。
一向在媒体面前行事低调的华为总裁任正非最近亮相央视，说的一番话朴素无华而充满力量：
……中国现在又冒出来很多企业，其实也跟华为一样，也是专心致志做一件事的。一个人一辈子能做成一件事，已经很不简单了。为什么？中国13亿人民，我们这几个把豆腐磨好，磨成好豆腐；你那几个企业好好去发豆芽，把豆芽做好；我们13亿人每个人做好一件事，拼起来我们就是伟大祖国……
致谢
参加2016年Code Craft，我们有幸从11409支队伍中脱颖而出，一路从线上初赛走到区域复赛，再到最后的总决赛，从春季到夏季，拥有了难忘的经历，收获远远大于付出。在这里，我想借用冠军队的其中一位女生说的话，沾沾喜气，同时来表达感谢。
首先，感谢我的队友。我从队友那里学到了很多。如果没有他们，我绝不可能在这场比赛中一路走到最后。
其次，感谢华为。华为举办的这个比赛，为我们提供了一个展示自己的舞台，给我们的生活添了一分精彩。
最后，感谢这个时代。这个时代是信息的时代，是计算机的时代。我为选择了和计算机、信息相关的专业而感到自豪，也想把自己的青春挥洒在这片土地上。
Code Craft，再见！