讨论/综合讨论/📣 全新「周赛评分算法」即将上线,现邀扣友们前来出谋划策!/
📣 全新「周赛评分算法」即将上线,现邀扣友们前来出谋划策!

image.png

0x00 背景简介

力扣周赛一直是力扣以及资深用户非常重视的竞赛,它意在给大家的刷题带来更大的挑战性以及成就感。然而,由于一些设计缺陷,力扣周赛的评分算法存在一定的局限性,使得它不能充分体现平台用户的水平。

基于以上的背景,力扣团队决定重新设计一个评分算法。在进行了一系列调研以及实验后,我们决定试用一种由 ELO 以及 Codeforces 修改得来的算法。

0x01 新算法的目标

通过这个算法,我们想要解决旧算法的以下问题:

  1. 用户在参加了很多次比赛以后,旧算法的分数更新非常小:

image.png

  1. 旧算法下,用户如果忘记参赛,分数会被扣非常多:

image.png

我们对 “忘记参赛” 的定义为:用户报名了,但没有 任何 提交(包括错误的提交)。

在解决旧问题的同时,我们需要避免引入新的问题:

  1. 在解决问题 1 的同时,分数不能波动太大。

  2. 我们会把忘记参赛的人特判出来,不算在参赛者里。但是为了避免 “保分” 的现象,依然需要给忘记参加的用户一些惩罚

0x02 ELO 算法介绍

原始的 ELO 算法适用于 1 vs 1 的比赛

设比赛前用户 A 的分数为 RAR_A,B 的分数为 RBR_B,则 A 对 B 的期望胜率为

EA,B=11+10(RatingB−RatingA)/400E_{A, B}=\frac{1}{1+10^{(Rating_B-Rating_A)/400}}

在一场比赛后,A 的新分数变为

RatingA′=RatingA+K(SA−EA,B)Rating^\prime_A=Rating_A+K(S_A-E_{A, B})

其中 SAS_A 是 A 的真实比赛结果(胜 = 1,和 = 0.5,负 = 0),K是权重,在传统的 ELO 算法中通常是常数。

0x03 新算法介绍

由于 ELO 算法是用于 1 vs 1 的比赛,而我们的周赛本质上是多人 free-for-all 比赛,所以我们需要对算法进行一些修改。本算法的核心思想就是在多人比赛中,每位参赛者相当于与其他参赛者都各自进行了一场比赛,对于每位参赛者,排名在其前的相当于胜,排名在其后的相当于负,没有平局。

我们首先算出每位参赛者 i 在比赛后的期望排名 ERankERank(Expected Ranking),它等于其他参赛者对该参赛者的期望胜率之和,即

ERanki=∑j=1nEj,i+1(j≠i)ERank_i=\sum^n_{j=1}E_{j, i}+1 (j \neq i)

之后算出期望排名与实际排名 RankiRank_i 的几何平均 mim_i

mi=ERanki×Rankim_i=\sqrt{ERank_i \times Rank_i}

然后可以使用二分搜索算出参赛者在比赛后的期望分数 ERatingiERating_i(Expected Rating),它满足如下公式

∑j=1n11+10(Ratingj−ERatingi)/400+1=mi\sum^n_{j=1}\frac{1}{1+10^{(Rating_j-ERating_i)/400}}+1=m_i

其中

Δ=f(k)×(ERatingi−Ratingi)\Delta = f(k) \times (ERating_i - Rating_i)

其中 kk 是该参赛者曾经参加过的比赛次数,f(k)f(k) 函数初始值为 0.5,随着比赛次数增多会逐渐收敛到 0.2222...,即 2 / 9

最后得到新分数

Ratingi′=Ratingi+ΔRating^\prime_i=Rating_i+\Delta

此外,对于忘记参赛的用户,我们目前采用了最后的【大家来讨论】一节中的第一个选项的做法,并不参与分数的计算,而是单独扣分。

0x04 新旧算法结果对比

下面的图片是第 83 场周赛到第 167 场周赛(包含双周赛)使用新算法计算的中国区前 10 名,初始分数为 1500。

