CEOI 2025 discussion

#	User	Rating
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3447
6	Um_nik	3387
7	heuristica	3322
8	turmax	3317
9	tourist	3307
10	jiangbowen	3291

#	User	Contrib.
1	Qingyu	156
2	nik_exists	150
2	maspy	150
4	Um_nik	143
5	Errichto	139
6	adamant	137
7	AmShZ	135
8	maroonrk	133
9	BledDest	132
10	qwexd	129

Since CEOI 2025 is over and the tasks and test data have been published, can we discuss the solutions here?

Here are the tasks.

Upd: you can find the tasks here (for now)

Upd: https://github.com/asociatia-sepi/archive/tree/main/CEOI-2025

Upd: I was upsolving this CEOI now for practice and I decided to write some solutions because I couldn't find them.

Boardgames

Solution 1

This is the approach from the official editorial. The core idea relies on a divide and conquer strategy:

Initially, we invoke the function $$$f(1, n)$$$.
Find the position $$$i$$$ closest to the border such that $$$i$$$ and $$$i+1$$$ are not in the same connected component.
If the subgraph from $$$L$$$ to $$$R$$$ is connected, we can just return $$$1$$$.
Otherwise, we split the problem and return $$$f(L, i) + f(i+1, R)$$$.

The main implementation challenge here is to efficiently maintain graph connectivity while supporting fast addition and removal of elements from both the front and the back.

To do that, check this. :P

$$$O(n \log^2 n)$$$

Solution 2

Let $$$dp_i$$$ be the answer for the first $$$i$$$ elements. We want to optimize the transition $$$j \to i$$$ to run quickly.

Let's first simplify the problem by assuming the graph is a forest. Notice that for a subgraph spanning from $$$j$$$ to $$$i$$$ to be connected, the following property must hold exactly:

$$$i - j - \text{count(edges inside } [j, i]\text{)} = 1$$$

Since it always holds that this expression is $$$\ge 1$$$, it naturally inspires us to use a segment tree. We can maintain this minimum value for each $$$j$$$. Among all indices $$$j$$$ that achieve this minimum, we simply pick the one that minimizes $$$dp_j$$$.

For the full solution, we must eliminate extra edges that form cycles. To do this, we avoid adding edges with a minimum value $$$\min(u, v)$$$ that would complete a cycle. This requires maintaining an online Minimum Spanning Tree (MST), which can be accomplished via:

Divide and conquer in $$$O(n \log^2 n)$$$
Link-Cut Tree or this in $$$O(n \log n)$$$

Highest

This problem can be elegantly modeled using binary lifting. The primary obstacle is that after executing a jump, we are allowed to move backward. Let us define the DP state:

$$$dp[x][k][o]$$$: The rightmost position reachable starting from $$$x$$$, given that we have utilized $$$2^k - o$$$ coins ($$$0 \le o \le 1)$$$.

We can compute this entirely in $$$O(n \log^2 n)$$$ time by rebuilding a Range Minimum Query (RMQ) structure for each power $$$k$$$.

To optimize the complexity down to $$$O(n \log n)$$$, notice that if we have already covered the interval $$$[L, R]$$$, it is always optimal to jump from the position that yields the rightmost 1-cost jump and 2-cost jump within $$$[L, R]$$$.

Lawnmower

First, design a naive $$$O(N^2)$$$ dynamic programming approach. To optimize it, we can analyze the cost structure of the transitions. The cost of transitioning from $$$j \to i$$$ is expressed as:

$$$\text{cost}(j \to i) = b \cdot \left\lceil \frac{\sum V(j+1 \dots i)}{c} \right\rceil + \sum_{k=j+1}^i \left( \left\lceil \frac{v[k]}{c} \right\rceil + S \right) \cdot a[k]$$$

where $$$S$$$ represents an error offset term that is strictly either $$$0$$$ or $$$1$$$.

If we let $$$\text{pref}[i] = \sum V(0 \dots i-1) \pmod c$$$, then $$$S = 1$$$ for some $$$k$$$ and a chosen $$$j \le k$$$ if and only if $$$\text{pref}[j]$$$ falls within the cyclic interval:

$$$(\text{pref}[k], \text{pref}[k] + (v[k] \bmod c))$$$

evaluated modulo $$$c$$$. This can now be solved with segment tree supporting range addition and range minimum query. On each position $$$x$$$ we maintain minimum $$$\text{dp}[j]$$$ such that $$$\text{pref}[j] = x$$$.

