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

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 分。(目前采用的方案)

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

展开讨论
力扣 (LeetCode)发起于 2019-12-20
最近编辑于 2019-12-20

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
展开全部 36 讨论