每张图中上图是每场比赛后的分数,下图是每场比赛对应的排名:

0x05 新中国区前 10 名

0x06 一些结论

  • 从图上可以看出,新的算法可以有效解决分数收敛过快的问题,同时在用户参赛一定场次以后,分数依然会根据排名有可见的波动。

  • 经过我们的对比,用新算法得到的前十名的平均竞赛排位比用旧算法得到的更靠前,说明新算法可以更准确地反映选手的算法水平。

  • 新算法对最近几场比赛更为看重,在近期的比赛中排名靠前的选手的分数普遍更高。相比旧算法,新算法更具时效性。

0x07 更多数据

使用新算法计算后的中国前 1000 名的分数以及排名信息请见以下表格:

【👉 戳我】

0x08 大家来讨论

  • 力扣平台非常重视用户的成长。我们观察到有一些用户在一段时间内的水平得到了很大的提升,但由于他们参加了很多场周赛,每次的加分没有真实反映他们的算法水平。所以在这里征询以下大家的意见,我们是否需要赛季?如果需要的话,我们提供两个长度选项:

    • 半年

    • 一年

  • 我们应该如何给忘记参赛的用户惩罚?我们提供两个选项:

    • 算分数的时候扣一个固定百分比的分(如 33%),e.g. 如果比赛前是 2000 分且忘记参赛了,那么比赛后就是 1940 分。(目前采用的方案)

    • 一年(或者一赛季)一次【免死金牌】,忘记参赛也不扣分。第二次及以后的忘记参赛会以输给所有人来计算分数。

展开讨论
共 36 个讨论

开发里有没有打撸啊撸或者农药的小伙伴,你们可以参考游戏的分级制度啊,赛季制度,段位制度,排位赛制度,充钱制度就先别学了

26

支持周期一年的赛季 √

顺便一提,排名提高了好几百,支持新算法,哈哈

13

1、可以有赛季,全体评分(即目前的评分)和赛季评分共存。个人认为赛季不宜过长,半年比较合适。
2、忘记参赛的用户惩罚,第一个选项我不赞同,理由是固定百分比,改成固定分数比较合适,因为分数高的用户参赛次数多,一次忘记参赛在所有报名的比赛中所占比例小,如果固定百分比扣分,就是没有考虑到不参赛的次数占报名总次数的比例。第二个选项我比较赞同,一赛季一次免死金牌比较合适,一个小的建议是第二次及以后的忘记参赛按照该次比赛得零分计算分数(每次比赛四道题根据难度高低有各自的分数,正确提交即可得到该题分数,零分意味着没有一道题正确提交,可能是只有错误提交或者没有任何提交,我认为忘记参赛应该和得零分等同,就像高考缺考和参加考试但是全部题都做错的结果一样都是零分)。
3、提一个另外的建议,和周赛评分算法不直接相关,但是可能间接相关。目前的周赛规则为,每次提交只有两种可能,正确提交和错误提交,无论是答案错误还是TLE、MLE都是错误提交,正确提交得全部分,错误提交得零分。为了使比赛更具备区分度,建议考虑根据测试用例的通过率进行评分,通过全部测试用例得全部分,通过部分测试用例得部分分,具体得分和测试用例通过率的关系每道题都可以不一样,但是计算测试用例通过率的时候必须考虑所有的测试用例,而不是只要有一个测试用例不通过就不考虑后面的测试用例,例如一道题有100个测试用例,一次提交的代码没有通过第11个测试用例和第21个测试用例,其余的测试用例都通过,则这次提交的测试用例通过率应为98/100(而不是10/100或19/100)。
如果引入部分得分的规则,比赛排名依然是优先根据总得分降序排列其次根据总时长升序排列。错误提交加时的规则为:如果一道题的某次提交的得分高于之前的每次提交的得分,则更新该题得分,同时该题的错误提交次数为最后一次提交之前的总提交次数。
举例:5分题,有多次提交,每次提交的得分依次是1分、2分、3分、4分、4分、3分、5分,则每次提交之后,该题的得分和错误提交次数依次是:1分0次、2分1次、3分2次、4分3次、4分3次、4分3次、5分6次。
如果引入部分得分的规则,还有一点关于比赛要更改的是:如果有错误提交,则应该显示该次提交的得分以及测试用例通过率,测试用例通过率可以是直接显示通过率的百分比,或者显示“通过测试用例数/总测试用例数”,关于错误信息,不能显示具体测试用例,而只能显示错误类型(例如编译错误、答案错误、超出时间/空间限制),这样是为了防止作弊。等到比赛结束以后,从题库进入题目作答,则和正常作答一样,显示错误的具体测试用例。
引入部分得分的规则对于技术的实现可能会有困难,但还是希望官方能够考虑,因为引入部分得分的规则可以使比赛更具有区分度,也会使比赛更有趣,比赛的策略也会有所调整。

