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 [email protected] 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

A. 铁甲战士

除了最开始，抽牌堆里至少包含一张牌，也就是刚打出的那张。下面默认抽牌堆里已经包含一张牌。可以发现，如果在出剑柄打击后不出耸肩无视，那么后面迟早会把手牌全部出完，无法持久地打下去，所以剑柄打击后必须出耸肩无视。同理，如果出了一张狂怒/全身撞击，那么下一张必须要打剑柄打击。因此除了游戏开头，一定是狂怒/全身撞击，剑柄打击，耸肩无视循环出。对于游戏开头和结尾只有 $O(1)$ 种可能，可以直接枚举。可以发现，一定是一个前缀打狂怒，一个后缀打剑柄打击，直接二分分界点即可。需要写高精度。

B. 小青鱼

如果每次操作是操作一整行/列/对角线，那么题目等价于 3sum 问题，可以用一次 FFT 解决。

那么现在区间怎么做。考虑分块。把 $n\times n$ 分成 $n/B\times n/B$ 个 $B\times B$ 的块。这样每一条线会经过 $O(n/B)$ 个整块和 $O(B)$ 个散点。整块同样 FFT。散点暴力加入。复杂度 $O(n\sqrt{n\log n})$。

不想要这个 $\log n$ 因子。可以发现行的多项式的点值可以在横着扫时保留。每次更新一个单点系数可以 $O(B)$ 改完点值。对列和斜同理。这样 $\log n$ 就没了。复杂度 $O(n\sqrt n)$。

C. 货币

相当于对每个 $i$，我们需要在 $(1,i)$ 到 $(1,i+1)$ 与 $(2,i)$ 到 $(2,i+1)$ 之间选择一个走。选每一种需要一个代价，如果 $i$ 和 $i+1$ 选择了不同的行，那么就需要额外付出 $(1,i+1)$ 到 $(2,i+1)$ 之间边的代价。再加上 $m$ 条限制，是一个小型的切糕模型，直接建图跑网络流即可。

D. 广为人知题 2

本题为 IDM Problem 的 CountDistinct 查询。详细做法见 Nearly Optimal Internal Dictionary Matching。

给所有串赋一个权值 $v_t$，其中 $t$ 为一个 $s$ 的子串，初始均为 $0$。我们直接将所有模式串对应的 $v_t$ 加 $1$，查询的答案即为查询串 $s[l,r]$ 所有本质不同子串中 $v$ 的和。

考虑所有串形成的 trie（这里 trie 字符着加，为了匹配正串 SAM）。记 $f_u$ 为 $u$ 到根的所有串的 $v$ 之和。答案为 trie 上所有是 $s[l,r]$ 子串的点的 $v$ 之和。显然构成一个 trie 上包含根的连通块，答案即为：

$$\sum\limits_{u是叶子}f_u-\sum\limits_u (u儿子个数-1)f_u$$

首先考虑后者。按 $r$ 扫描线，考虑 LCT，维护 SAM 上连续上一次出现位置相同的节点。每次 access 时遇到一个连续段时，考虑段尾的点何时儿子个数 +1，应为 $l\leq \mathrm{last}-\mathrm{len}$ 且 $s[1,r]$ 所在子树第一次出现节点（即上一个连续段中的 $\mathrm{last}$ 不会在这里贡献）。所以对 $l$ 是一个区间加。查询即为单点查询。该部分时间复杂度 $O(n\log^2n+q\log n)$。

再考虑前者。首先叶子一定左端点为 $l$。其次若 $s[l,t]$ 非叶子，说明存在 $s[l',r']=s[l,t]$ 且 $t

最后考虑如何求出 $\sum\limits_{i=x}^r f_{s[l,i]}$。差分后变为若干个 $\sum\limits_{i=l}^r f_{s[l,i]}$。而这等价于广为人知题查询（IDM Problem 的 Count 查询），可以用基本子串结构（见 Nearly Optimal Internal Dictionary Matching）在 $O((n+q)\log n)$ 内解决。

总时间复杂度为 $O(n\log^2 n+q\log n)$。若 $n,q$ 同阶，可优化至 $O\left(\frac{n\log^2n}{\log\log n}\right)$。

E. 浅斟低唱

考虑维护长度 $\geq 2$ 的所有 0 的连续段和 1 的连续段，每次 1 操作是让所有 0 连续段左移一位，所有 1 连续段右移一位，2 操作同理。

例子：经过 1 操作后，

01010000111101010001110111100010101 变成

10100001011110100010111011100101010

唯一出现问题的可能即为存在一个 0 连续段与一个 1 连续段撞上了。此时可以暴力修改，由于所有连续段长度总和这时会减 2，且长度总和初始最多为 $n$，修改最多增加在每次操作的边界 ，所以总暴力修改次数为线性。

总时间复杂度为 $O((n+q)\log n)$。

F. Trash Problem

