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

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

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

展开讨论

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

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