队长2021年code jam参赛历程

大家好，我是练习时长一年半的算法练习生--------魔法小分队队长。从2019年秋天开始，在做好人生决定后，我开始正式学习算法。

大学的时候虽然也上过C语言，也写过一些小程序，但是都不涉及算法，我甚至还参加过一次程序设计大赛。原本以为就是自己设计一些小游戏之类的，去了之后才发现是要做题。我当时真的是什么都不懂，连时间复杂度是什么都不知道。看了一眼，只会做两道题，我就想会做两道也可以了，赛场上实时最好成绩也就是两道。我就开始做，做完之后，提交，告诉我， Time limit exceeded。我还以为是机器出错了，就一直交，一直Time limit exceeded。最后的结果，一道都没做出来，没有成绩。那个比赛貌似是叫一个力高新能的企业赞助的，赛后企业宣讲，我也没有任何兴趣听，就领了一个小纪念品回去了。

前一段时间，我无意发现acm.ustc.edu.cn这个网站居然收录了这场比赛，我的大学阴影比赛。看到这些题目，我仿佛又看到了在机房那个崩溃了的自己，现在想想真的好笑。一个N=10^5的题目，我居然用最暴力的O(N^2)来做，你不超时谁超时？

这就是我第一次参加比赛的经历，之后我就没参加过任何正式的比赛。leetcode周赛和codeforces都属于练习赛的性质，没啥奖品。而第二次正式的比赛就是这次code jam。

Code jam是谷歌组织的比赛，一年一度，大神云集，这场比赛的详细介绍我写到这个专栏了，大家如果完全没听说过可以看一下。

比赛的前期还是挺顺利的，3月28日，我以494名的成绩顺利过了qualification比赛，然后4月9日我在round 1又拿了296名。我甚至还录了视频放到了B站，本来觉得这种视频没人看，一万播放量到头了，结果居然突破了20万，也谢谢大家对我的支持。

在拿了296名后，我突然就燃起了希望。因为round 2前1000名都能进，而如果我保持qualification的成绩，稳进，如果以round 1a的成绩 （round 1一共3轮，只要通过任何一轮就可以晋级），哪怕乘以3，也是900名，还是可以进的，我觉得自己应该没什么问题。

接下来我就开始把主要精力放到了学术上了，过了一周，我决定给自己模拟测试一下，于是抽了2个半小时，做了2020年的题目，做完傻眼了，两个半小时只过了第一题和第二题的小数据，排名2800名。然后我不服气，做了2019年的题目，这次更惨，只过了一个小数据，排名3000多名。突然感觉到比赛的艰难。

然后我就开始疯狂的刷以前的题目，在刷题的过程，发现code jam的题目出的是真的新鲜，质量高，每做完一道题都觉得自己学会了不少东西。但是我发现自己的水平只能在2012年以前的比赛拿到前1000名甚至前500，但那个时候编程还没火，参加比赛纯粹是兴趣，不像现在似的全民刷题，所以没有任何意义。这就好比你做1980年的高考题目，绝对能上清北，但当时什么条件，现在又是什么条件？

所以，我降低了自己的期望，round 2如果没过，那也是情有可原的。

在准备了四周后，5月15日上午10点，round 2比赛正式打响。

首先第一题，是一道互动题，两种操作，给你一个隐藏的数组，你要把这个数组从小到大排序好。

你可以选择查询某个区间的最小值，但是需要花费金币，区间越大，花费越低。你也可以交换任意两个数，不会花费任何金币。最后花费金币越少越好。

我一看，这.....也太简单了吧，典型的选择排序啊。在确定读题无误后，我开始写程序，然后发现用人家给的test tool一直无法通过，后来检查了半天，发现排序完之后人家还会给输出，我自己没有接收就下一步了。这样就会造成我下一步的接收信息实际上是人家上一步的输出，就全乱套了。

这个错误足足耗费了我15分钟，最后我26分钟才过了，一看实时排名1700+，我心里一凉，感觉不妙。

然后第二题，有一种大多边形套着小多边形的图形，跟下图一样，告诉你总边数，问你哪种方案能让多边形的数量最多。比如下图，33条边，最多可以搞出三个多边形来，一个24边形，一个6边形，一个三角形。

