The 2nd Universal Cup Finals: Analysis Report
Qingyu Shi
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.
Summary
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)
| Problem |
I |
C |
J |
L |
D |
F |
K |
M |
G |
B |
E |
H |
A |
| Expected Solves |
20 |
20 |
20 |
15 |
10 |
10 |
8 |
5 |
3 |
2 |
2 |
2 |
0 |
| Actual Solves |
20 |
18 |
20 |
20 |
4 |
17 |
5 |
4 |
0 |
1 |
1 |
3 |
0 |
Expected Medals Cut-off
| Awards |
Champion |
Gold Medal |
Silver Medal |
Bronze Medal |
| Expected Solves |
10 ~ 12 |
8~9 |
6~7 |
5~6 |
| Actual Solves |
10 |
8 |
6 |
5 |
Judges
Qingyu
Chair of the Scientific Committee & Technical Committee
Executive Director of Contest
|
jiangly
Deputy Chair of the Scientific Committee
Subdirector of Contest
|
Lynkcat
Chief Judge
Subdirector of Contest
|
Tech, System Supports, and Live Streamers
cubercsl
Deputy Chair of the Technical Committee
Executive Director of Tech & System
|
Dup4
Director of Judging
|
twingy
Director of Challenge Affairs
|
Liangzheng Yang
Subdirector of Judging
|
dailongao
Director of Live Stream Affairs
|
Lidia Perovskaya
Member of Live Stream Affairs
|
xiaowuc1
Member of Live Stream Affairs
|
kostka
Member of Live Stream Affairs
|
Wenhan Huang
Member of Live Stream Affairs
|
Tangent
Director of Organizing
Member of Live Stream Affairs
|
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 图的顶点是可能的候选圆心，取出这些候选圆心可以得到对应的候选圆。要判断一个候选圆是否合法，只需要判断圆心是否在圆并的圆弧拉直后的区域里，必要性是显然的，充分性可以通过分析不可能出现误判合法的情况进行证明，此处略去细节。
综上所述，具体算法流程如下：
- 使用极角排序+扫描线求出圆并，这部分复杂度是 $O(n^2\log{n})$，理论上可以通过求解 Power Diagram 做到 $O(n\log{n})$。
- 使用半平面交算法求出圆并顶点的 V 图的顶点，可以通过 Power Diagram 的性质证明圆并顶点最多有 $6n$ 个，这部分复杂度也是 $O(n^2\log{n})$，或者随机打乱半平面之后逐次切割凸多边形做到期望 $O(n^2)$，理论上也可以做到 $O(n\log{n})$。
- 判断每个候选点是否在圆并的圆弧拉直后的区域里，使用经典的回转数算法可以做到单次 $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.
我们首先先做两个转化：
- 把$0$变成$-1$然后求前缀和，这样一来，区间[l, r]的绝对众数是 $1$ 等价于 $s_r-s_{l-1} \geq 1$ ($0$是对称的)
- 把相同的相邻 $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)$。
