写这段文字的时候，青鱼已经连续 42 个小时没有睡觉了，如果写出来的东西很烂，那么对不起。

跟自己斗争了一整天后还是决定找一个地方简单写一点没有营养的文字。

很对不起所有对我有期望的网友们，小青鱼还是没有做到 —— 或者说，已经不知道怎样才能做到。从一开始小青鱼就明白，中国大陆没有身份的申请人想进入 MIT 有怎样的难度。过去的五个月，小青鱼确实已经尽了全力，从自己的文书到去要每一封 letter，以及去到 Boston，去到 Cambridge， 跟 admission office 去线下分享我的成长经历，分享 Universal Cup。然而，小青鱼终究还是太没实力，没有展示出独特的闪光点能让这所学校选择我。

也许在一开始，我对 MIT 的申请就没有任何机会 —— 我来自不入流的高中，没有进入过国家队，也没有其他国际奖项。无论在 MIT 的网友们怎么告诉小青鱼 “青鱼一定能赢的”，小青鱼心中也早就明白 pi day 那一天的结果。小青鱼自己就是一个很奇怪的人类，在过去几年中扮演着自己想要出演的角色，在算法竞赛圈子里尝试构建一个自己的王国。在 NOI 训练期间创建了 QOJ，在高中 take a gap year 去创办 Universal Cup，又或是花了几个月，靠着自己半斤八两的算法竞赛水平，参与命题了一场又一场的比赛。也许是由于自己天生的性格，又或许是因为我接受的家庭与教育经历，小青鱼似乎非常抗拒在某个时期做应该做的事情。小青鱼如果循规蹈矩，也许当时就该抓住机会选择转学到那个地方，在那里参加选拔，最终参加 IOI。可小青鱼如果真这么听话，当年又为什么能够在兖州偷偷去搞算法竞赛，进入到这个圈子呢。也许正因为自己觉得人生就该不务正业，感受那股劲，所以才决定举起长茅，冲向风车。

话说的有点远，小青鱼在过去一年承受的打击实在太大，有好多次没能控制自己，在各种小群内宣泄自己的情绪。也是在去年，小青鱼感到了前所未有的自卑感，发现和我玩在一起的网友们，在我同龄时取得了远远超越我的成就。我是个坏东西，情感能轻松左右我的思想，让我变成了我不喜欢的样子。真的非常感谢所有包容小青鱼走过这一困难时期的朋友们，能让小青鱼没有被 2024 年的多次连击打倒，还能站起来直面自己的恐惧。

只可惜，小青鱼最后还是没有获胜。非常感谢在波士顿期间遇到的所有朋友们，感谢与我进行友好交流的 Alex，Brian，Eva，ETK 老师，丁老师，戴老师，邓老师，谦谦，JV 老师，以及很多很多其他第一次见面的网友们。非常感谢大家对我的认可与鼓励，Boston 这座城市很美丽，小青鱼度过了很开心的两周。只是很抱歉，小青鱼没有能力能够加入你们的 campus，在九月与大家再度相会，能够和你们度过一段同学的时光。

最后，祝贺所有被 Class of 2029 录取的朋友们，祝贺咋克，Eva 老师，wxb 老师，以及其他小青鱼不认识的优秀的同学们。你们的实力远远超过了我，祝愿你们能够在 MIT 成功，也希望小青鱼能够顺利找到自己的学上。

This is the draft of the problems of the 2nd Universal Cup Finals. We expect to officially release a version of this document in a few months. If you find an error, please send an e-mail to admin@qingyu.us or a private message to me (@Qingyu) about it.

This year, we received 98 problem submissions from 60 different proposals all over the world. We admitted 15 problems to our pool (and used 13 of them in the end), and shortlisted 5 more problems for backup.

Congratulations to USA1 for the title as The 2nd Universal Cup Champion! As the team got the highest rating in online stage and won the semifinals by a wide margin, they were considered favorites to win the title. They lead the contest by solving 7 problems in the first two hours of the contest, and secured their position by solving a total of 10 problems. Very impressive!

Expected Difficulties (Easy to Hard)

Expected Medals Cut-off

Proposed by Lynkcat.

This analysis is only a draft. Detailed analysis will be added a bit later.

sol：可以发现如果两个障碍形如 $(x,y+1),(x+1,y)$ 那么 $(x,y),(x+1,y+1)$ 也可以被填为障碍。不断做这个过程直到没有这样的两个障碍。最后可以得到若干个连通块，每个连通块形如：占据了若干行，每行是一个区间，区间的左右端点单调不降。

考虑从 左上角 开始，每次能往下走就往下走直到走到矩形的下边界或者右边界。如果走到右边界直接输出 $0$。这样得到一条路径 $P$。再从 右下角 开始，每次能往左走就往左走，走到左边界（走到上边界无解），这样得到一条路径 $Q$。求出 $P,Q$ 的交点，考虑一条新路径 $L$ 是由 左上角 沿 $P$ 走到交点然后沿着 $Q$ 走到 右下角。我们称这条路径 $L$ 是询问矩形的真下边界。

类似的方法求出矩形的 真上边界，可以证明答案即为 两个路径围成的区域面积$-$两个路径围住的连通块的面积和。

