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:

1. Initially, we invoke the function $$$f(1, n)$$$.
2. Find the position $$$i$$$ closest to the border such that $$$i$$$ and $$$i+1$$$ are not in the same connected component.
3. If the subgraph from $$$L$$$ to $$$R$$$ is connected, we can just return $$$1$$$.
4. 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.

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:

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.

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:

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 a chosen $$$j$$$ if and only if $$$\text{pref}[i]$$$ falls within the cyclic interval:

evaluated modulo $$$c$$$. This can now be solved with segment tree supporting range addition and range minimum query.

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: 1. Divide the array by its midpoint and inspect all queries intersecting the middle. 2. 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$$$. 3. 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.

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.

1. 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.
2. 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.
3. 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.
4. 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! :)