Equalmex

First, we need to determine the $$$\text{mex}$$$ for each query. This can be achieved using a segment tree that maintains the last occurrence time for each value $$$X$$$. By performing a binary search over the segment tree, we can easily locate the lowest $$$X$$$ whose last occurrence lies outside the query interval.

We can solve the queries using a divide and conquer strategy:

Divide the array by its midpoint and inspect all queries intersecting the middle.
Focus exclusively on the right side (the left side is completely symmetric). Let $$$f_x$$$ be the $$$\text{mex}$$$ value from the middle to position $$$x$$$.
We need to compute how many jumps ($$$j \leftarrow i$$$, where $$$f_i = \text{mex}$$$) can be performed starting from $$$x$$$, and determine our final landing position.

A naive segment tree implementation yields a total complexity of $$$O(n \log^2 n)$$$. However, we can optimize this to $$$O(n \log n)$$$ by restricting our attention only to jumps ($$$j \leftarrow i$$$) where $$$f_i = f_j = \text{mex}$$$, allowing us to utilize a clean two-pointers approach.

When we moved the left and right endpoints of the query there can still be more available jumps to do. But there is at most $$$3$$$ of them so we can do them manually giving us total time complexity $$$O((q+n) \log n)$$$.

Split

Suppose you have a fixed prefix. If it is not a prefix of any given permutation, we can uniquely determine its split point. This gives rise to a set of conditions $$$(x, y)$$$, meaning element $$$x$$$ must appear before element $$$y$$$.

Focusing on the first permutation, we can run an $$$O(n^2)$$$ DP:

$$$dp[x][y]$$$: The number of valid permutations if we have placed $$$x$$$ elements before the split point and $$$y$$$ elements after the split point.

Evaluating this independently for each of the $$$O(n^2m)$$$ prefixes is way too slow. Instead, we can precompute the states:

$$$dp[s][x][y]$$$: Where $$$s$$$ is the split point, having already determined the last $$$x$$$ elements before the split and the last $$$y$$$ elements after the split.

By implementing this carefully, the precomputation complexity is bounded by $$$O(n^2(n+m))$$$. Carefully brute-forcing all valid prefixes that could potentially form a split can similarly be optimized to $$$O(n^2(n+m))$$$.

Theseus

https://codeforces.me/blog/entry/144670?#comment-1293957

TL;DR

Suppose all edges are initially oriented from the smaller vertex value to the larger vertex value. Assigning a value of $$$1$$$ to an edge reverses its directed orientation.

Sort all edges $$$(x, y)$$$ where $$$x \lt y$$$ lexicographically (by the first element, then by the second). This defines their priority. Theseus's strategy is always to traverse the first available outgoing edge based on this priority.
We need to construct a directed graph that structurally forms a directed tree. Run a BFS starting from the target node $$$t$$$ and group all nodes with the same distance layer together.
Iterate layer by layer from the largest distance down to the smallest distance. Assign each node a potential $$$P$$$, which is initially set to $$$0$$$ for all nodes.
Iterate through the edges in order of their sorted priority:
- If at least one node of an edge has already been assigned an outgoing edge, skip it.
- If we encounter an edge going from the current layer (node $$$x$$$) to the next layer (node $$$y$$$), add it to the graph and assign $$$P(y) = P(x)$$$.
- If we encounter an intra-layer edge between $$$(x, y)$$$, we direct the edge from the smaller potential to the larger potential. If their potentials are equal, we orient it as $$$y \to x$$$ and increment the potential: $$$P(x) := P(x) + 1$$$.

That's all folks! :)

Comments (23)

Write comment?

Sul_A.

14 months ago, hide # |

+12

Where are the statements?

→ Reply

dinohaur

14 months ago, hide # ^ |

Wait what?

I thought they would give problems along with the data.

For some reason they only added the test data

I've deduced the statement of equalmex:

You are given an array

Unable to parse markup [type=CF_MATHJAX]

of length

. You are also given

queries of the following form: "You must split the array

into the maximum number number of segments such that each element is in exactly one segment, and the MEX of each segment is equal."

Example:

Input:


10 2
1 1 2 2 3 3 1 2 3 4
1 6
1 9

Output:

1
2

Explanation:

1 1 2 2 3 3 => 1 1 2 2 3 3

