wyoj-system/app/libs/uoj-contest-lib.php

<?php
define("CONTEST_NOT_STARTED", 0);
define("CONTEST_IN_PROGRESS", 1);
define("CONTEST_PENDING_FINAL_TEST", 2);
define("CONTEST_TESTING", 10);
define("CONTEST_FINISHED", 20);

function g2_g($x) {
	return 1 / sqrt(1 + 3 * $x * $x / M_PI / M_PI);
}

function g2_E($u, $uj, $pj) {
	return 1 / (1 + exp(-g2_g($pj) * ($u - $uj)));
}

function g2_f($x, $delta, $phi, $v, $a, $tau) {
	return (exp($x) * ($delta * $delta - $phi * $phi - $v - exp($x)) 
		/ (2 * pow($phi * $phi + $v + exp($x), 2)))
		- ($x - $a) / $tau / $tau;
}

function calcRatingGlicko2($standings, &$new_rating, &$new_rd, &$new_vol) {
	$TAU = 0.6;

	$n = count($standings);
	$rating = array();
	$rd = array();
	$vol = array();
	for ($i = 0; $i < $n; ++$i) {
		$rating[$i] = ($standings[$i][2][1] - 1500) / 173.7178;
		$rd[$i] = $standings[$i][2][2] / 173.7178;
		$vol[$i] = ($standings[$i][2][3] ?? 0.06);
		if ($vol[$i] <= 0) $vol[$i] = 0.06;
	}

	if ($n == 1) {
		$new_rating[0] = $rating[0];
		$new_rd[0] = $rd[0];
		$new_vol[0] = $vol[0];
	}
	
	for ($i = 0; $i < $n; $i++) {
		$delta = 0;
		$v = 0;

		for ($j = 0; $j < $n; $j++) if ($i != $j) {
			$s = 0;
			if ($standings[$i][3] > $standings[$j][3])
				$s = 0;
			else if ($standings[$i][3] == $standings[$j][3])
				$s = 0.5;
			else
				$s = 1;
			$e = g2_E($rating[$i], $rating[$j], $rd[$j]);
			$v += pow(g2_g($rd[$j]), 2) * $e * (1 - $e);
			$delta += g2_g($rd[$j]) * ($s - $e);
		}

		if ($v < 1e-20) $v = 1e-20;
		$v = 1 / $v;
		$delta *= $v;

		if ($delta > 10) $delta = 10;
		if ($delta < -10) $delta = -10;

		$a = 2 * log($vol[$i]);

		$A = $a;
		if ($delta * $delta > $rd[$i] * $rd[$i] + $v)
			$B = log($delta * $delta - $rd[$i] * $rd[$i] - $v);
		else {
			for ($k = 1; $k < 100 && g2_f($a - $k * $TAU, $delta, $rd[$i], $v, $a, $TAU) < 0; ++$k)
				;
			$B = $a - $k * $TAU;
		}

		$fa = g2_f($A, $delta, $rd[$i], $v, $a, $TAU);
		$fb = g2_f($B, $delta, $rd[$i], $v, $a, $TAU);
		while ($fa * $fb > 0) {
			$B -= $TAU;
			$fb = g2_f($B, $delta, $rd[$i], $v, $a, $TAU);
		}

		$k = 0;
		while (abs($B - $A) > 1e-6 && $k < 100) {
			if (!is_finite($fa) || !is_finite($fb)) break;
			if (abs($fa - $fb) < 1e-15) break;
			$C = $A + ($A - $B) * $fa / ($fb - $fa);
			$fc = g2_f($C, $delta, $rd[$i], $v, $a, $TAU);
			if ($fc * $fb <= 0) {
				$A = $B;
				$fa = $fb;
			}
			else
				$fa = $fa / 2;
			$B = $C;
			$fb = $fc;
			++$k;
		}

		$new_vol[$i] = exp(($A + $B) / 4);
		$new_rd[$i] = sqrt($rd[$i] * $rd[$i] + $new_vol[$i] * $new_vol[$i]);
		$new_rd[$i] = 1 / sqrt(1 / $v + 1 / $new_rd[$i] / $new_rd[$i]);
		$new_rating[$i] = $rating[$i] + $delta / $v * $new_rd[$i] * $new_rd[$i];
		$new_rating[$i] = $new_rating[$i] * 173.7178 + 1500;
		$new_rd[$i] *= 173.7178;
	}
}

/*
 * 新的 Rating 计算函数，采用 Codeforces 算法。
 * 具体算法是：
 * 设参赛前每人的 Rating 是 r_i, 比赛的最终排名是 R_i，那么
 * 首先承认：在先前 Rating 的基础上，i 战胜 j 的概率是 P_ij = \dfrac{1}{1 + 10^{\dfrac{r_j - r_i}{400}}}
 * 立即得到 i 的期望排名 E_i = \sum_{j \ne i} P_ji + 1
 * 显然，真正的排名和期望排名之间的差距，就是 rating delta 的来源。
 * 我们取 S_i = \sqrt{E_i R_i}，二分出一个 u 使得计算出的 S_i = E_i，rating 应当向 u 的方向变化。
 * 取 \delta = \dfrac{u + r_i}{2}，随后我们对 \delta 进行微调。
 * 第一次微调：取 d = \dfrac{-1 - \sum_{i} \delta_i}{n}，将所有人的 \delta 加上 d。
 * 第二次微调：取排名前 s = \min{n, 4\sqrt n} 高的人，让这些人的 rating 变化量之和为零，得到 d。
 * 随后再将所有人的 \delta 加上 d，得到最终的 rating。
 * */
