Facebook黑客杯背后的难题大师解释了他们如何提出问题

您可以精确地与僵尸战斗吗？饥饿的鱼能从动态编程中受益吗？这些问题激发了为Facebook年度Hacker Cup设计问题的开发人员的灵感。 

今天是该竞赛的决赛，已经是第九年。编程竞赛向公众开放，今年吸引了6,000多名参与者。最终的25名参赛者，经过了四轮最高分的预选赛，将尝试解决从太平洋标准时间上午9:30 –美国东部标准时间12:30 pm -5：30pm开始的胜利之路。您可以在此处观看直播。 

由于Stack Overflow的全部目的是询问和回答编程问题，因此我们认为与一些为Hacker Cup编写问题并学习如何解决问题的开发人员坐下来很有趣。尽管关于SO的大多数问题本质上都比较实用，但是Stack Exchange拥有自己的Code Golfers社区，他们乐于在业余时间为编程问题设计最有效的解决方案。 

那么，是什么导致巨大的Hacker Cup问题呢？我们与Hacker Cup贡献者Jacob Plachta和Wesley May进行了聊天，他们撰写了过去几年中使用的大多数问题。两人在多伦多大学学习期间相识，并自2014年以来一直在合作举办Hacker Cup。 

除了分享有关他们如何解决这些问题的过程的一些见解之外，普拉塔和梅还分享了一个针对2018赛季设计的问题，但最终并未包含在比赛中。您可以在此处找到它，我们期待看到我们的社区对此难题有所帮助。 

取得适当的平衡

May和Plachta说，设计一个出色的Hacker Cup问题集的挑战在于管理问题的难度，多样性和独创性。每一轮的目标是缩小下一轮的范围，并确保每个人都拥有愉快的教育经历。

“在最后一轮，理想的情况是每个问题都得到解决，每个人至少解决一个问题，但没人能解决每个问题，” May说。“在较早的几轮中，我们希望总的困难是使每个解决所有问题的人都进步，但是您并不需要解决所有问题。”

问题必须具有多样性，同时又要保持在比赛范围之内。每个问题的解决方案应该可以从第一原理或众所周知算法的组合中获得。任何人都不应为一个问题所困扰，因为它依赖于一些非常专业的知识。也就是说，没有人希望在每次比赛中都解决相同的问题，因此问题也必须是原创的。

普拉奇塔（Platchta）认为存在两种产生问题的一般方法。首先涉及从解决方案的某些方面入手，然后进行反向工作以解决问题。“这种方法可以奏效，但也很容易导致出现问题，最终感觉更标准，更原始。” Plachta说。第二种方法（如今Plachta经常使用）是从一个解决方案未知的问题开始的。

普拉希塔说：“我基本上花了大量时间在思考可能会变成问题的粗略想法上。” “任何给定的想法都不太可能实现，绝对不到10％的机会。毕竟它可能会变得毫无趣味，或者在尝试解决由此产生的问题时，结果会变得太容易，太麻烦或无法解决。不幸的是，您通常在经过很多思考后才知道。但是，在尝试了足够多的不同想法或变化之后，我会遇到一个实际上变成一个大问题的想法。总是很令人兴奋！”

从日常世界中寻找灵感

有时候，现实世界中的经验会带来问题。May和Plachta遇到了让他们思考的问题，然后慢慢找到了一种将这些想法变成编码问题的方法。“我帮助编写了2015赛季第三轮名为Broken Bits的问题，” May说。“这是基于我对数字时钟损坏的实际观察得出的，这意味着某些LED分段只是无法工作。我记得凝视了一段时间，然后思考，好了，您可以看一下这个时钟，也许由于某些部分丢失而无法说出现在的时间，这使它变得模棱两可。但是，如果您观看此时钟足够长的时间，那么最终您可能会有足够的信息来弄清楚它实际上应该是几点钟了。”

问题想法也可能来自游戏。May回忆说：“我和朋友一起玩了很多Pathfinder Adventure Card Game。” “您必须为攻击选择不同的项目，这意味着使用不同的骰子来确定您将遭受的损失。也许我的一次攻击的平均伤害较高，但我可能更喜欢另一次攻击的平均伤害较低，但方差较高。这变成了一个名为“与僵尸战斗”的问题，该问题出现在2017年的资格赛中。”

“有时候，每年我们都会在多个问题中使用相同的字符和主题。这些问题在主题上可能感觉相似，即使它们可能非常不同，也应该相似。” May说。“去年，我们遇到了一个苦苦挣扎的计算机科学专业学生的一系列问题，这些学生永远无法完全正确地编写代码。” 一旦想到了主题，Plachta和May就会尝试进一步开发该主题，以查看可能还会出现其他问题。

这是计算机编程的挑战，但有时灵感来自大自然，例如观看象牙鱼将蛤c砸向行星地球上的岩石。“这个概念看起来很酷，所以我考虑了如何扩展它。也许可能会有多个硬度不同的蛤different和岩石，因此蛤need需要砸在更坚硬的岩石上。” “我考虑了很多变化，包括放置这些蛤and和岩石的背景以及目标是什么。事实证明，将它们排列在数字线上并要求最小旅行距离以打开所有蛤the的简单概念解决了正确的问题，从而导致了2019年第二轮海鲜的最后一个问题。”

