讲解各种编程比赛

川长思鸟来 2022-08-04 16:39 171阅读 0赞

过去十年间我一直在参加各种编程比赛。我参加了很多比赛，更重要的是，我参加了很多不同类型的比赛。我的冒险起始于经典算法，之后我转到了优化问题。目前我主要参加机器学习竞赛（作为兼职），我也参加一些只是为了好玩的比赛。

考虑到有像我这样广泛经历的人并不多，我想我应该写一个编程（算法?）竞赛流行类型的（相对）简短的总结。这不是一个完整的列表，我只关注了那些最流行的，并且在我看来最有用的竞赛。

这篇文章的结构是以竞赛类型，而不是竞赛网站为导向的。也就是说，我把有相似特征的网站/竞赛归类，而不是呈现给你们仅仅加了我个人描述的随机网站。由于有些网站提供了几种类型的竞赛，我不得不多次列出它们。

如果你对编程竞赛的世界感到困惑或者好奇，这篇文章能给你关于这个主题的详尽综述。

经典算法

有时又被称为二元问题或（带贬义地）消遣算法。提供给你问题陈述，你的目标是写一个通常很短的程序：读入输入，处理它并输出计算结果。任何东西都是按给定的问题陈述来的。大部分情况下， 你要提交程序源代码，源代码在远程服务器上编译并运行一些对你隐藏的数据。下面要提到的所有竞赛的共性是：你的程序要么被认为是完全正确的，要么是完全错误的，没有中间结果。

经典算法竞赛通常是编程竞赛的入门级别。难度从答案显而易见，到只有问题作者知道怎么解答。对于新手程序员，它们提供了小的挑战，是很棒的实践练习。在更高的级别，它们需要高度的专注，很好的长期记忆，解决问题的技巧以及很深的专业知识。如果能在这些竞赛中做好，你会开发出很多可以轻易迁移到计算机科学其他领域的技能。前提是你专注于开发纯粹的技能，而不是把时间花在解决成百上千的问题上以期望今后能遇到类似的问题。（译者注：即不要用题海战术）

竞赛联盟  
有两个主要的网站定期举办比赛。第一个是 [TopCoder][]（以下简称 TC），举办Single Round Matches (SRMs)。第二个是 [CodeForces][]（以下简称 CF）。

这两个网站很相似。一周会举办几次比赛（即将到来的比赛链接：TC，CF）。比赛持续大约2小时。每种比赛都会用几个（TC 是 3 个，CF 是 5 个）为这轮特别准备的原创经典问题（通常，对于所有的比赛都是这样的，但我想澄清这一点）。你只需提交程序源代码，程序会在服务器上远程执行。你的程序如果想要被认定为正确，需要在指定的时间和内存限制下运行，产生正确的输出。美中不足的是，只有在比赛结束后你才知道你的解答是否正确。当这轮结束后，你的排名会得到更新（类似于 ELO 等级系统），这很准确地代表了你目前的水平。赛前参赛者（根据他们当前的排名）会被分到两个不同的赛区，每个赛区使用根据参赛者水平量身定做的题目。另外，赛后你可以看其他人的提交，也会发布题解（解释了问题的正确解答）。所有的题目会添加到练习区，这样你之后就可以去解答那些你在比赛中未能解答的题目。这使得这两个网站成为完美的训练场。

这些是它们的相似之处，那么不同之处是什么呢？TC 最大的缺点是（除了糟糕的管理，不过那又是另一回事了）它使用一个陈旧的 Java applet 来用于竞赛。尽管这使得参加第一次比赛比它应有的过程更复杂（TC 那设计糟糕的网站对此也没什么帮助），但从长远看来比“HTML5”界面也差不了多少。另一个差别是两个网站的题目的关注点稍有不同。TC 上的任务通常向解决问题倾斜，有时候甚至像谜题，然而 CF 就包含很多基于数据结构的“filler”（缺乏想象力的代名词）问题，但这主要取决于问题作者。基于我的经历，TC问题（平均来说）稍微有趣些，但CF的题目更为多样—主要是因为CF每轮有更多的题目。两种竞赛都有一个特性是提供寻找他人代码中bug的机会（如果你成功找到了会获得额外的分数），但是CF对此的设计很可怕（译者注：表示对此没什么感受），最好就是完全忽略它。