function calcRatingX($standings, &$new_ratings, &$new_rating_rds, &$new_rating_vols) {
	$n = count($standings);
	$rating = array();
	$delta = array();
	$ds = 0;
	for ($i = 0; $i < $n; ++$i) {
		$rating[$i] = $standings[$i][2][1];
		$new_rating_rds[$i] = 0;
		$new_rating_vols[$i] = 0;
	}
	for ($i = 0; $i < $n; ++$i) {
		$l = 0;
		$r = 4000;
		while ($l <= $r) {
			$mid = ($l + $r) / 2;
			$e = 1;
			for ($j = 0; $j < $n; ++$j)
				if ($i != $j)
					$e += 1 / (1 + pow(10, ($mid - $rating[$j]) / 400));
			$s = sqrt($e * ($i + 1));
			if ($e <= $s)
				$r = $mid - 1;
			else
				$l = $mid + 1;
		}
		$delta[$i] = (($l + $r) / 2 - $rating[$i]) / 2;
		$ds += $delta[$i];
	}
	$ds = (-1 - $ds) / $n;
	for ($i = 0; $i < $n; ++$i)
		$delta[$i] += $ds;
	$s = min($n, 4 * sqrt($n));
	$ds = 0;
	for ($i = 0; $i < $s; ++$i)
		$ds += $delta[$i];
	$ds = -$ds / $s;

	for ($i = 0; $i < $s; ++$i)
		$delta[$i] += $ds;
	for ($i = 0; $i < $n; ++$i)
		$new_ratings[$i] = ceil($rating[$i] + $delta[$i]);
}

function calcRating($standings, &$new_ratings, &$new_rating_rds, &$new_rating_vols, $K = 400) {
	$DELTA = 500;

	$n = count($standings);
	
	$rating = array();
	for ($i = 0; $i < $n; ++$i) {
		$rating[$i] = $standings[$i][2][1];
		$new_rating_rds[$i] = 0;
		$new_rating_vols[$i] = 0;
	}
	
	$rank = array();
	$foot = array();
	for ($i = 0; $i < $n; ) {
		$j = $i;
		while ($j + 1 < $n && $standings[$j + 1][3] == $standings[$j][3]) {
			++$j;
		}
		$our_rk = 0.5 * (($i + 1) + ($j + 1));
		while ($i <= $j) {
			$rank[$i] = $our_rk;
			$foot[$i] = $n - $rank[$i];
			$i++;
		}
	}
	
	$weight = array();
	for ($i = 0; $i < $n; ++$i) {
		$weight[$i] = pow(7, $rating[$i] / $DELTA);
	}
	$exp = array_fill(0, $n, 0);
	for ($i = 0; $i < $n; ++$i) {
		for ($j = 0; $j < $n; ++$j) {
			if ($j != $i) {
				$exp[$i] += $weight[$i] / ($weight[$i] + $weight[$j]);
			}
		}
	}
	
	for ($i = 0; $i < $n; $i++) {
		$new_ratings[$i] = $rating[$i];
		$new_ratings[$i] += ceil($K * ($foot[$i] - $exp[$i]) / ($n - 1));
	}
	
	for ($i = $n - 1; $i >= 0; $i--) {
		if ($i + 1 < $n && $standings[$i][3] != $standings[$i + 1][3]) {
			break;
		}
		if ($new_ratings[$i] > $rating[$i]) {
			$new_ratings[$i] = $rating[$i];
		}
	}
	
	for ($i = 0; $i < $n; $i++) {
		if ($new_ratings[$i] < 0) {
			$new_ratings[$i] = 0;
		}
	}
}

function genMoreContestInfo(&$contest) {
	$contest['start_time_str'] = $contest['start_time'];
	$contest['start_time'] = new DateTime($contest['start_time']);
	$contest['end_time'] = clone $contest['start_time'];
	$contest['end_time']->add(new DateInterval("PT${contest['last_min']}M"));
	
	if ($contest['status'] == 'unfinished') {
		if (UOJTime::$time_now < $contest['start_time']) {
			$contest['cur_progress'] = CONTEST_NOT_STARTED;
		} elseif (UOJTime::$time_now < $contest['end_time']) {
			$contest['cur_progress'] = CONTEST_IN_PROGRESS;
		} else {
			$contest['cur_progress'] = CONTEST_PENDING_FINAL_TEST;
		}
	} elseif ($contest['status'] == 'testing') {
		$contest['cur_progress'] = CONTEST_TESTING;
	} elseif ($contest['status'] == 'finished') {
		$contest['cur_progress'] = CONTEST_FINISHED;
	}
	$contest['extra_config'] = json_decode($contest['extra_config'], true);
	
	if (!isset($contest['extra_config']['standings_version'])) {
		$contest['extra_config']['standings_version'] = 2;
	}
}

