退役竞赛选手来闲聊一下LeetCode题目和周赛

lz现就读于中部某校cs master项目，每天都来地里闲逛/签到/答题，无奈每天两颗大米攒的速度实在有点慢，不知道何时才能攒到188看面经。lz平时不太自拍，房东也不让养宠物，每天都眼馋隔壁有猫主子可以出面营业。lz想一想自己也没什么一技之长，唯有在刷题方面还有点心得，所以也想分享出来骗（划掉）赚一点大米。lz本科的时候打了两年的ACM竞赛，也给一些小比赛出过题，虽然竞赛成绩不算理想，但终归还算是学了一些东西。去年十月底后知后觉开始准备找实习最后侥幸上岸，现在每周也就打打lc周赛，这里贴一个lz lc周赛的rating（281突然变unrated吞掉我30分可恶）。

相信大家关于如何解题的tutorial也看了不少，这里就不班门弄斧了，比我厉害的大佬比比皆是，他们关于如何刷题、学习算法的教程远比lz要详细和完善。lz今天想从出题人的角度来聊一聊LeetCode（或其他同类OJ）的题目。

先是一点常用的名词解释：
AC：accepted，即提交的代码通过
TLE：time limit exceeded，指代码运行时间超时，也可以直接说代码t了
模板题：几乎没有任何包装，直接考察某种算法，做题人直接照抄算法模板即可ac
签到题：一场比赛最简单的题，有手就能过，和签到一样
暴力：brute force，即基本没有任何技巧，直接遍历所有情况得出答案
卡常：指代码理论复杂度符合题目预期，但是t了，因为代码常数过大（比如本来跑一遍循环可以获得的信息但是跑了五遍），可能由于题目给的时间太紧或做题人代码实现不够优雅导致
标程：标准程序，出题人自己的solution
1e5: 1*10^5，用来描述数据量的简写（同理有1e6，1e7等）

作为一个出题者，一般来说构思一道算法题会有两种方式：1. 清楚自己想考什么算法/知识点/公式，然后找一个场景把这个算法包装起来使得题目不显得那么模板（考察做题人是否真正理解了这个算法）；2. 从生活中或是别的场景获得了启发，发现某个问题可以抽象成一个模型，这个模型正好可以用某个算法来解，于是出成了一道算法题。在这个过程中，往往题目的难度是不太好把控的，而题目的难度又往往和数据量相关——一道很难的题可能因为数据太弱（比如数据量太小或者不够全面）导致题目变水，比如nlogn的预期复杂度结果被n^2的写法过了；一道很简单的题可能因为时间上限给太紧导致只有很少人通过，变成了比谁代码常数更小的难题。出题者在确定题目的时限时又需要考虑到数据量、不同语言的运行效率、测评机的配置的影响，所以确定题目的时限其实是很麻烦的一件事。LeetCode在题目描述界面没有像其他OJ一样显示每道题的时间限制，不过题目一般时限都在1s～3s左右，这一点大概了解一下就行。
除此之外，由于OJ是黑盒测试，只比较运行的输出结果，所以测试数据是否完善也非常重要：如何尽量让数据cover掉所有的corner cases？如何尽量让所有错误的做法都无法通过？怎样用大数据检测提交的代码是否有正确的时间复杂度？这都是出题人要考虑的问题。再加上题目本身有无错误、问题描述是否清楚无歧义、测试样例是否能帮助做题人正确理解题目要求等等因素，一道题目往往需要多个验题人，经过层层测试才能最终来到大家面前。出一道好题很难，办一场好的、题目有区分度的比赛很难，像LeetCode和隔壁Codeforces等OJ能为全世界应试者、算法爱好者常年提供稳定、高质量的题目，更是一件非常不容易的事情。