枚举左边界。此时从左往右扫，记录每个格子当前是一个 $2\times 2$ 的一半还是已经完成。每次扫的时候如果当前是一半但是下一个是黑格，那么包含这一行的就全不合法。否则如果当前是白格，就将这个状态异或 $1$。扫到某个时刻，一个区间合法当且仅当当前这些状态都是已完成，且这个区间不包含前面所说的那些行，且与所有出现过的连续状态 $1$ 的区间交的长度为偶数。前两个条件容易满足，重点在于第三个条件。

可以发现，$[l,r]$ 与所有连续状态 $1$ 的区间交的长度为偶数等价于 $[1,r]$ 与所有连续状态 $1$ 的区间交的长度为奇数的区间左端点集合等于 $[1,l-1]$ 与所有连续状态为 $1$ 的区间交的长度为奇数的区间左端点集合相同。直接扫描线扫 $r$，哈希一下，如果哈希表 $O(1)$ 复杂度即为 $O(n^3)$。

G. 分析

注意到代价为 $A$ 的操作可以直接视为加了一条重边，所以我们可以先执行所有代价为 $A$ 的操作，在考虑怎么走。可以发现加完边之后需要执行的 $B$ 操作次数即为度数为奇数的点数除以 $2$ 再 $-1$（如果没有度数为奇数的点即为 $0$）。

树形 dp，过程中考虑是否加重边，状态内记子树根的度数奇偶性和是否有度数为奇数的点即可。

时间复杂度 $O(n)$。

H. 代数

题解

首先把子树大小的 $k$ 次方改为选 $k$ 个点都在子树内的方案数。进一步，可以看作有 $n+1,n+2,\dots,n+k$ 这 $k$ 个点，每个点随机选择 $1,2,\dots,n$ 中的一个点作为父亲，问有多少种方案使得它们都在 $u$ 子树内。

考虑从前往后 dp，设 $d[i][j]$ 表示前面 $i$ 个点考虑完，有 $j$ 个点还存在没出现的儿子的子树里有 $n+1,\dots,n+k$ 这 $k$ 个点之一。那么转移即为：

1. 新出现的点子树里没有 $n+1,\dots,n+k$ 这 $k$ 个点之一。那么随便接到任意一个点上即可。
2. 新出现的点子树里有这 $k$ 个点之一，假设接到了点 $u$ 下面，此时 $u$ 还有别的没出现的儿子的子树里有这 $k$ 个点之一。
3. 新出现的点子树里有这 $k$ 个点之一，假设接到了点 $u$ 下面，使得 $u$ 没有没出现的儿子的子树里有这 $k$ 个点之一。

要计算每个点的答案，需要从前往后做一遍，转置之后从后往前再做一遍，最后在中间统计答案即可。

时间复杂度 $O(nk)$。

I. 二十二

首先忽略所有没有用的操作。其次，全局取 min 操作一定是从小到大操作的，因为如果有两个前面大右边小，前面的一定没用，可以把它放到紧挨着小的的右边，也没用。这样每一个 max 操作就可以放在任何一个 min 操作前面，可以看作对（这个 min 对应的 $c$ 或者原本的 $c$）取 max。

所以结论即为把所有区间 max 操作的 $c$ 变为所有比 $c$ 小的 min 操作的值之一或者不变后，先操作最小的全局 min，后操作所有 max 操作，有多少种最终序列。可以区间 dp，dp 数组类似 $dp(l,r,x)$，表示区间 $[l,r]$ 内最终序列的所有数均 $\geq x$ 且 $l-1,r+1$ 两个位置 $< x$ 的方案数。因为这样只需考虑被 $[l,r]$ 包含的 max 操作。每次枚举区间最小值转移即可，会有亿点细节。

在 $n,m,k$ 同阶时，时间复杂度为 $O(n^4)$。

J. 我以渺小爱你

条件等价于把每条 hyperedge $(x,y,z)$ 拆成三条边 $(x,y),(y,z),(z,x)$ 后建成的无向图中不包含四元环。

首先构造图 $\mathrm{ER}_q$：

点：$\bmod q$ 意义下三维空间的所有不同直线。

边：两条直线垂直。

容易证明 $\mathrm{ER}_q$ 有点数 $q^2+q+1$，边数 $\frac 12 q(q+1)^2$，且图中不存在四元环。

构造答案：hyperedge 为 $\mathrm{ER}_q$ 中所有的三角形。容易验证满足边数条件。

K. 应氏杯

在钦定一个点是极小值之后，它和周围点之间的大小关系就确定了。

一个经典结论：对于一个森林，如果所有父亲小于儿子，那么赋一个排列的方案数为 $n! \prod_u \frac 1{siz_u}$。

考虑树形 dp，记 $d[u][i][j]$ 为 $u$ 子树内，钦定了 $i$ 个点为极小值，当前小于关系构成的子树大小为 $j$ 的方案数。每次钦定一个点为极小值时，它小于所有儿子，且小于它的父亲。小于它的父亲可以通过容斥变为无限制减去父亲小于它。

是一个二维背包。把一维改成维护点值+插值之后，可以做到 $O(n^3)$。