11

建议7月开启赛季+3月开启第二赛季。一年两次排位刷新!对应春招秋招

3

求个用户天梯分对应名称颜色 like CF

3

作为一名刚加入不久的新人也来提提建议。

  1. 赛季问题
    建议每一年作为一个赛季。 因为每次秋招也是针对某一年毕业的学生。 可以通过一年的学习来判断自己的实力是否够面试。另外, 如果迟迟不更新会导致分数“通货膨胀”比较严重。(典型例子如cf 2100+不一样)。

  2. 忘记参赛。
    建议参考cf平台上的, 只要未提交就不算做没有参加。 (但是提交错误一题也没过就算输给所有人了)

@stormsunshine 和他的第三条我有些许不同意见。
如果说每次四道题的区分度太小, 我们可以这样。
将每次的第三题和第四题分别出一个easy版本和hard版本(例如数据范围不同,限制条件差异)。 但不可直接改为IOI赛制。 因为那样容易出现暴力乱搞的情况(NOIP和现在的CSP都快成为暴力大赛了)。 因此如果说最后的7分题改为简单和困难两个版本, 分别占2和5分, 这样可以使更多的同学在三题过后有题可以做并且提高区分度。 而最后的5分减少了因为最后一题分值太大导致做不出最难的题就拿不到高分的现象。 更容易在赛季中上分。

举个例子:
在n * m的棋盘上放满1 * 2 的骨牌, 问放置方法有多少种。 结果需要mod 998244353.

easy: n = 2, 1 ≤m≤\leq m \leq 8
hard: 1 ≤n,m≤\leq n, m \leq 8

另外, 我再加一条建议, 虽然感觉很容易引起攻击, 但我仍然要说一下。

在这种比赛赛中出的题目, 建议数据范围可以开的区分度更强一些。 象周赛170中有同学反应出T2可以用暴力优化过, 但这显然不是出题人的本意。 这道题难度为Medium即需要用效率较高的算法通过。

标程时间复杂度 建议数据规模下限 建议数据规模上限
O(n!)O(n!) 8 10
O(3n)O(3^n) 8 12
O(2n)O(2^n) 12 24
O(n4)O(n^4) 50 100
O(n3)O(n^3) 200 500
O(n2logn)O(n^2logn) 782 1536
O(n2)O(n^2) 2000 1e4
O(nn)O(n \sqrt{n}) 5e4 1e5
O(nlogn)O(nlogn) 2e5 5e5
O(n)O(n) 1e6 1e7
O(logn)O(logn) 1e9 1e18

按照以上建议扩大部分题目数据规模更能达到比赛效果。本数据参考自codeforces平台。 该平台因为评测机性能比较高, 采用了较强的数据, 以避免不符合题目要求的程序通过。

2

支持忘记比赛要有惩罚,不过按照百分比来扣分对于分高的选手不太公平。
建议改成扣固定分数,然后划一个分数线,低于此的就不再扣分了,或者阶梯制,比如分数低于某某的忘记一次扣 20,否则扣 50 之类。

2

什么时候上线呢

2

@LeetCode 新排名啥时候更新啊?

1

支持新算法,觉得各种不同的比赛制度可以分开统计排名,最后分开显示。就跟匹配赛和排位赛一样的制度。