问题在于多次询问 刻画每次的上下边界。可以发现四种走法本质上构成四颗树，接下来要做的是建出树之后使用差分技巧+倍增处理出答案。

Proposed by Kubic.

This analysis is only a draft. Detailed analysis will be added a bit later.

考虑 $a$ 的前缀和数组 $b$。

每次操作相当于是选择 $i\in [0,n)$ 满足 $b_i< b_{i+1}$，然后将 $b_i$ 变为 $b_{i+1}$ 或将 $b_{i+1}$ 变为 $b_i$。

我们希望通过这个操作使得 $b$ 单调不降。

设最终的 $b$ 为 $c_0\dots c_n$。

可以发现，一定能将 $c$ 划分为若干个值相等的区间，并且对于每一个划分出的区间 $[l,r]$，一定存在 $x\in [l,r]$，满足 $b_l\le b_x\le b_r$，且 $c_{l\dots r}$ 全部都是从 $b_x$ 扩展而来的。

对于这样的一组 $l,r,x$，可以知道其代价为 $r-l+\sum\limits_{i=l}^x [b_i>b_x]+\sum\limits_{i=x}^r [b_i< b_x]$。

暴力转移为 $O(n^2)$ 或 $O(n^3)$。

考虑钦定一组 $0=x_0\le x_1\le\dots\le x_m=n$ 代表转移过程中的关键元素。对于相邻的 $x_k,x_{k+1}$，我们要求 $b_{x_k}\le b_{x_{k+1}}$，它们之间的贡献为：$\min\limits_{y_k}\left(x_{k+1}-x_k-1+\sum\limits_{i=x_k}^{y_k} [b_i< b_{x_k}]+\sum\limits_{i=y_k+1}^{x_{k+1}} [b_i>b_{x_{k+1}}]\right)$。

通过调整法可知，一定存在一组最优解使得 $b_{x_k+1}\dots b_{x_{k+1}-1}$ 中所有元素均 $\notin[b_{x_k},b_{x_{k+1}}]$。

因此令 $f_{i,j,t=0/1}$ 表示考虑 $b_1\dots b_i$，最后一个关键元素为 $x_k=j$，$w=[i>y_k]$ 的答案。

线段树上维护矩阵乘法标记即可做到 $O(n\log n)$。

Proposed by unputdownable.

This analysis is only a draft. Detailed analysis will be added a bit later.

sol

首先，注意到，如果将 $b$ 按降序排序得到 $b_1$，那么 $\text{LIS}(a+b_1),\text{LIS}(b_1+a) \in \{\text{LIS}(a),\text{LIS}(a)+1\}$。

如果这两个相等，那么 $b_1$ 就是答案。

接下来考虑不相等的情况。

记 $A=\text{LIS}(a)$。

由于两边对称，所以不妨设 $\text{LIS}(a+b_1)=A+1,\text{LIS}(b_1+a)=A$。

注意到此时意味着 $\text{LIS}(a+b)\geq A+1$，因为 $b$ 降序排列时是 $\text{LIS}(a+b)$ 最小的时候。

所以如果有 $\text{LIS}(b+a)$ 最大时，即 $b$ 升序排列时，$\text{LIS}(b+a)\leq A$，那么必定无解。

接着考虑构造一个 $b$ 使得保持 $\text{LIS}(a+b)=A+1$ 且 $\text{LIS}(b+a)=A+1$。

后者必然可以做到，否则是上述无解情况。

这个构造其实是简单的，只要在 $b_1$ 中反转一个最短的后缀使得 $\text{LIS}(b+a)=A+1$ 可以成立即可。

记这个解为 $b_2$，需要检查一下是否有 $\text{LIS}(a+b_2)=A+1=\text{LIS}(b_2+a)$，若是，则有解。

否则此时 $\text{LIS}(a+b_2)>A+1=\text{LIS}(b_2+a)$，可以证明其无解：

首先此时 $a+b_2$ 的 $\text{LIS}$ 必然包括 $b_2$ 反转的那个后缀，易证。

若是存在解 $b_3$，记 $\text{LIS}(b_3)=\text{LIS}(b_2)+k$

容易证明 $\text{LIS}(a+b_3)=\text{LIS}(a+b_2)+k$。

且 $\text{LIS}(b_3+a) \leq \text{LIS}(b_2+a)+k$（由 $b_2+a$ 的 $\text{LIS}$ 形态易证）。

带回 $\text{LIS}(a+b_2)>A+1=\text{LIS}(b_2+a)$ 即可推出矛盾。

所以此时无解。

Proposed by Qingyu.

This analysis is only a draft. Detailed analysis will be added a bit later.

注意到 $k$ 个白色格子最多覆盖 $2k + 2$ 个内部点，因此我们首先有 $2k+2 \geq (n-1)(m-1)$。

我们发现只要clue不在边界上，那么这个下界总是可达的。在非角落的边界上第一步会浪费 2 个点，在角落前两步会浪费 4 个点，对应分别会 -1 和 -2。

注意特判 $\min(n,m) = 1$、$\min(n,m) = 2$ 以及 $2 \mid (n, m)$ 的情况，实现细节有一些多。

Proposed by xtqqwq.

