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

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

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

展开讨论

(揉眼睛 ( ‘-ωก̀ )有赛季机制是好的,最好像lol那种,有排位,当然我说的是调动人的积极性向好的方向发展。

展开全部 36 讨论