Codeforces Round 875 (Div. 2)

Solutions for Codeforces Round 875 (Div. 2) (contest 1831). 2/6 problems verified against sample I/O. Difficulty range: 800-2800.

6 items

Codeforces Round 875 (Div. 2)

Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 800-2800 | Time: 13m 58s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Twin Permutations	800	constructive-algorithms	1m 45s	✗
B	Array merging	1000	constructive-algorithms, greedy	1m 23s	✓
C	Copil Copac Draws Trees	1400	dfs-and-similar, dp, graphs	1m 23s	✓
D	The BOSS Can Count Pairs	2000	binary-search, brute-force, data-structures	1m 36s	✗
E	Hyperregular Bracket Strings	2400	combinatorics, data-structures, hashing	3m 20s	✗
F	Mex Tree	2800	brute-force, dp, trees	4m 31s	✗

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

CF 1831F - Mex Tree

We are asked to maximize the sum of MEX values over all paths in a tree where each node can be colored either 0 or 1. A path is defined as the unique simple path between any two nodes, including paths that start and end at the same node.

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

CF 1831E - Hyperregular Bracket Strings

We are asked to count bracket sequences of length $n$ that are globally regular, while also being locally regular on certain specified subintervals. The input gives us the length $n$ and a list of $k$ intervals $[li, ri]$.

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

CF 1831D - The BOSS Can Count Pairs

We are given two arrays a and b of equal length n. The task is to count the number of index pairs (i, j) with i < j such that the product of the a elements at those indices equals the sum of the corresponding b elements: a[i] a[j] = b[i] + b[j].

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

CF 1831A - Twin Permutations

We are given a permutation a of length n, which means it contains all integers from 1 to n exactly once in some order. Our task is to construct another permutation b of the same length such that the sequence formed by summing corresponding elements, ai + bi, is non-decreasing.

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

CF 1831B - Array merging

We are given two arrays, a and b, of the same length n. The task is to form a new array c of length 2n by successively taking the first element of either array until both are exhausted.

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

CF 1831C - Copil Copac Draws Trees

We are given a tree with $n$ vertices, described as a list of $n-1$ edges. Copil Copac draws the tree step by step: he always starts with vertex 1, then repeatedly scans the list of edges in order, drawing any vertex connected to a previously drawn vertex.