Analysis will be added a bit later.

Proposed by lanos212.

This analysis is only a draft. Detailed analysis will be added a bit later.

发现考虑水珠移动很困难，因为水珠的位置是不确定的。

考虑相对移动，移动这个矩形网格区域，而不是水珠。

这样发现一个格点如果被 $K$ 个矩形包含，那么有 $K+1$ 种情况：

• 不放水珠。
• 在第 $1,2,\cdots,K$ 个矩形区域放水珠。

那么只要把每个格子的 $(\text{被矩形覆盖次数}+1)$ 全部乘起来即可。

注意当移动后，矩形不包含某格子时，这个格子都要立即累乘进答案，并且清空覆盖次数，因为被风吹出去的水珠不会再吹回来。

我们需要优化这一过程，具体可以单独考虑某一列的格子如何计算答案。

考虑如果某一秒时，这一列不被矩形包含，那么这一列的所有格子覆盖次数就清空了。

那么只需要对这一列被矩形覆盖时间的每个连续段计算答案即可。

假设这一列被连续覆盖了 $k$ 秒，可以考虑其从下往上每个格子被覆盖次数：

• 当 $k < N$ 时，形如 $1,2,\cdots,k,k,k,\cdots,2,1$。（中间有 $N-k+1$ 个 $k$）
• 当 $k \ge N$ 时，形如 $1,2,\cdots,N,N,N,\cdots,2,1$。（中间有 $k-N+1$ 个 $N$）

那么对于 $k=1,2,\cdots,T$，分别预处理该列 $(\text{被矩形覆盖次数}+1)$ 的乘积。

这一部分预处理阶乘，使用快速幂即可做到 $O(T \log T)$。

现在要维护所有列的覆盖次数并且做到实时计算并清空未被覆盖的列。

由于 $|d_i|$ 比较大，显然不能直接区间加暴力清空。

考虑对每个当前正在被覆盖的列，记录其开始被覆盖的时间点，清空时只需要作差即可得到覆盖总时长。

然后使用 deque 维护每一个被覆盖时间相同的段即可，每次将移出矩形的列区间清空，加入矩形的列区间覆为当前时间。

注意当 $|d_i|\ge M$ 时要把整个 deque 清空。

时间复杂度 $O(T(\log T+\log N+\log M))$，瓶颈在于快速幂。

Proposed by quailty.

This analysis is only a draft. Detailed analysis will be added a bit later.

答案圆半径不小于最大圆的半径，考虑大于最大圆的半径的情况，那么圆并的圆弧边界实际上不构成限制，只有顶点构成限制，求出所有圆并顶点的 V 图，V 图的顶点是可能的候选圆心，取出这些候选圆心可以得到对应的候选圆。要判断一个候选圆是否合法，只需要判断圆心是否在圆并的圆弧拉直后的区域里，必要性是显然的，充分性可以通过分析不可能出现误判合法的情况进行证明，此处略去细节。

综上所述，具体算法流程如下：

1. 使用极角排序+扫描线求出圆并，这部分复杂度是 $O(n^2\log{n})$，理论上可以通过求解 Power Diagram 做到 $O(n\log{n})$。
2. 使用半平面交算法求出圆并顶点的 V 图的顶点，可以通过 Power Diagram 的性质证明圆并顶点最多有 $6n$ 个，这部分复杂度也是 $O(n^2\log{n})$，或者随机打乱半平面之后逐次切割凸多边形做到期望 $O(n^2)$，理论上也可以做到 $O(n\log{n})$。
3. 判断每个候选点是否在圆并的圆弧拉直后的区域里，使用经典的回转数算法可以做到单次 $O(n)$ 判断，由于候选点最多是 $18n$ 个，这部分复杂度是 $O(n^2)$，理论上可以通过扫描线做到 $O(n\log{n})$。

Proposed by Elegia.

This analysis is only a draft. Detailed analysis will be added a bit later.

首先要分析解的结构, 根据线性方程解的维度的扩域不变性, 不妨在代数闭包 $K = \overline{\mathbb{F}_{p}}$ 上考虑问题.

在代数闭域 $K$ 上, 特征多项式完全分裂, 对于每个特征值 $\lambda$, 我们首先记广义特征空间 $V_\lambda = \bigcup_{n\to\infty} \ker((A-\lambda I)^n)$, 根据 $AB=BA$ 可以得到它是 $B$-不变子空间, 所以我们只需要对每个 $A|_{V_\lambda}$ 考虑 $B$ 的解空间维数, 最后加起来.

现在假设 $A$ 唯一的特征值是 $\lambda$, 记 $\lambda_i = \dim \ker (A^i) - \dim \ker (A^{i-1})$, 对于 Jordan 块的理解告诉我们 $\lambda_1 \geq \lambda_2 \geq \cdots$ 是一个整数拆分. 经过一定的手玩可以得到, 解空间的维数此时是 $$\sum \lambda_i^2.$$

显然我们是很难真的做 $K$ 上的线性代数的, 但是 $\mathbb F_p$ 上的矩阵, 我们有 $O(n^3)$ 的一个简单的随机化算法求出它的有理标准型相应的多项式 $\cdots \mid p_2 \mid p_1$.

