This is the draft of the problems of the 3rd 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 358 problem submissions from 164 different authors all over the world. We shortlisted 20 problems to our pool, and used 13 of them in the end. The task authors are: Xutong Ding, Zhiyuan Ge, Yuchong Guo, Siyuan Huang, Vsevolod Lepeshov, Xinlong Li, Jiahe Liu, Qingyu Shi, Yaohui Zeng.

The problemsetting for the Universal Cup Finals is always challenging. With the world’s strongest teams gathered in Shanghai, the judge team put tremendous effort into optimizing the final problem set. In the later stages of the problemsetting process, we found that several problems, such as J, L, and another unused task, were much harder than we had expected. We replaced one problem in the harder range with Problem I, but even with the help of multiple judges and testers, we still underestimated the difficulty of many tasks in the set — especially Problem D.

Congratulations to USA1 for defending their champion title of the Universal Cup!

Expected Difficulties from SC Chair (Easy to Hard)

Expected Medals Cut-off

Judges

• Chair, Executive Director: Qingyu Shi
• Deputy Chair: Lingyu Jiang
• Chief Judge: Yaohui Zeng
• Judge: Xutong Ding, Yuhao Du, Zhiyuan Ge, Yuchong Guo, Siyuan Huang, Vsevolod Lepeshov, Bingpei Li, Xinlong Li, Yichen Li, Jiahe Liu, Yaowei Lyu, Jiachen Tang, Zonghan Yang, Junlin Ye

Problem Selection Committee

• Chair: Qingyu Shi
• Deputy Chair: Yuhao Du, Lingyu Jiang, Yaohui Zeng
• Members: Peijian Du, Yixong Gao, Zhiyuan Ge, Yanru Guan, Cheng Jiang, Siyuan Jiao, Bingpei Li, Zhuocheng Lin, Jiahe Liu, Jiameng Liu, Yaowei Lyu, Zixuan Qiu, Zexu Shi, Hengzhe Sun, Jiachen Tang, Chunyang Wang, Zhaoyuan Wang, Zhenyu Wang, Junlin Ye, Penghao Zhai, Hengyi Zhang

Technical and Sys-Op Team

• Members: Shengliang Cai, Haojun Pan, Lyuzhi Pan, Liangzheng Yang

Testers

• Testers: Kai'an Chen, Ruicheng Cai, Yifan Chen, Zhezhang Chen, Jiangqi Dai, Qiyu Feng, Cheng Jiang, Jianing Liu, Weikun Pu, Peixuan Sun, Jun Tao, Chuxi Yi, Zhihang Yu, Mixuan Zhang, Xuxiang Zheng, Kangyang Zhou, Zemu Zhu

Prepared by Qingyu and GeZhiyuan.

Analysis will be added a bit later.

Prepared by Kubic and Qingyu. Alternative Solution by Diaosi

Analysis will be added a bit later.

Prepared by Dinshey.

Analysis will be added a bit later.

Prepared by Qingyu.

Analysis will be added a bit later.

Prepared by Kubic.

Analysis will be added a bit later.

Prepared by jiangly, Kubic, and Qingyu. Alternative Solution by zhoukangyang

Analysis will be added a bit later.

Prepared by ccz181078 and nzhtl1477

Analysis will be added a bit later.

Prepared by Coffee_zzz and Qingyu

First consider how to proceed when the position of $1$ is known.

Suppose $p_x = 1$. Then we can arbitrarily choose a number $y$ and query $(x, y)$, then recursively query the returned number until we encounter a number that has already been queried. In this way, the values of these numbers can all be determined. Repeat selecting $y$ until all numbers' values are determined.

Next consider how to proceed when the position of $1$ is unknown.

Consider pretending that some number is $1$ and then performing the above procedure. If during the process we find a number smaller than it, that indicates it is not $1$; at that point, we pretend that this smaller number is $1$ instead. This process is akin to Euclidean subtraction: every two additional operations can at least halve the true value of the number being treated as $1$. Therefore, the number of additional operations is $2 \log n$, and the total number of operations is $n + 2\log n$.

