Educational Codeforces Round 109 (Rated for Div. 2)

Solutions for Educational Codeforces Round 109 (Rated for Div. 2) (contest 1525). 3/6 problems verified against sample I/O. Difficulty range: 800-2800.

6 items

Educational Codeforces Round 109 (Rated for Div. 2)

Type: Div. 2 | Problems: 6 | Verified: 3/6 | Rating range: 800-2800 | Time: 24m 31s

Problem Name Rating Tags Solve Time Verified
A Potion-making 800 math, number-theory 9m 47s ✓
B Permutation Sort 900 constructive-algorithms, greedy 2m 16s ✓
C Robot Collisions 2000 data-structures, greedy, implementation 3m 3s ✗
D Armchairs 1800 dp, flows, graph-matchings 2m 16s ✓
E Assimilation IV 2100 combinatorics, dp, math 2m 33s ✗
F Goblins And Gnomes 2800 brute-force, dp, flows 4m 36s ✗
Practice › Codeforces Solutions › Educational Codeforces Round 109 (Rated for Div. 2) ›

CF 1525A - Potion-making

We are tasked with creating a potion that contains exactly $k%$ magic essence and $(100-k)%$ water. The cauldron starts empty, and we can only add one liter at a time of either ingredient.
codeforces competitive-programming math number-theory Jun 10, 2026
Practice › Codeforces Solutions › Educational Codeforces Round 109 (Rated for Div. 2) ›

CF 1525F - Goblins And Gnomes

The city is a directed acyclic graph. The statement guarantees that once a goblin leaves a hall, it can never come back, which is exactly the definition of a DAG. During wave i, exactly i goblins appear. Each goblin chooses a directed path.
codeforces competitive-programming brute-force dp flows graph-matchings Jun 10, 2026
Practice › Codeforces Solutions › Educational Codeforces Round 109 (Rated for Div. 2) ›

CF 1525E - Assimilation IV

Monocarp has an empire of n cities and wants to control m points on a map. Each city can build one Monument. When a Monument is built, it controls all points within a distance that grows by 1 each turn.
codeforces competitive-programming combinatorics dp math probabilities two-pointers Jun 10, 2026
Practice › Codeforces Solutions › Educational Codeforces Round 109 (Rated for Div. 2) ›

CF 1525D - Armchairs

We have a row of n armchairs, some of which are initially occupied by people. Our goal is to move every person to a currently empty armchair in such a way that all initially occupied seats become free.
codeforces competitive-programming dp flows graph-matchings greedy Jun 10, 2026
Practice › Codeforces Solutions › Educational Codeforces Round 109 (Rated for Div. 2) ›

CF 1525C - Robot Collisions

We have a set of robots moving along a one-dimensional line segment from 0 to $m$. Each robot starts at a distinct integer position between 0 and $m$ and moves either left or right at a constant speed of 1 unit per second.
codeforces competitive-programming data-structures greedy implementation sortings Jun 10, 2026
Practice › Codeforces Solutions › Educational Codeforces Round 109 (Rated for Div. 2) ›

CF 1525B - Permutation Sort

We are given a permutation of the numbers from 1 to n. In one operation, we may choose any contiguous segment of the array and rearrange the elements inside that segment however we like. The only restriction is that the chosen segment cannot be the entire array.
codeforces competitive-programming constructive-algorithms greedy Jun 10, 2026