做法大概是这样: 随机一个向量 $v$, 求出最小多项式 $p_1(A)v=0$, 然后在商空间上再随机一个向量, 这么搞出 $p_2(A)v=0$, 以此类推, 经过比较精细的实现可以发现这是 $n^3$ 的.

每个 $p_i(x)$ 给出是 $A$ 的每个特征值的一个极大 Jordan 块, 把 $p_i(x)$ 不断做无平方因子分解可以拆出这些 Jordan 块的长度.

最后在广义特征空间的第 $i$ 层, 我们可以得到一些多项式 $\cdots \mid q_{i2}(x) \mid q_{i1}(x)$, 由于这些多项式无重根, 他们的次数就足够揭示出每个特征值对应的 $\lambda_i$, 足够我们求出答案.

Proposed by quailty.

This analysis is only a draft. Detailed analysis will be added a bit later.

太简单了，不写了。

Proposed by skyline.

This analysis is only a draft. Detailed analysis will be added a bit later.

我们首先先做两个转化：

1. 把$0$变成$-1$然后求前缀和，这样一来，区间[l, r]的绝对众数是 $1$ 等价于 $s_r-s_{l-1} \geq 1$ ($0$是对称的)
2. 把相同的相邻 $b_i$ 合并。这样一来，找到连续 $k$ 个绝对众数是 $1$ 的区间等价于找到$s_r-s_{l-1} \geq k$ ($0$是对称的)

接下来，我们令 $f_i$ 表示只考虑前缀，合并后第 $i$ 个大区间的右端点最小是多少。设合并后一共有 $m$ 个区间。

下面要证明， 对 $1 < i < m$，第 $i$ 个区间（由对称性，不妨设这个区间的要求是$s_r-s_{l-1} \geq k$）的右端点可以是 $j$ 等价于：$j > f_{i-1}$ 且 $s_j-min_{t=f_{i-1}}^{j-1}s_t \geq k$。

当 $j > f_{i-1}$ 且 $s_j-min_{t=f_{i-1}}^{j-1}s_t \geq k$。即存在 $f_{i-1} \leq t < j$ 满足 $s_t \leq s_{f_{i-1}}$ 且 $s_j-s_t \geq k$，此时原来 $f_{i-1}$ 为第 $i-1$ 个区间右端点的方案只要把第 $i-1$ 个区间的右端点改成 $t$ ，第 $i$ 个区间的右端点设为 $j$ ，就是一个合法的第 $i$ 个区间右端点是 $j$ 的前 $i$ 个区间的方案；

当 $j$ 可以是右端点，假设对应的方案里第 $i-1$ 个右端点是 $t$ ，由定义有 $f_{i-1} \leq t < j$ 且 $s_j-s_t \geq k$，原条件自然满足。

有了这个证明之后，我们可以先顺着扫求出 $f_1$，然后用上面的检验方法顺着扫求出 $f_2$ 至 $f_{m-1}$，最后确认 $n$ 是不是合法的第 $m$ 个区间右端点。

时间复杂度是线性的。

Proposed by Little09.

This analysis is only a draft. Detailed analysis will be added a bit later.

无解条件：$b$ 数组每项相同，且存在至少一个 $i$ 满足 $a_i\ne b_i$。

充分性：不妨设 $b_i=w$。考虑最后一次操作，一定会选择一个位置乘 $x$，由于要变成 $w$，所以 $x$ 是 $w$ 的因数，那么另一边 $\bmod x$ 就不可能变成 $w$。

必要性考虑构造证明：

找到一个比 $3\cdot n$ 大的质数 $P$。

首先我们先按 $b_i$ 排序。我们用 $O(1)$ 次操作把 $a_1$ 变为 $1$，其中涉及的乘法操作给 $a_n$。接下来考虑 $a_2\sim a_{n-1}$ 这些东西我们希望用 $2(n-2)$ 次操作让它们直接变成 $b_2\sim b_{n-1}$。考虑 $a_i\to b_i$，先乘一个 $\ge 3$ 的最小的数 $k$ 使得 $a_i\cdot k> 2\cdot b_i$，然后用一次取模操作变成 $b_i$，这里会产生多余的两次操作，一次是模 $k$，一次是乘 $(a_i\cdot k-b_i)$，我们把模操作用在 $a_1$ 上，把乘法操作用在 $a_n$ 上。

这样经过 $n-2$ 次后，$a_1=1$，$a_n$ 是一个很大的数，但一定不是 $P$ 的倍数。接下来只考虑 $a_1$ 和 $a_n$ 即可。那么我们先求出 $a_n$ 在模 $P$ 意义下的逆元，如果不是 $1$ 那么给 $a_n$ 乘上这个数，取模操作在 $a_1$ 上。接下来给 $a_n\bmod\ P$，那么就变成 $a_1=P,a_n=1$，再操作 $2$ 就变成 $a_1=1,a_n=2$。