年度现场比赛

有四个大的比赛：[Google Code Jam][]、[Facebook Hacker Cup][]、[Yandex.Algorithm][] 和 [TopCoder Open][]（算法组）。它们都很相似。为了取得现场比赛资格，你要参加一系列在线资格赛。通常都是采用淘汰赛的形式，在随后的每一轮减少参赛者的数量。通常对参赛者的身份没有限制（除非你的国家不幸在美国的禁止入境名单上）。每一轮时间都很短，在 90 分钟和 3 个小时之间，只考经典的二元问题（译者注：前面提过了）。如果你取得了现场赛资格，他们会支付你参加比赛的交通食宿费用。他们也给获胜者奖金，但对于大多数人来说，你能赢得的最重要的东西是旅行本身，或者（通过比赛）在顶级 IT 公司找到工作。

这些比赛之间有一些小的差别（题目质量、晋级结构、提交系统），但是它们有两个共性：晋级其中任何一个都非常难（如果你没有两年经验，想要取得资格是极不可能的，即使你聪明且专注于此）。另一个是[有个人][Link 1]（Gennady Korotkevich）在2014年赢了个大满贯。考虑到所有这些竞赛要想赢都有很高不确定性，这是一个难以置信的壮举。

伯乐在线补充：Gennady Korotkevich，年仅11岁时便参加国际信息学奥林比克竞赛，创造了最年轻选手的记录。在2007-2012年间，总共取得6枚奥赛金牌；2013年美国计算机协会编程比赛冠军队成员；2014年Facebook黑客杯冠军得主。截止目前，稳居俄编程网站Codeforces声望第一的宝座，在TopCoder算法竞赛中暂列榜眼位置。

在线判题系统  
这些有很多了，仅列举一些：[SPOJ][]、[UVA][]、[Timus][]。通常，它们主要作为过去的ICPC（译者注：即 International Collegiate Programming Contest， 国际大学生程序设计竞赛）竞赛题的存档。

你在这些网站上花时间原因不外乎那么几个：

一：你觉得你很不擅长某些类型的题目，因此你在寻找一些很难的特定题目（如果你以成为世界前100为目标，这甚至都不应该发生），而你在其他地方又找不到这些题目。  
二：你参加了一场比赛，那些题目被上传到判题网站，你想继续尝试那些你没有解决的问题或者尝试其他的解题方案。  
三：你的算法课老师很懒，他讨厌他的工作。  
优化问题

这种问题的标准例子是[旅行商问题][Link 2]。这些问题以这样的事实来刻画：根据你的解答质量，你得到不同的分数。它们被（或者至少应该被）设计为不可能获得完美的分数。

有优化问题的比赛通常持续时间更长，因此相对于经典算法比赛关注于不同的技能集，比如心理耐力、时间管理或开箱即用的问题解决技能。通常，优化问题要求你是个多面手，但是你不必擅长于任何特定领域。它们也更接近于做实际研究，因此如果你想把你的职业生涯与软件开发以外的事绑在一起，尝试下它们是个不错的主意。

马拉松比赛  
不幸的是，没有太多地方可以让你磨练在这个领域的技能。Topcoder有[马拉松比赛][Link 3]，但是他们不再定期举办比赛，几年前他们还这么做。在马拉松比赛旗下举办的大多数比赛都属于机器学习类（在下面描述），例外是年度Top Coder Open比赛中的马拉松类，现场决赛和资格赛都使用优化问题。有传闻他们想重新举办定期比赛，但到目前为止什么都还没改变。