function updateContestPlayerNum($contest) {
	DB::update("update contests set player_num = (select count(*) from contests_registrants where contest_id = {$contest['id']}) where id = {$contest['id']}");
}

// problems: pos => id
// data    : id, submit_time, submitter, problem_pos, score
// people  : username, user_rating
function queryContestData($contest, $config = array()) {
	mergeConfig($config, [
		'pre_final' => false
	]);
	
	$problems = [];
	$prob_pos = [];
	$n_problems = 0;
	$result = DB::query("select problem_id from contests_problems where contest_id = {$contest['id']} order by problem_id");
	while ($row = DB::fetch($result, MYSQLI_NUM)) {
		$prob_pos[$problems[] = (int)$row[0]] = $n_problems++;
	}

	$data = [];
	if ($config['pre_final']) {
		$result = DB::query("select id, submit_time, submitter, problem_id, result from submissions"
				." where contest_id = {$contest['id']} and score is not null order by id");
		while ($row = DB::fetch($result, MYSQLI_NUM)) {
			$r = json_decode($row[4], true);
			if (!isset($r['final_result'])) {
				continue;
			}
			$row[0] = (int)$row[0];
			$row[3] = $prob_pos[$row[3]];
			$row[4] = (int)($r['final_result']['score']);
			$data[] = $row;
		}
	} else {
		if ($contest['cur_progress'] < CONTEST_FINISHED) {
			$result = DB::query("select id, submit_time, submitter, problem_id, score from submissions"
				." where contest_id = {$contest['id']} and score is not null order by id");
		} else {
			$result = DB::query("select submission_id, date_add('{$contest['start_time_str']}', interval penalty second),"
				." submitter, problem_id, score from contests_submissions where contest_id = {$contest['id']}");
		}
		while ($row = DB::fetch($result, MYSQLI_NUM)) {
			$row[0] = (int)$row[0];
			$row[3] = $prob_pos[$row[3]];
			$row[4] = (int)$row[4];
			$data[] = $row;
		}
	}

	$people = [];
	$result = DB::query("select username, user_rating, user_rd, user_vol from contests_registrants where contest_id = {$contest['id']} and has_participated = 1");
	while ($row = DB::fetch($result, MYSQLI_NUM)) {
		$row[1] = (int)$row[1];
		$people[] = $row;
	}

	return ['problems' => $problems, 'data' => $data, 'people' => $people];
}

function calcStandings($contest, $contest_data, &$score, &$standings, $update_contests_submissions = false) {
	// score: username, problem_pos => score, penalty, id
	$score = array();
	$n_people = count($contest_data['people']);
	$n_problems = count($contest_data['problems']);
	foreach ($contest_data['people'] as $person) {
		$score[$person[0]] = array();
	}
	foreach ($contest_data['data'] as $submission) {
		$penalty = (new DateTime($submission[1]))->getTimestamp() - $contest['start_time']->getTimestamp();
		if ($contest['extra_config']['standings_version'] >= 2) {
			if ($submission[4] == 0) {
				$penalty = 0;
			}
		}
		$score[$submission[2]][$submission[3]] = array($submission[4], $penalty, $submission[0]);
	}

	// standings: rank => score, penalty, [username, user_rating, user_rd, user_vol], virtual_rank
	$standings = array();
	foreach ($contest_data['people'] as $person) {
		$cur = array(0, 0, $person);
		for ($i = 0; $i < $n_problems; $i++) {
			if (isset($score[$person[0]][$i])) {
				$cur_row = $score[$person[0]][$i];
				$cur[0] += $cur_row[0];
				$cur[1] += $cur_row[1];
				if ($update_contests_submissions) {
					DB::insert("insert into contests_submissions (contest_id, submitter, problem_id, submission_id, score, penalty) values ({$contest['id']}, '{$person[0]}', {$contest_data['problems'][$i]}, {$cur_row[2]}, {$cur_row[0]}, {$cur_row[1]})");
				}
			}
		}
		$standings[] = $cur;
	}

	usort($standings, function($lhs, $rhs) {
		if ($lhs[0] != $rhs[0]) {
			return $rhs[0] - $lhs[0];
		} elseif ($lhs[1] != $rhs[1]) {
			return $lhs[1] - $rhs[1];
		} else {
			return strcmp($lhs[2][0], $rhs[2][0]);
		}
	});

	$is_same_rank = function($lhs, $rhs) {
		return $lhs[0] == $rhs[0] && $lhs[1] == $rhs[1];
	};

	for ($i = 0; $i < $n_people; $i++) {
		if ($i == 0 || !$is_same_rank($standings[$i - 1], $standings[$i])) {
			$standings[$i][] = $i + 1;
		} else {
			$standings[$i][] = $standings[$i - 1][3];
		}
	}
}