最后我们发现 $a_1=1,a_n=2$ 可以扩展成任意 $(x,y)$ 满足 $x\ne y$ 的对。方法很多，这里给一种。首先如果 $b_1\ne 1$，那么我们可以先扩展成 $(b_1,1)$ 再用一次操作；否则我们直接扩展成 $(1,b_n)$。最后如果两个数顺序不对，那么把 $(1,2)$ 变成 $(2,1)$ 即可。从 $(1,2)$ 到 $(1,x)$ 也是简单的，如果 $x$ 是偶数那么直接乘上去，否则乘到 $(1,x+1)$，再操作一次 $x$，变成 $(x,1)$。

Proposed by Larunatrecy.

This analysis is only a draft. Detailed analysis will be added a bit later.

首先给排列重标号使得 $p_i=i$，即初始时每个点自成一个环。

因为这是一棵树，所以每次删除一条边时，两端点一定在不同的环里，操作之后就会合并两个环，因此所有操作结束后一定只有一个环，即 $q$ 如果有 $>1$ 的环那么一定不合法。

另一方面，我们倒着考虑分裂环的过程，因为分裂之后两环据独立的，故我们可以发现所有树边在环内不交。下证这也是一个充分条件：

• 如果我们先择了边 $(x,y)$，那么环被分成 $x\to q_y\to \dots \to q^{-1}_y$ 和 $y\to q_x\to \dots \to q^{-1}_y$ 两部分，记作 $L$ 和 $R$。那么我们就是要选择合适的 $x,y$ 使得 $x$ 和 $R$ 无边，$y$ 和 $L$ 无边。换言之如果按同一个方向给每个点连的边标号，我们要使的 $(x,y)$ 这条边同时是 $x,y$ 的第一条边。任选一个 $y$ ，并选其第一条边连的点作为 $x$，如果这条边也是 $x$ 的第一条边就成功了，否则继续考虑从 $x$ 的第一条出边，因树边不交所以最终一定可以找到这样的边 $(x,y)$，操作之后归纳即可。

那么我们现在就是找多少棵生成树的边在环内不交，我们把环看成序列，那么确定 $1$ 号点和 $n$ 号点连的边之后序列就会被划分成若干不交区间，故我们用区间 DP 解决这个问题。

$f_{l,r,0/1}$ 表示只考虑区间 $[l,r]$ 内， $l,r$ 是否联通的方案数，直接转移是 $O(n^4)$ 的，前缀和优化可以做到 $O(n^3)$。

Proposed by Kubic.

相当于是 $b$ 被划分为若干个段，每次选择一个段，将它砍成两半，并可以选择是否交换这两段的顺序。注意交换两段时只交换对应的 $b$，不交换对应的 $a$。

考虑判断一个 $b$ 是否能得到 $a$。

显然任意一个段 $[l,r]$ 中所有 $a_i$ 和所有 $b_i$ 组成的可重集必须相同，否则一定不能得到目标序列。

对于一个段 $[l,r]$，设 $S_0$ 为一个集合包含所有 $x$ 满足从 $x$ 处断开，并且不进行交换，依然能保证所有段合法，$S_1$ 同理表示进行交换时的所有 $x$。

有重要性质：所有合法的操作可以按照任意顺序进行。

在大部分情况下 $S_0,S_1$ 中至少有一个为空。如果 $S_0,S_1$ 均非空，则一定有 $b_l=b_r=a_l$ 或 $b_l=b_r=a_r$。

设 $dp_{l,r,0}$ 表示当前段为 $[l,r]$，且 $S_1$ 为空的方案数，$dp_{l,r,1}$ 表示当前段为 $[l,r]$，且 $S_0$ 为空的方案数，$dp_{l,r,2}$ 表示总方案数。

考虑如何计算 $dp_{l,r,0}$。$dp_{l,r,1}$ 的计算方法是类似的。

设 $S_0$ 中的最小值为 $x$，我们令它为最先进行的操作。则我们要求左边段 $S_0$ 为空，而对右边段无限制。即；

$$dp_{l,r,0}\rightarrow dp_{l,x,1}\times dp_{x+1,r,2}$$

但这个转移式计算的实际上是 $S_0$ 非空的方案数。我们还需要减去 $S_0,S_1$ 同时非空的方案数。

考虑如何计算 $b_l=b_r=a_l$ 时的方案数。$b_l=b_r=a_r$ 的情况是类似的。

如果 $a_l< a_{l+1}$ 那么显然方案数为 $0$。否则我们有 $a_l=a_{l+1}$。

显然此时 $l\in S_0,r-1\in S_1$，已经满足 $S_0,S_1$ 均非空。因此只要求 $b_{l,r}$ 能够变换到 $a_{l,r}$。

而 $b_l,b_r$ 已经确定为 $a_l$，因此只要求 $b_{l+1,r-1}$ 能够变换到 $a_{l+2,r}$，而这个方案数即为 $dp_{l+2,r,2}$。

总时间复杂度为 $O(n^3)$。

Attachments

• Contest Rules

Overall Schedule

• To contestants: Please wear the blue hoodie on 19th, 21st and 23rd Feb, and the white one on 20th and 22nd Feb.
• To staff and volunteers: Please wear the red hoodie on 19th, 21st and 23rd Feb, and the green one on 20th and 22nd Feb.

Notice