这题我想了10分钟，发现就是一动态规划加点数论。因为里层和下一层肯定差个整数倍，假设dp[n]表示总边数为n时，最大多边形的个数。我只要寻找n的因数m_1,m_2....m_i，然后让dp[m1-1]尽可能大即可。  然后写上去一交，就wrong answer了。

然后我仔细分析题目，找了半天才找到原因，因为n/m表示的是最里层多边形的边数，而这个边数是不可能为2的，所以我们要有附加条件。加上这个constraint再交就过了。

做完这道题，我的排名上升到了1300，然后就是第三题了。

第三题是把一堆半径为1,2,3......n的馅饼叠在一起，但是顺序可以变化，比如n=4，就有24种可能，毕竟1*2*3*4=24。然后呢，我们定义：如果上面的馅饼比下面的大，那么会把下边的馅饼盖住，下面的馅饼就不可见了。我不知道馅饼先后循序，但是我每次都可以看见可见馅饼的数目。

比如，如果馅饼的顺序是1,3,2，第一张馅饼1放上去肯定可见，第二张3会把1盖住，而最后一张2虽然不如3大，但其在3上边，所以也可见。所以三次叠加的可见数分别为[1,1,2]

现在就是，我给你一个可见数数组，你数一下一共种permutation可以达到。比如[1,1,2]，就有两种方案[1,3,2]和[2,3,1]都能做到，所以输出2。

这题我一开始就想到用递归来做，但是只能搞小数据，大数据递归直接就炸了。在想了10分钟没有任何大数据思路的之后，我开始写起了递归，20分钟后，我成功拿到小数据的分。

此时我排名进了前成功1000，但是这个排名是虚的，因为很多人比我慢是因为他直接搞大的test set，肯定要慢一点，等搞完大的我肯定就不行。

然后我就有两个选择了，还有40分钟，我可以选择围攻大数据，也可以选择切第四题。

我首先读了一下第四题，发现第四题的小数据就是一典型的匈牙利配对算法。但是，我并不会写匈牙利算法。昨天晚上还看了，但是没看懂，我当时真的很后悔没重视这个算法。

然后我就纠结，到底要不要再学习一下匈牙利，然后把第四题小数据做出来。然后我觉得可能短短30分钟未必能学会，而且也就11分， 还是围攻第三题大test set吧。

做完这个决定，我就开始对第三题进行疯狂的围攻，在比赛结束15分钟，我终于想到一个分治法思路，然后开始写，调试。

时间一分一秒的过去，我的测试结果总是不太对，在最后的5分钟我灵光一闪，想到自己测试不过的原因，然而，当我本地测试终于通过后，比赛已经结束好几分钟了。

最终我的排名定格在1672，无缘round 3，也没有T-shirt，什么都没有.....

虽然这个无缘是我预想到的，但我还是很难受，我前面如果再快一点，没准就过了。然后我看了一下第1000名的成绩，发现即使我在最后的5分钟极限AC，最后还是因为罚时被淘汰，心里突然就释然了一点。

而且，当我把这个本地测试通过的代码交上去之后，large test set会超时，因为分治法也是O(n^2)，我最后用了一种完全不同的方法做出了这道题，这种方法我在比赛的时候是不可能想到的。

然后，我在想如果我会匈牙利算法，然后做出第四题第一问会是怎么样，答案是，还是会被淘汰，只不过名次是1300多，但没有本质区别，我还是拿不到T-shirt。除非我做出来，并且在最后几分钟极限ac第三题，这两个都做到才行。但第三题我灵光一闪的思路也不是最优的，所以，这种情况不可能发生。

总之，我不过还是因为我太菜，实力差距太大，1600多名已经比我练习的名次好多了，我15年以后的题目练习名次就没进过2000。只可惜，我是不可能凭借这次比赛直接拿到谷歌的面试了，这个要进round 3才可以，这样的名次也不知道还值不值得写在简历上了。

不过呢，我现在已经比我一年前刚刷题的时候好多了，因此，继续加油，明年再战！

本文为我原创本文禁止转载或摘编

学习 编程