Since CEOI 2025 is over and the tasks and test data have been published, can we discuss the solutions here?↵
↵
Here are the [tasks](https://ceoi2025.utcluj.ro/category/13).↵
↵
Upd: you can find the tasks [here](https://codeforces.me/blog/entry/144670?#comment-1293960) (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:↵
$$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](https://codeforces.me/blog/entry/130107) 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:↵
↵
$$\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 a chosen $j$ if and only if $\text{pref}[i]$ falls within the cyclic interval:↵
$$(\text{pref}[j], \, \text{pref}[j] + c - (v[i] \bmod c))$$↵
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↵
↵
> **TL;DR Strategy:** 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 < 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! :)
↵
Here are the [tasks](https://ceoi2025.utcluj.ro/category/13).↵
↵
Upd: you can find the tasks [here](https://codeforces.me/blog/entry/144670?#comment-1293960) (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:↵
$$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](https://codeforces.me/blog/entry/130107) 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:↵
↵
$$\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 a chosen $j$ if and only if $\text{pref}[i]$ falls within the cyclic interval:↵
$$(\text{pref}[j], \, \text{pref}[j] + c - (v[i] \bmod c))$$↵
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↵
↵
> **TL;DR Strategy:** 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 < 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! :)