1. On February 19th, there is no group dining. You may order room service and we will cover the cost.
2. For everyday’s breakfast, please use your room card to enter the dining room.
3. For all transportation from Sanyapo Campus, please be at Hotel Lobby, The Amber House Songshan Lake Dongguan in time.
4. If you encounter any unexpected circumstances, please contact volunteers immediately.
5. To ensure the safety of all participants and the smooth operation of the event, please strictly adhere to the on-site safety regulations.
   • During the event, do not leave the designated area without permission, and refrain from climbing, chasing, using open flames, or engaging in any other behavior that may endanger yourself or others.
   • All participants must follow the instructions of staff and volunteers, as well as comply with venue signage and safety notices.
   • If any personal actions (such as ignoring warnings, unauthorized movement, or dangerous activities) result in personal injury, property damage, or other adverse consequences, the individual involved shall bear full responsibility for all resulting liabilities and losses.
   • The event organizers will not be held accountable.

Programming Environment

• OS: Ubuntu 24.04.1 LTS
• Desktop: GNOME Flashback
• Editors: vi/vim, gvim, emacs, gedit, geany, kate
• IDEs: Eclipse, IntelliJ, CLion, PyCharm, RustRover, Code::Blocks, Visual Studio Code
• Contest Control System: DOMJudge 8.3.1

Languages

Conference Information

Linear Systems Surprises

Presenter: __Richard Peng__

Abstract: Algorithms researchers strive to design better ways of solving problems that are central to many disciplines. Systems of linear equations arise throughout engineering and sciences in tasks ranging from physical simulation to data analytics. In many cases where linear systems don’t exactly model the problem, they provide the steps that lead to the solutions. Despite linear systems’ storied history spanning centuries, the current best algorithms for general linear systems, as well as many important subclasses, remain comparatively slow.

Over the last few decades, algorithms researchers developed entirely new approaches to solving linear systems. These progress led to accelerations in many applications, as well as entirely new theoretical frameworks for designing and analyzing algorithms. This talk will briefly overview some of the surprising ways of thinking about approximations, iterative convergences, and algebraic structures that originated from studying linear systems.

An Introduction to Symbolic Program Generation

Presenter: __Ruyi Ji__

Abstract: Large Language Models (LLMs) have recently achieved remarkable success in program generation, particularly in competitive programming. For example, OpenAI reported that its o1 model achieved gold medal-level performance in last year's International Olympiad in Informatics (IOI), and its o3 model attained an estimated rating of ~2700 on Codeforces, ranking among top competitive programmers.

Despite these impressive milestones, current LLMs still suffer from several limitations. One major challenge is their inability to deduce general rules purely from examples, as their inference heavily depends on the presence of natural language. To address this limitation, symbolic approaches — representing a different paradigm of artificial intelligence — offer a complementary solution. Unlike LLMs, which rely on fitting vast amounts of data through large neural networks, symbolic systems represent knowledge via a small set of interpretable rules and perform reasoning by searching through combinations of these rules. While such systems are less effective at handling natural language, they excel at reasoning directly from structured examples.

In this presentation, I will provide an overview of symbolic program generation (i.e., program synthesis) and share recent progress in synthesizing efficient programs and complex algorithms.

Tight Bounds for Retrieval Data Structures By

Presenter: __Tingqiang Xu__

Abstract: Retrieval data structures are data structures that answer key-value queries without paying the space overhead of explicitly storing keys. The problem can be formulated in four settings (static, value-dynamic, incremental, or dynamic), each of which offers different levels of dynamism to the user. In this presentation, I will talk about optimal bounds for the final two settings (incremental and dynamic) in the case of a polynomial universe. This complete a line of work that has spanned more than two decades, and also come with a surprise: the incremental setting, which has long been viewed as essentially equivalent to the dynamic one, actually has a phase transition, in which, as the value size v approaches log n, the optimal space redundancy actually begins to shrink, going from roughly n log log n (which has long been thought to be optimal) all the way down to Θ(n) (which is the optimal bound even for the seemingly much-easier value-dynamic setting).

Practice on medical LLMs

Presenter: __Benyou Wang__

Abstract: Recently, OpenAI's ChatGPT and various open-source community models, such as LLaMA 3, have significantly advanced the development of AI applications. In the medical field, both proprietary and open-source models hold great potential. However, when it comes to solving real-world medical problems, there is still a "last mile" to cover. In this Speech, we will introduce our team's development of the medical large language model, HuatuoGPT, and its multilingual and multimodal extensions, the Apollo series. We will also discuss the technical solutions for HuatuoGPT-o1, which aim to enhance the performance and interpretability of large language models, particularly in the context of longer diagnostic reasoning chains. Finally, we will look ahead to the future development of medical LLMs. Specifically, we will explore the potential of using AIGC technology to create a large number of patient agents to train both human and AI doctors. By doing so, we can accumulate real patient needs and doctor feedback, ultimately working towards the development of generalist medical artificial intelligence (GMAI).

Universal Cup 是一个致力于服务竞赛编程社区的组织，专注于提供高质量的训练资源并举办全球线下赛事。2025 年 Universal Cup 总决赛（即第二届 Universal Cup 总决赛）是本赛事第二赛季的最终比赛。

共有 20 支队伍通过在线比赛、半决赛或线下夏季峰会晋级，将争夺第二届 Universal Cup 冠军的头衔。