Finally, run an algorithm similar to topological sorting to compute the values of all numbers.

Prepared by Kubic

Analysis will be added a bit later.

Prepared by fstqwq, Gromah, and quailty

The problem asks for the shortest line segment that intersects a given set of $n$ lines in the 2D plane. This is known as the “Shortest Transversals of Lines”.

If we fix the angle of the segment (assuming it is not parallel to any input line) and rotate the plane such that the segment becomes vertical, the problem reduces to finding the shortest vertical segment intersecting all lines. This is equivalent to finding the minimum vertical distance between the upper and lower envelopes of the rotated lines.

We can relax the constraint on the angle. Instead of strictly looking for the minimum vertical distance in the rotated frame, we seek the shortest segment connecting a point on the upper envelope to a point on the lower envelope. Since both envelopes are convex, this minimum distance can be efficiently computed using a two-pointer technique.

The angles of the input lines split the range of possible orientations into $O(n)$ intervals. Each interval corresponds to a specific combinatorial structure of the upper and lower envelopes. These envelopes correspond to the boundaries of different unbounded cells in the arrangement of the input lines. By the zone theorem, the total size of these unbounded cells is $O(n)$, and thus the total size of the envelopes is $O(n)$.

To construct the envelopes efficiently, we first consider the unbounded cells intersected by the line $y = -\infty$. Excluding horizontal lines, each non-horizontal line intersects $y = -\infty$ at a unique point. The angles of the lines corresponding to these intersection points are monotonic from left to right. These points split $y = -\infty$ into several ranges, each belonging to a specific unbounded cell.

Each such cell is defined by the intersection of two sets of half-planes: those forming the left boundary and those forming the right boundary. As we sweep from left to right along $y = -\infty$, the left boundary evolves by adding half-planes with monotonic angles. This monotonic property allows us to maintain the left envelope using a stack-based Half-Plane Intersection (HPI) algorithm. The right boundary is symmetric; it can be maintained by scanning from right to left, and then effectively restored by rolling back the HPI structure during the left-to-right sweep.

Note that each unbounded cell has exactly two ray boundaries. The rays forming the desired envelope must have distinct angles. Therefore, we can ignore unbounded cells where the two bounding rays have the same angle (which typically arises from parallel lines). To handle this, we add lines with identical angles simultaneously to the HPI structure.

To efficiently extract the envelope for each interval, we sweep upwards from $y = -\infty$ along the left and right boundaries simultaneously, until the boundaries intersect (closing the cell) or are truncated by the lowest horizontal line. This process precisely extracts the boundary of the corresponding unbounded cell.

The case for $y = +\infty$ is symmetric. We can process the upper envelopes similarly by reversing the orientation, allowing us to compute both the upper and lower envelopes for all intervals.

The overall time complexity is $O(n \log n)$, dominated by the initial sorting step.

Prepared by unputdownable

Analysis will be added a bit later.

Prepared by Dinshey

Analysis will be added a bit later.

Prepared by Qingyu and sevlll

So for planar graph we can direct edges in a way that all indegrees are at most $5$ (just choose lowest degree vertice repeteadly). Lets direct edges this way, similarly for both runs.

Then consider a restoring algorithm for the second run: lets iterate through vertices in topological sorting order. The goal is to determine whether vertice has a bomb uniquely. For all neighbours, except $5$, we already know whether they have a bomb or no. So, if this vertice happens to be without bomb, there are only 6 options of what $a_v$ can be equal to. So if $a_v$ is neither of those 6 options, we can safely conclude that this vertice has a bomb.

So, if we manage to assign numbers in first run, in such a way, that for every vertice with a bomb, $a_v$ is always neither of those 6 options, in second run we can use this restoring algorithm, and say that vertice doesnt have a bomb if $a_v$ is one of the 6 options.

So, we can find this assignment on first run, that works for almost all vertices except like 5 of them (with some kind of greedy + pigeonhoole principle), and we can store information about those 5 special vertices in a binary string $s$, to solve the problem.