“鉴于象牙鱼可能采取的可能路径呈指数级增长，这是一开始似乎不可行的问题，这是理想的。只是在进一步考虑之后，您才能将可能的最佳路径缩小到一组更易于管理的模式。从那里开始，它可以归结为使用动态编程可解决的问题，这是通过递归解决较小的子问题来有效解决优化问题的通用方法，这在比赛中通常很有用。尽管在这种情况下，需要一种更高级的技术（通常被称为“凸包技巧”）来获得足够的有效时间复杂性。”

无论灵感如何，他们都通过将其包装在叙述中来使问题变得有趣。“故事的最后是一层清漆。就像您当然不必拥有它，但它却有趣得多。” 在两个披萨送货员之间的竞争中，提出了在网格上放置块的问题。关于在树上的节点周围移动的问题变成了一个痣家庭的婚姻冲突的故事。 

不断发展的复杂性

如果您看一下几十年前奥运会体操运动员的获胜常规，那么与当今顶级表演的复杂性相比，它们似乎简直太简单了。自2011年以来一直在举办的Hacker Cup期间完成的这类问题也是如此，这种问题来自更早的比赛，如ICPC（自1970年代以来一直活跃）。自从5月开始以来，问题就变得越来越难。“如果我回想起2008年ICPC的世界总决赛问题，现在我可以解决很多这样的问题。而如果我单单从今天开始看一个问题，我大概最多可以解决11个问题中的三个。”

1970年代和80年代的最后一轮比赛今天被认为是中等难度。“以前的问题非常明确地说明了您必须采取的措施，而大多数挑战在于实施而不是实际解决问题。如今，这类问题通常被认为是琐碎而乏味的。” “重点已经转向寻找核心算法和数据结构的有趣应用。因此，例如，找出最适合这种情况的工具-二进制搜索，深度优先搜索，分段树，动态编程等，然后使它们发挥作用。”

由于许多参赛者在整个高中和大学时代就一直在解决这类问题，并且配备了预先编写的算法，因此“黑客杯”的问题不仅仅在于确定正确的工具。“如今，我们试图解决问题的方式是有趣的转变，”梅说。“也许您会得到一些未在图表上明确玩过的游戏，但是如果您以正确的方式考虑它，您会发现它实际上具有抽象的图表结构。一个棘手的问题应该很难解决，因为需要一系列有趣的见识才能提出可行的解决方案，而不是因为实际的编码工作既冗长又挑剔。”

随着参赛者能力的提高，有时候是参赛者使问题作者感到惊讶。“参赛者提交的内容有时会比我们自己想出的更优雅，” Plachta解释说。“一个很好的例子是在今年的第三轮中存在一个名为“整数即服务”的问题。我打算让解决方案涉及素数分解并独立处理不同的素数，这是处理GCD和LCM的一种非常典型的方法，这是此问题所必需的。而且，这就是多少人去做。但是，一些顶级选手想出了一种更简单的方法，即利用GCD和LCM相互交互并更直接地使用它们。即使在比赛的短时间内看到这些思考过程，也真的很酷，令人印象深刻！”

虽然竞争性程序设计的更广阔世界已经发展，但黑客杯也是如此。在最初的几年中，每轮比赛都有三个问题，包括决赛。现在，每个在线回合都有四个问题，最后一轮比赛从三个问题的三个小时变为六个问题的四个小时。“不仅增加了问题，我们还努力保持质量和原创性。我们希望每一年都比上一年更好。” May说。随着时间的流逝，总体理念的某些方面也发生了变化。“过去，对于每个问题给出的示例测试用例，我们都是卑鄙的。由于您只有一次机会可以在Hacker Cup中提交每个问题，因此我们如今变得更加慷慨。如果您对样本数据正确，则可能是正确的解决方案。我们正在尝试测试您解决有趣问题的能力，

骇客，针对骇客，向所有人开放

May和Plachta都是前ICPC世界总决赛的竞争对手。他们最初是在2011年在多伦多大学ICPC团队的选拔赛上见面的，最终他们一起参加了世界总决赛。第二年，由于世界总决赛有两次出场限制，May不能再参加ICPC比赛，所以他接任了U.T的教练职务，而Plachta和他的团队又进行了一次世界总决赛。从那时起，他们在各种竞赛中都遇到了书面问题，包括高中水平的竞赛，例如加拿大计算机奥林匹克竞赛和沃本挑战赛。

更值得注意的是，虽然May在学习CS时成为一名竞争性程序员，但Plachta却在学习音乐。“我的第一个世界总决赛团队有一名统计学专业的学生，他负责解决大多数问题，而我们其他两个人则负责所有编码工作，”梅说。“您无需参加传统的“技术”课程即可享受算法竞赛并获得成功。我的两个最好的队友都没有专注于CS或工程。”

多年来，黑客杯的参与者一直在Facebook工作，其中许多人参加时仍在上大学或高中。梅说：“尽管竞争性编程仅测试非常具体的技能子集，但参加者显示出一定程度的编码热情。” “我在西蒙·弗雷泽大学（Simon Fraser University）读本科，这在美国并不是特别着名。我竞争激烈的编程活动首先使我成为Facebook的关注。”

早些年，Facebook始终在其门洛帕克总部举办比赛的最后阶段。为了扩大比赛的范围和可及性，Facebook开始从全球范围内选择新的地点来举办现场活动。今年，黑客杯将在都柏林举行，您可以在美国东部时间上午8:30开始观看决赛的现场直播。如果您想了解更多有关Plachta的信息，请在此处查看个人资料。最后但并非最不重要的一点是，如果您今天早晨感到有些困惑，请不要忘记查看Hacker Cup团队在Code Golf上分享的问题。