竞赛形式

1. 竞赛时长为五小时。在不可预见的情况下，科学委员会主席有权修改竞赛时长。如竞赛形式或时长发生变更，参赛队伍将以统一方式及时获悉。
2. 竞赛题目数量不少于 10 题，且不超过 14 题。
3. 队伍可通过 Clarification Request 提交对题目可能存在错误的申诉。澄清请求必须仅使用英文撰写。
4. 竞赛期间可能发布 Clarification，内容可能包括题目说明、附加细节、额外示例或对题目的修改（包括补充、删除或更改）。
5. 所有 Clarification 信息均仅以英文提供，并会在竞赛现场统一公布。

题目

1. 所有题目陈述仅提供英文版本。
2. 参赛队伍可使用字典或在线翻译工具自行翻译题目内容，官方不提供翻译。
3. 任何题目均不会提供部分分数。
4. 竞赛题目类型包括：

• 标准输入/输出题：程序需从 标准输入 读取数据，并将结果输出到 标准输出。
• 交互题：程序需通过标准输入/输出与 交互器 进行交互。
• 多次运行题：程序将多次运行，每次使用不同的输入数据。
• 仅输出题：参赛队伍无需提交程序，仅提交最终答案。

提交与评测

1. 竞赛评测平台采用 DOMjudge，一个开源自动化竞赛系统。
2. 支持的编程语言包括 C、C++、D、Python 3、Java、Kotlin 和 Rust。
3. 详细的语言版本与规格请参考 TechNote 文档。
4. 每次提交的评测结果仅为通过（Accepted）或未通过（Rejected），不会提供部分分数或错误测试点编号。
5. 未通过的提交将标记为以下之一：

- 编译错误（CE）
- 运行时错误（RTE）
- 时间超限（TLE）
- 结果错误（WA）
- 无输出（NO）
- 输出超限（OLE）

计分、排名与奖项

1. 队伍按照解题数量进行排名，解出相同题目数量的队伍按照 罚时 进行排名。
2. 如罚时相同，则按 最后一个通过题目的提交时间 进行排名。如果仍有相同，将按照以下方式，直到决出所有相同队伍的名次：
   • 所有排名相同的队伍将按照他们的 最后一次通过提交的提交时间（精确到毫秒） 排名。该时间越早的队伍排名越高。没有通过任何题目的队伍的时间被视为 00:00:00.000
   • 如果仍有相同，这些排名相同的队伍将会按照他们在第 2 届 Universal Cup 中的 rating 进行排名。
   • 如果仍有相同，一道用于打破平局的额外题目将决定这些排名相同的队伍的排名。
   • 如果仍有相同，将通过抽签决定这些队伍的排名。
3. 罚时 计算方式为 所有解出的题目的耗时总和 加上 该题目的额外罚时。
4. 题目的耗时是指从竞赛开始到首次通过该题的提交时间，以分钟计算。
5. 题目的额外罚时为 20 分钟 乘以 首次通过前所有未通过的提交次数（编译错误除外）。
6. 未解决的题目不计算罚时。
7. 比赛进行 4 小时后，实时排名将被冻结，之后的提交结果将在榜单上显示为“待定”。
8. 金牌将会颁发给比赛中获得前三名的队伍（共三名）。
9. 银牌将会颁发给比赛中获得第四名至第七名的队伍（共四名）。
10. 铜牌将会颁发给比赛中获得前八名至第十二名的队伍（共五名）。
11. 科学委员会主席有权决定为队伍颁发额外的奖牌。

竞赛环境

1. 每支队伍仅配备 一台计算机。
2. 所有队伍的计算机配置相同。
3. 队伍可自带 鼠标、键盘 或 手写板 进入比赛区域，但不保证所有外接设备都能正常使用。
4. 队伍不得携带 个人计算机、手机、计算器 或其他电子设备进入比赛区域。
5. 技术委员会有权检查队伍携带的外接设备。如有争议，技术委员会主席的决定为最终裁决。
6. 参赛队伍可浏览互联网以获取任何资料。
7. 竞赛期间，禁止与队伍以外的任何人交流。
8. 任何在互联网上分发题解、代码或辅助程序的行为均被严禁。
9. 参赛队伍不得提交恶意代码，包括但不限于攻击评测系统或恶意占用评测资源。
10. 在科学委员会主席指示前，不得触碰比赛工作站的任何设备。

申诉

1. 参赛队伍可对题目内容、提交评测结果或竞赛相关决定提出申诉。
2. 申诉内容必须仅使用英文撰写。
3. 评测裁判将对申诉做出决定，可能会调整竞赛期间的评测结果。
4. 如果对裁判决定仍有异议，可向 Universal Cup 科学委员会主席提交最终申诉。
5. 科学委员会主席的决定为最终裁决。

竞赛委员会

科学委员会

• 主席： Qingyu
• 副主席： jiangly
• 委员： bulijiojiodibuliduo, quailty, Heltion, Lynkcat

技术委员会

• 主席： Qingyu
• 委员： cubercsl, dup4, Tangent

组织委员会

• 主席： chenjb