话说回来，其实做题者往往能通过题目数据量来获得非常重要的信息。就lz自己而言，每次见到一道题目，在读完description之后，第一件事就是下滑看题目的数据量。事先声明：接下来的内容仅针对在OJ上做题的场景，对于面试时面试官直接口述题目不给数据量、让你想最优解的情况不在讨论范围内。
lz在lc上暂时没找到lc测评机的配置，不过一般算法题可以记住一个大致的标准：测评机1s能完成的运算量，大概在1e8这个级别左右。加上一些常数的影响，如果标程的解法是O(n)的，那数据量应该会定在n<=1e6左右。由于不同编程语言的效率有着显著的不同，相同的代码逻辑用C++写可能跑起来需要1s，用Java就要变成2～3s，换成Python则可能高达10s. 但是出题者又不能随便给不同的语言定不同的时限，因为时限越长，越有可能通过各种奇怪的优化、剪枝、设置编译命令等骚操作用不正确的复杂度ac。这也是为什么竞赛选手一般都写C++——尽可能规避不同语言运行效率带来的影响（其实C++的STL非常好用）。但是LeetCode这个平台本来就是求职向，大家的使用的语言五花八门，不可能要求所有人都写C++，所以在数据量上做了一定的妥协——有些标程是O(n)的题目数据量只有1e5，保证n^2的代码过不掉就行了。不过这也给一些人提供了操作空间，如果没想到或者不想写类似双指针、单调栈/单调队列等O(n)的算法，用线段树、树状数组、rmq等带个log的算法（nlogn）也能过，因为1e6的log大概在20左右，1e5*20=2e6，也可以在1s内运算结束。
同理，我们可以通过观察题目给出的数据量，来“猜测”出题人希望你用什么样的复杂度ac. 如果题目数据量是1e5，那你的solution就不能超过nlogn，如果在这个数据量下你想到了一个n^2的解法——你还是别写了，肯定过不了；如果题目的数据量在2k左右，那你可以使用n^2（2e3*2e3=4e6，能过）的算法，也几乎是一定不存在On或者nlogn的解——如果有，出题人为什么不加大数据量？（啊你说周赛第一题，签到题的话那没事了）。
如果看到数据量在15～18——那我反手就是一个

1. for (int mask = 0; mast < (1 << n); i++) {
   
2. 
   
3. }

复制代码

这是非常常见的bitMask的数据量（如果后来发现不是我就把这段代码删掉XD），如周赛277和280的最后一题。因为2^18在2.6e5左右，剩下的复杂度正好用来做一些额外的操作去计算/遍历我们想要的答案。如果希望突破hard题，或者想周赛冲到1900+，你需要对这种数据敏感到这个程度。

以上的描述只是作为一个启发，算法的时间复杂度分析并不仅有这几种，比如周赛281的第三题——每次循环遍历26个字母，枚举哪个可以放在当前位置。数据量1e5，算法复杂度O(26n)，正好是2.6e5，能过。再比如279第三题这种奇怪的描述：

你可以看出来toString方法可以是On的，因为只调用5次；而fix，unfix，flip，all，one，count等方法的复杂度最多都只能是logn，因为可能调用1e5次。
分析数据量还有个好处在于，如果你觉得你的时间复杂度是对的：在这个数据量下肯定是能过的，但是t了，那一般都只有两种可能：1. 你的代码实现不够优雅，常数太大了，可以试试适当剪枝然后再交一次（如刚结束的284最后一题，图论题本来就自带大常数，在1e5的数据量下跑3遍dijkstra很容易给卡常）；2. 你复杂度分析错了。

除了时间复杂度，有的数据量还可以提示你题目的解法。如果你发现题目给你一个数组，里面数据的大小不超过1e5: 可能是出题人好心，这样设置题目里的数据正好不超过int范围，你不需要考虑使用long；也可能是提示你开一个大小为1e5的数组，然后对应位置记录每个元素的个数，如281最后一题。

最后一点题外话。刷题确实不是一个容易的过程，从一头雾水到渐渐有点感觉再到（还算）得心应手，lz也花了很长一段时间。其实lz不太赞同做不出来的题直接看答案，但是可以把它拆分成几个步骤：
1. 遇到一道题，想了半天不会写，好，打开discussions看看题目的tag发现是dp，那现在会不会写？
2. 如果还不会，打开第一篇题解看看dp状态是怎么设的，dp[i][j]代表什么，好，现在会不会写？
3. 如果还不会，看看dp转移方程，好，现在能写了吗？
4. 如果还是不会，那详细看一遍题解，再思考一会儿，现在能不看题解自己写一遍吗？
你在一道题上花了多少时间，就决定你对这道题有多深的印象。如果发现自己刷了题老是记不住，那估计是花的时间还不够多。