幸运的是，尽管没有太多比赛，TopCCoder有过去比赛题目的存档。因此如果你的目标只是更擅长优化题目，你可以练习这些旧题。好处是你可以获得所有的优胜解答，另外在这些过去的比赛对应的论坛通常有个“发布你的方法”的帖子。

在一些其他的比赛中你也可以遇到优化问题。但不幸的是，我不认为有可以与马拉松比赛相提并论的。这个类别下最流行的比赛大概是 [Al Zimmermann][] 的编程比赛，但是那的题目都很浅，不太有趣。

机器学习

有时被错误地称为数据科学。这是个有大把钱的地方，因为对专长于机器学习的人才有很大需求，至少相比对经典和优化问题人才的需求来说是很大的。

相比其他类型的比赛，机器学习需要的知识要多得多，通常来说也不那么有趣。尽管如此，这些比赛仍然是目前在这个领域获得一些亲身实践经历的最容易的方式。如果你需要一些动力，记住需要机器学习技能的工作的报酬在整个IT界是最高的那部分。

马拉松比赛（再次）  
我可能提到上面提过的网站/比赛。Topcoder把优化和机器学习问题结合到一个类别。说得更准确些，在某些时候马拉松比赛类别扩张为包括机器学习比赛。

Topcoder的机器学习比赛通常只以一种方式呈现。由于整个Topcoder是个众包平台（再加上围绕它构建的社区），客户有时候会有用“简单的”软件竞赛不能解决的问题。在有些情况下，他们处理的问题可以包装成一个机器学习比赛，给表现最好的方案大笔钱。由于机器学习比赛仍然是马拉松比赛，整个提交系统的运行方式是和优化问题完全一样的。唯一的差别是机器学习比赛通常不加入到练习区。

Kaggle  
Kaggle是个很大程度围绕机器学习比赛而建的网站。我将关注于TC和Kaggle的差别。最大的差别是在Kaggle你只提交你的解答的输出，而不是整个程序，这有很多后果。首先，你获得整个数据集，对你可以使用的语言/库没有限制。没有任何时间限制，如果你想（并且支付得起）的话，甚至可以用整个集群来计算结果。由于大家不用提交源代码，在比赛结束后你不能查看解答。另一方面，社区要活跃得多。当比赛还在进行中时，会有很多“练习赛”，在此人们分享他们的解答。Kaggle的比赛时间也长得多（对于有奖金的比赛通常是两个月）。

总体来说，两个网站各自为稍有不同的目的服务，各有利弊。对于那些对高层知识，而不是各种机器学习技术如何工作的低层内部机制更感兴趣的人来说，Kaggle应该更为友好，然而TC对于有很强算法背景的人来说可能更好。另一种看待这个的方式是，在Kaggle你（通常）使用工具，而在马拉松比赛你（通常）写你自己的工具。

欢乐24小时

15年前，第一届 Challenge24 组织起来了。我不会细说它的历史，因为实际上我也所知甚少。但我会把这个比赛描述为“24小时的疯狂”。它是在布达佩斯举办的年度团队比赛。你有大概15道题。题目的范围很广：经典、优化、TCP/IP之上的游戏、计算机视觉、声音分析、谜题，以及难以用语言描述的东西。你把你自己的硬件带到比赛现场，整个比赛是离线完成的。老实说，这是我参加过的最有趣的比赛。即使我上次参加时发烧了，我还是要这么说。

Challenge24启发了Deadline24，这反过来又启发了Marathon24（两个都是在波兰举行）。它们是Challenge24的简化版，但仍然很有趣。它们没有大量题目，通常只有三个游戏，每轮游戏和比赛同时开始。例如，过去的一个游戏是30个选手同时玩经典的行星游戏。

