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.

Part I. How to Solve $k=1$

Consider a subproblem: suppose we guarantee that the $1$s are mutually non-adjacent, and we only need to decide whether the sequence can be fully deleted.

Observe that if the start/end of the sequence is a $1$, we can pad a $0$ at the start/end, and the answer remains unchanged.

Now split the sequence by the $1$s into several contiguous segments of $0$s. Let the sequence of these segment lengths (gaps) be called $l$.

Observe that if $l$ is all $1$s, then it can definitely be fully deleted. And if not all $1$s, then $l$ must contain two adjacent numbers whose sum is greater than $2$.

Therefore, before reaching the state where $l$ is all $1$s, we can always guarantee that each $1$ deletes two $0$s, which is clearly optimal.

In summary, the subproblem guaranteeing non-adjacent $1$s is equivalent to: each $1$ at the boundary contributes $+2$, and each non-boundary $1$ contributes $+3$. If the total can reach $n$, it can be fully deleted; if it cannot reach $n$, it cannot.

Now consider the original problem. Observe that the chosen $1$s must be mutually non-adjacent, and we apply the decision method of the non-adjacent-$1$s subproblem to the chosen positions. This amounts to selecting some non-adjacent $1$s, where boundary ones contribute $+2$ and middle ones contribute $+3$, minimizing the number of selected $1$s under the premise that the sum reaches $n$. Simple greedy/dynamic programming can easily solve it.

Part II. How to Achieve $O(n^2)$ on the Original Problem

Directly applying $k=1$ to $k>1$ seems to give the following:

• Select several $1$s from the sequence with mutual distance at least $k$, then for a selected $1$ at position $i$ provide a contribution of $\min(i-1, k) + \min(n-i, k) + 1$. The total contribution must be $\geq n$, minimizing the number of selected positions.

But this is false. Consider $k=2$: you'll find $0001001000$ cannot be fully deleted.

Intuitively, the problem occurs at the last deletion. Let's patch it:

• Enumerate the last $1$ to be deleted. The problem is then divided into left and right subproblems.
• The two subproblems are symmetric, similar to the original problem but slightly different:
  • Given a binary string $s$ of length $m$. You can perform several deletion operations; each time you select a $1$ and delete it along with the characters within distance $k$ (after deletion, the two sides are joined together).
  • But you cannot select a $1$ in the first $k$ positions. However, you don't need to fully delete the string—you only need to reduce the string length to $\leq k$.

Remarkably, this subproblem has a nice approach:

• First turn the $1$s in the first $k$ positions into $0$s. Then select several $1$s from the sequence with mutual distance at least $k$, where a selected $1$ at position $i$ provides a contribution of $k + \min(m-i, k) + 1$. The total contribution must be $\geq m-k$, minimizing the number of selected positions.

Why is this correct on the subproblem? And why is this conclusion true for the original problem when $k=1$?

• We find that the essence of deletion is:
  1. Step One: If the gap sequence contains two adjacent $l$s whose sum is $\geq 3k$, delete the $1$ sandwiched between these two $l$s.
  2. Step Two: When no such adjacent $l$ exists, delete all $1$s from right to left.
• Mapped to the original problem: at the end of Step Two, the remaining string length is $< k$. In the original case $k=1$, so this is of course correct!
• And in the new problem, Step One causes no waste, and the final string length is necessarily $\leq k$. Once Step Two is entered, the remaining string length after deletion is $< k$, so all requirements are satisfied!

Thus we have solved the original problem in $O(n^2)$.

Part III. How to Achieve $O(n)$ on the Original Problem

Directly split into two cases:

1. Case One: If we select a $1$ from the first $k$ positions of the start or the last $k$ positions of the end, the following decision method becomes true:
   • Select several $1$s from the sequence with mutual distance at least $k$, then for a selected $1$ at position $i$ provide a contribution of $\min(i-1, k) + \min(n-i, k) + 1$. The total contribution must be $\geq n$, minimizing the number of selected positions.
2. Case Two: If not selected, then every $1$'s contribution is $2k+1$, depending only on the number selected.

For Case One, assume WLOG that a $1$ is selected in the first $k$ positions (the other side is symmetric). In this case:

• Enumerate the first selected $1$, then greedily select going forward.
• The first selected $1$ has $k$ possibilities, and at most $\lceil \frac{n}{2k+1}\rceil+1$ positions are selected. Time complexity $k \times O(\frac{n}{k}) = O(n)$.

After checking all of Case One, erase all $1$s in the first $k$ positions of the start and last $k$ positions of the end (i.e., turn them into $0$s), then check Case Two:

• First check whether we can select $\lceil \frac{n}{2k+1}\rceil+1$ mutually-distance-$\geq k$ $1$s. If so, it is definitely a valid solution, which can be greedily obtained.
• Otherwise, we find that $\lceil \frac{n}{2k+1}\rceil$ is already a lower bound on the answer, so we only need to check whether there is a solution with answer $\lceil \frac{n}{2k+1}\rceil$:
  • Since the total number of selected $1$s is now fixed, for a given $1$, checking whether it can serve as "the $r$-th of all selected $1$s, and be deleted last" is an easy matter, and this $r$ corresponds to an interval. For all $1$s, this interval can be found with a two-pointer in $O(n)$.
  • Let $f_{i, 0/1}$ denote: under the condition "$i$ $1$s are selected, and there is/is not one among them that can serve as the last-deleted $1$," the minimum possible position of the $i$-th $1$ across all selection schemes is at least $f_{i, 0/1}$. The transition is not hard—just combine with the intervals found earlier by the two-pointer, then use a sweep line and an auxiliary array to compute it in $O(n)$.

Thus we have solved the original problem in $O(n)$. The two-pointer and dynamic programming details used to solve Case Two may be somewhat involved, but if you don't want to deal with them, you can directly write $O(n \log n)$, which requires no case analysis and is much simpler.

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

If the original string is not a Lyndon string, then simply not partitioning works.

Otherwise, the first letter of the original string must be the smallest character; assume it is $a$.

Now discuss the distribution of $a$ in the original string: all $a$s form several contiguous segments, and the segment lengths must have the leading one be the longest. If the original string is not a single $a$, it must contain a character that is not $a$.

If all $a$s are distributed contiguously (all at the start), there is definitely no solution.

If the positions of $a$ split into at least two contiguous segments and the total count is $3$ or more, then the leading segment has length at least $2$, and we can partition the leading segment of $a$s from the following string.

If $a$ appears only $2$ times, these two $a$s must both be in the first string. In this case the form of the first string is basically determined; the only thing that can vary is the length of the suffix that follows.

The following suffix first has a length restriction (imposed by the requirement that the first string must be a Lyndon string). Under this restriction, taking an increasing prefix minus one position to maximize the first character of the remaining string is definitely optimal, and the rest is solved recursively.

Let the character set size be $m$. Since the recursion can proceed at most $m$ times, a poor implementation may degrade to $O(nm)$. But when deciding whether to recurse, we only need the count and positions of the smallest character that follows, and the recursion process only needs to traverse the part assigned to the first string, so the complexity can be made $O(n)$.

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.