The Universal Cup is an organization aiming at serving the competitive programming community, dedicated to provide high quality training resources and host onsite global events. The 2025 Universal Cup Final Contest (or The 2nd Universal Cup Finals) is the final contest of the 2nd season of our event.

A total of 20 teams have qualified through online competitions, semifinals, or onsite summer summits to compete for the title of The 2nd Universal Cup Champion.

Contest Format

1. The competition will last five hours. The Chair of the Scientific Committee has the authority to modify the contest duration in the event of unforeseen circumstances. If any changes occur regarding the contest format or duration, participants will be notified in a timely and uniform manner.
2. There will be at least ten (10), but no more than fourteen (14) problems in the contest.
3. Teams may submit claims regarding potential mistakes in a problem via a clarification request. Clarification requests must be written in English only.
4. Clarifications may be issued during the competition. These clarifications may include explanations of problem statements, additional details, extra examples, or modifications to a problem (including additions, removals, or changes).
5. All clarifications will be provided in English only, and notifications will be announced at the competition venue.

Problems

1. All problem statements will be provided in English only.
2. Teams may use dictionaries or online translation tools to translate the statements into other languages. No official translations will be provided.
3. No partial scores will be awarded for any problem.
4. The types of problems in the competition include:
   • Standard I/O problem: Your program must read input from the standard input and write output to the standard output.
   • Interactive problem: The program interacts with an interactor through standard I/O.
   • Multiple-Run Problem: The program will be executed multiple times, each with a different input.
   • Output-Only Problem: Teams do not submit a program but instead submit the final answers directly.

Submissions

1. The judging platform of the competition is DOMjudge, an open-source automated system to run programming contests.
2. The supported programming languages include C, C++, D, Python 3, Java, Kotlin, and Rust.
3. The detailed language specifications should be referred to in the TechNote document.
4. Each submission is judged as accepted or rejected. No partial scores or failed test ID will be given to the teams.
5. Rejected runs will be marked with one of the following:
   • Compilation Error (CE)
   • Runtime Error (RTE)
   • Time Limit Exceeded (TLE)
   • Wrong Answer (WA)
   • No Output (NO)
   • Output Limit Exceeded (OLE)

Scoring, Ranking, and Awarding

1. Teams are ranked according to the most problems solved.
2. Teams who solve the same number of problems are ranked first by the least penalty, with the following tie-breakers in order:
   • the tied teams will be ranked according to their last AC time, in milliseconds. Teams has the earlier last AC time will be ranked higher. Teams did not solve any problems will have the last AC time as 00:00:00.000.
   • if there is still a tie, the tied teams will be ranked according to their ratings on The 2nd Universal Cup.
   • if there is still a tie, the tied teams will be ranked according to an additional play-off task.
   • if there is still a tie, a lucky draw will determine the ranking of all tied teams.
3. The penalty is the sum of the time consumed for each problem solved plus the penalty in that problem.
4. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submission of the first accepted submission, in minutes.
5. The penalty in a problem is twenty (20) minutes times the number of non-accepted submissions before the first accepted submission, excluding the ones with a compilation error verdict.
6. There is no time consumed for a problem that is not solved.
7. The leaderboard will be frozen 4 hours after the contest starts, and the results submitted after 4 hours will be shown as pending on the leaderboard.
8. Gold Medals will be awarded to the Top 3 teams (1st, 2nd, and 3rd places).
9. Silver Medals will be awarded to the Next 4 teams (4th to 7th places).
10. Bronze Medals will be awarded to the Next 5 teams (8th to 12th places).
11. Additional Medals might be awarded at the decision of Chair of the Scientific Committee.

Contest Environment

1. Each team will be provided with one computer only.
2. All teams will have equivalent computing equipment.
3. Teams may bring their own mouse, keyboard, or graphics tablet to the contest area. However, it is not guaranteed that all the external devices could work properly on your workstation.
4. Teams may not bring their own computers, smartphones, calculators, or other electronic devices to the contest area.
5. The Technical Committee may inspect the external devices brought by a team before the contest. In case of ambiguity, the decision of the Chair of the Technical Committee shall be final.
6. Teams are allowed to browse the Internet to access any materials.
7. Teams are prohibited from communicating with anyone outside their team during the contest.
8. The distribution of any problem-solving materials, including ideas, codes, or auxiliary programs, on the Internet is strictly forbidden.
9. Teams may not submit malicious codes, including but not limited to attacks on the judging platform and malicious occupation of evaluation system resources.
10. Do not touch anything at the team workstations until so directed by the Chair of the Scientific Committee.

Appeal

1. Teams may submit an appeal regarding potential mistakes in any problems, verdicts of the submissions, or other contest decisions.
2. Appeals must be written in English only.
3. Judges will give a decision to an appeal, which might change a verdict given during the contest.
4. If you are still not satisfied with the results given by the judges, you may file a final appeal with the Universal Cup Scientific Committee.
5. The decision of the Chair of the Scientific Committee shall be final.

Competition Staff

Scientific Committee:

• Chair: Qingyu
• Deputy Chair: jiangly
• Members: bulijiojiodibuliduo, quailty, Heltion, Lynkcat

Technical Committee:

• Chair: Qingyu
• Members: cubercsl, dup4, Tangent

Organizing Committee:

• Chair: chenjb