由于只有有限数量的队伍会被邀请到决赛，这些比赛都举办在线资格赛。由于这些比赛并没有其他年度比赛那么流行，实际上即使没有任何显著的算法（甚至编程）背景，也很可能获得其中之一的资格。

还有一个额外的年度比赛值得一提，它和这些24小时比赛有些类似：互联网问题解决比赛。这个比赛也有很多任务，尽管它们更类似于经典算法。

其他

还有两个大的网站被遗漏了。第一个是CodeChef，有两种不同的月度比赛。两种都是经典算法比赛。另一个是HackerRank，混合了在线判题系统和举办各种类型一次性比赛的功能。我遗漏它们的原因是，它们都因问题陈述的质量低而闻名（译者注：译者使用过这两个网站，对此没什么感受）。考虑到有大量的其他比赛，通常你应该避开它们（尽管有很少的例外）。

如果你还在读高中，对你来说最重要的比赛是国际信息学奥林匹克竞赛。每个国家都有其国家级奥林匹克竞赛和自己的规则。在很多国家，在国家级奥林匹克竞赛中表现优异是进入理想大学最简单和安全的方式。

国际大学生程序设计竞赛（ACM/ICPC）是“经典算法”比赛，在这里所有的比赛/网站中历史最为悠久。它是面向学生的团队比赛。每支队由同一大学的3个人组成。ICPC的主要目标是编程在世界范围的普及。这是用复杂的多层获得资格制度和（同样复杂）的合格标准来达成的。这保证了世界总决赛中队伍的多样性。作为取舍，根据你所在的地方，要想晋级世界总决赛，要么是令人吃惊地容易，要么是近乎不可能。专门针对ICPC来练习可能是把你的时间投资在编程竞赛中最坏的方式，因为它提升的技能集是最窄的，唯一的例外是你生活在那些“幸运的”（译者注：即容易晋级的）地区。

鼓励奖要颁给Hello World Open，因为它创造了年度最大的扯淡比赛，有着很成功的销售计划。如果你仔细看，你会看到在比赛发起后，他们甚至在维基页面加入了他们的链接。我猜如果你制作收入最高的手机app，你会很熟悉这个。说真的，Topcoder应该向他们学习。

另一个鼓励奖要颁给 Imagine Cup。我参加了四次Imagine Cup。两次作为参赛者，一次作为裁判，最后一次作为助手。这些年我看着它从一个聚集多个不同领域（初创，数字艺术，算法/人工智能）的学生的创新年度比赛，到微软产品的傻逼公关。裁判经常是因政治原因被挑选的，绝对不能胜任他们的工作。并且所有没有直接促进微软产品的类别都停掉了。事实是，Imagine Cup是我参加过的最好的现场赛事。同时，现在我不会推荐任何人参加它们。

Project Euler是一种特别的在线判题系统（偏重数学），这在于你以编程为工具来解决问题，而不在于它本身。如果你真的想在没有时间压力的情况下做一些编程题，我建议你做Project Euler，而不是我提到的其他判题系统。另外，由于它很流行，如果你在某个问题卡住了，在网上找到一些帮助要容易得多。

[TopCoder]: https://www.topcoder.com/community/data-science/
[CodeForces]: http://codeforces.com/
[Google Code Jam]: http://blog.jobbole.com/86799/
[Facebook Hacker Cup]: https://www.facebook.com/hackercup
[Yandex.Algorithm]: https://contest.yandex.com/?lang=en
[TopCoder Open]: http://tco15.topcoder.com/algorithm/
[Link 1]: http://en.wikipedia.org/wiki/Gennady_Korotkevich
[SPOJ]: http://www.spoj.com/
[UVA]: http://uva.onlinejudge.org/
[Timus]: http://acm.timus.ru/
[Link 2]: http://en.wikipedia.org/wiki/Travelling_salesman_problem
[Link 3]: http://community.topcoder.com/longcontest/?module=ViewActiveContests
[Al Zimmermann]: http://azspcs.com/