这次的碎碎念就到这里啦，啰啰嗦嗦说了一堆，算是给新人一点小tips，非常感谢大家的观看，如果有谬误也欢迎指正。如果大家看得开心，也麻烦给lz加一点米（每天签到啥时候188啊呜呜呜），顺带祝lz今年秋招ng找工顺利吧。


补充内容 (2022-03-17 02:57 +8:00):
果然晚上脑子不清醒不要写代码……
中间的代码段应该是
for (int mask = 0; mask < (1 << n); mask++) {
}
后面的dp[ i ][j]里面的i被当成斜体标签了

感谢大家，大米够啦！

给了我一种电竞选手降维打击小镇做题家
感谢LZ

哈哈哈，数据规模反推时间复杂度真的是基操了，但是这个技能真的只有竞赛有用，求职的朋友们没必要太关注，毕竟正常点的面试官不可能会傻乎乎告诉你我这个题输入是个什么数据量的。
周赛对于求职的朋友们更大的意义还是在一个有限时间（时间有限所以有压力）的环境内尽可能地解决遇到的新问题的能力，从这个角度来还原面试的现场，对自己的水平进行检测。但单纯对于面试的话，刷题量到了一定水平后，还是模拟面试更能提升自己的能力，毕竟面试考察的远不止你能不能做出那一道题
关于什么时候刷题量算足够，我个人认为如果能稳定周赛保3争4的话（以前19.20年我还在打的时候是通常周赛是1e2m1h的配置，所以换句话说也就是1e2m能出，偶尔也能a一下h），求职方面基本就没有问题了，毕竟就算真出了你没见过不会的h，那你也至少能拿出个暴力解吧，逐步优化一下，沟通好的前提下其实对于大部分不是真的要黑你的面试官而言也足够了
最后一个建议是别气馁，有时候就是运气不好罢了，相信自己的能力，别跟自己过不去。来自一个当年rank2200分排名前500被谷歌电面easy题然后挂了的过来人：）最后上岸的面试甚至没问过我任何算法题

随便打了几场的被pip选手 (无任何竞赛经验)。除了一场三题 ，目前全是四题。但比分也不是特别高

补充内容 (2022-03-18 14:05 +8:00):
这周update目前rating 2393。。。。

补充内容 (2022-03-19 23:00 +8:00):
今天早赛Biweekly74 美服上排名是15，和国服合起来的话前50吧。
补充一下：虽然没有任何竞赛经验，但脑袋属于还可以那种。主要用c++ 和 java

补充内容 (2022-03-20 12:12 +8:00):
Weekly 285挺难的。才300人左右ak。勉强比赛前10min ak

感谢分享！已加米！

感谢分享，加米了！请问没搞过竞赛的人想上2000分大概需要多少刷题量？上2000分是不是每次都得4题全过

好久好久没听到有人打ACM了，已加米，小兄弟加油。

感谢楼主，mark一下

katwang 发表于 2022-3-16 09:58
感谢分享，加米了！请问没搞过竞赛的人想上2000分大概需要多少刷题量？上2000分是不是每次都得4题全过

每次都4题的话我估计够2700了

我都习惯了，每次3-4题的就unrated，每次2题的就不取消，已经快要2000分不保了，气死
然后楼主你的dp[ i ][j]的[ i ]被系统当成斜体代码吞掉了

katwang 发表于 2022-3-16 07:58
感谢分享，加米了！请问没搞过竞赛的人想上2000分大概需要多少刷题量？上2000分是不是每次都得4题全过

其实手速快的话，半小时过前三题然后开始挂机也能上2000（

一剑终情 发表于 2022-3-16 12:10
我都习惯了，每次3-4题的就unrated，每次2题的就不取消，已经快要2000分不保了，气死
然后楼主你的dp[ i ] ...

原来如此……我说咋全变斜体了hh