Codeforces Round 875 (Div. 1)

6 problems from Codeforces Round 875 (Div. 1) (contest 1830), difficulty 1400-3500. 3/6 solutions verified against sample I/O.

6 items

Codeforces Round 875 (Div. 1)

Div. 1 | 6 problems | 3/6 verified | Difficulty 1400-3500 | 14m 54s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Copil Copac Draws Trees	1400	dfs-and-similar, dp, graphs	20,309	2m	✓
B	The BOSS Can Count Pairs	2000	brute-force, math	5,850	3m 9s	✓
C	Hyperregular Bracket Strings	2400	combinatorics, greedy, hashing	2,184	1m 14s
D	Mex Tree	2800	brute-force, dp, trees	932	2m 59s	✓
E	Bully Sort	3500	data-structures, math	324	2m 23s
F	The Third Grace	3200	data-structures, dp	360	3m 9s

Practice › Codeforces Solutions › Codeforces Round 875 (Div. 1) ›

CF 1830F - The Third Grace

We are given a line of positions from 1 to m. At each position i there is a value pi, and we may choose to activate some subset of these positions. We are also given n intervals on the same line. For each interval [l, r], we look at the activated positions inside it.

Practice › Codeforces Solutions › Codeforces Round 875 (Div. 1) ›

CF 1830E - Bully Sort

We are given a permutation of size $n$, and we repeatedly apply a very specific “bullying” operation to measure how far the permutation is from being sorted. At any moment, we look at all indices where the value is not already correct.

Practice › Codeforces Solutions › Codeforces Round 875 (Div. 1) ›

CF 1830D - Mex Tree

Each test case gives a tree, and we must assign every vertex a label of either 0 or 1. Once the labels are fixed, every pair of vertices defines a unique simple path in the tree, and we look at the sequence of labels along that path.

Practice › Codeforces Solutions › Codeforces Round 875 (Div. 1) ›

CF 1830B - The BOSS Can Count Pairs

We are given two arrays of equal length, and we need to count how many index pairs behave in a very specific “cross condition”.

Practice › Codeforces Solutions › Codeforces Round 875 (Div. 1) ›

CF 1830A - Copil Copac Draws Trees

We are given a tree described by an ordered list of edges. The edges are not just connectivity information, their order matters because the drawing process scans them sequentially again and again. The process starts with only vertex 1 being considered “drawn”.

Practice › Codeforces Solutions › Codeforces Round 875 (Div. 1) ›

CF 1830C - Hyperregular Bracket Strings

Working