1 1 2 2 3 3 1 2 3 => 1 1 2 2 3 3|1 2 3

Constraints:

Unable to parse markup [type=CF_MATHJAX]
Unable to parse markup [type=CF_MATHJAX]

Subtasks:

Unable to parse markup [type=CF_MATHJAX]
Unable to parse markup [type=CF_MATHJAX]
Unable to parse markup [type=CF_MATHJAX]
Unable to parse markup [type=CF_MATHJAX]
Unable to parse markup [type=CF_MATHJAX]
No additional constraints

Pie_TealCompressorDragon

← Rev. 2 →

Score distribution should be (based on participants scoring): 1. 4 points 2. 6 points 3. 17 points 4. 10 points 5. 30 points 6. 33 points

libobil

Absurdly similar to IZHO 2024 P5

cadmiumky

← Rev. 4 →

+42

Following is my solution for problem Theseus (Day 2 P3). Many thanks to all the contestants with whom I talked that helped me realise some flaws I had in my proof and discussing them with me, and AlexLuchianov for the great task.

First, an important step is characterizing better what the strategy could ever look like for Theseus given whatever input he is given. We conclude that given that we are given labels of all current and incident nodes that we can communicate some intended edge orientation. Furthermore, to make our lives easier (and because ideally random never works much better, and as it will turn out, this will play a very important role in the correctness of the solution), we will consider that we will always proceed to the minimum labeled node we have an edge towards.

Another thing that is clearly needed in this problem is the BFS tree of the graph (rooted in $$$t$$$). Then these definitions naturally follow:

Layer/level: the induced graph on the nodes from an equal distance from t.
Parent edge: the edge for any one node connecting it to one node on a layer above it. We can consider such an edge is unique because we will always orient trans-layer edges in increasing order, and as such whenever we have to distinguish between such edges, given the already mentioned strategy, only one would ever be a candidate for any path.
Tempo move: a forced move by the (final) structure of the graph that happens from one node of any layer to another within the same layer.

We will now strive to create a system that well reflects the necessities of the problem. We will try to label nodes with some priorities as to reflect the amount of tempo moves we can still do. We then need this system to abide to the following rules:

All tempo moves are effectuated from one node of some priority to one of a strictly lesser priority.
Parents of any nodes accurately** reflect the worst count of tempo moves any valid path in the graph could lead to them.
The count of distinct priorities is 14 (logarithmic).

Consider the bottommost layer of the graph. We will try to find some "funnel" nodes we can send most of the nodes into as to "thin out" the graph (similar to what the strategy for ladders looks like). We will select these nodes to form an iset (independent set, I abuse this notation and will use iset as an independent set that is also a node cover) and we will direct all cross edges towards isets. We note that this step does not only occur for the bottommost layer, and will prove to appear at every level in some capacity.

Of course, the first rule might still fail given that isets are usually sparse, the many edges that are between non-iset nodes do not admit any immediately obvious solution. We employ the following fail-safes for them:

1) We construct the iset(s) by greedily adding nodes to them ulteriour to sorting the candidate nodes (we will discuss this later) in increasing order.

To better help visualise this, consider two nodes that do not belong to the iset. However, one of the nodes is incident to the minimum-labeled node of the layer. Then of course, the edge between these two nodes is sort of redundant from the perspective of the first node, and the aformentioned cis-edge can be oriented from the first node to the second (as the first would never want to go to a greater node as per the strategy).

To formalize this, we will call "spheres of influence" of any node inserted in the iset the set of nodes that are newly marked for iset conflict upon inserting some node X into the iset (ulteriour to getting to it and finding that it does not have an incident edge to any node already inside the iset).

Formality

This condition (sorting nodes prior to iset construction) then mostly solved the issue of internal edges withing non-iset nodes of any sphere of influence. To solve cross edges between non-iset nodes of any sphere of influence we employ the following criterion:

2) Cross edges are oriented from lesser labeled spheres of influence towards those that are greater labeled.

This basically means that for two nodes X and Y that belong to the sphere of influence of 1 and 17 respectively, it is safer to orient the edge from X to Y as X will already most certainly go to 1 (whereas Y might go to X if X is less than 17, breaking the intended notion that you go to the closest iset node possible in the final strategy).

We will generalize all of this to work not only for the bottom layer, but for all of them, in the following final algorithm outline:

We iterate layers from the bottom to the top.
We initially label every node with the minimum priority 0.
For each layer, in increasing order of priority, we construct the isets of the induced graph of the nodes on that layer and of that priority according to the aforementioned rules. We also orient all edges having one non-iset endpoint by the rules already established.
We look for each iset node whether any non-iset node would want to point to it (as per the strategy and that the parent has a lesser value than the incident iset node, rendering it useless).
If this is the case for any iset node, we increase their priority.
We batch the newly increased priority nodes to form further isets with the other nodes on the same layer of the new higher priority, repeating this process until no further priority increases are done.
For every node that we determined that their next move is not a tempo move, we force-set their parents' priority to their own priority.

This last part ties into the second rule, that stated that every node correctly represents the count of tempo moves any actual path could lead into them. More importantly, every node that does employ a tempo move does not imply on its own any restriction on the parent (this can be done by some sibling and is ignored).

We will now prove that the complexity of this is logarithmic. We will note with $$$C_i$$$ the count of nodes of priority $$$i$$$ prior to doing any operations on the current layer, and we will compare the new count $$$C'_i$$$ of the next layer. We employ the following potential function for such counts: $$$\phi(C) = \sum 2^{i} \cdot C_i$$$

We strive to prove that $$$\phi(C)$$$ will remain bounded by $$$N$$$ throughout, meaning the maximum non-zero term of $$$C$$$ would be at position maximum $$$13$$$, indicating a maximum of $$$13$$$ tempo moves were ever done throughout all the layers for any starting point.

Consider a simpler case when $$$C_i = (A, 0, 0, 0, ...)$$$ (bottom layer case). We observe that whenever we increase the priority of some nodes (let their count be $$$B$$$), there has to be a surjection between some (lesser) set of non-iset nodes towards these $$$B$$$. Given that, with this being a surjection, this left side is greater than $$$B$$$, and this number is already bounded by $$$A-B$$$, we know that $$$2 \cdot B \leq A$$$. Meaning that $$$C'_0 \leq A - 2 \cdot B$$$ (We lose both the iset nodes and those that point to them), and that $$$C'_1 = B$$$. Of course we have then that $$$\phi(C') \leq (A - 2 \cdot B) \cdot 1 + (B) \cdot 2 = \phi(C)$$$. We note these computations regard the priorities of the nodes that are the parents of all nodes that do not engage in tempo moves. Subsequent nodes may be added (as part of transitioning to the new layer) with priority 0. However, the number of such increases (on $$$C_0$$$) is at most $$$N$$$. With that (and considering the same outline when proving for all the priority transitions that can occur on any layer) the proof is complete, and the maximum amount of tempo moves that can be done is then $$$13$$$.

Can you explain what the statement is?

+10

Two step communication:

First step assigns 0/1 labels to edges
Second step receives a current node and a list of incident edges (other endpoint + label) and needs to return an incident edge

Purpose is that, given first step knows some target node $$$t$$$, to assign labels and create a strategy such that the second step can generate from an arbitrary unknown node $$$s$$$ a path towards $$$t$$$ in at most $$$min + C$$$ steps, where $$$min$$$ is the min distance from $$$s$$$ to $$$t$$$ in the graph, and $$$C = 14$$$.

MladenP

+60

Hey everyone, we managed to get together enough info to publish the CEOI tasks for upsolve on Olympicode (5 of them at least):

Day 1:

Day 2:

Equal Mex
Splits
Theseus: we are still testing Communication tasks on the platform, should be up in a few days

Please note: we only had access to the tests and statements. Because we didn't have official solutions or the official TLs/MLs, we currently gave (hopefully) generous time limits, and will probably change them when we get more info.

Please let us know if you notice that something is wrong, or if you have any more official info about the solutions/limits.

During the first day of the contest, the last subtask for Boardgames was split into two subtasks.

However, I'm not sure how exactly. (I think it was 16 points -> $$$n, m \leq 30000$$$ and 17 points -> last one)

Hey, are you sure it wasn't $$$n \leq 30000$$$ and $$$m \leq 60000$$$? Because I'm seeing a lot of testcases like that here. Either way, we pinged the organizers and if we're able to get any more info from them we will make sure to include it.

ltunjic

yes, $$$n \le 30000$$$ and $$$m \le 60000$$$ are correct bounds

+11

Update: There was an error in our checker for Board Game expo. We fixed it, as well as improved the time limits everywhere and regraded submissions. Please recheck your submissions if you want the most accurate results.