Codeforces Round 1040 (Div. 2)

Solutions for Codeforces Round 1040 (Div. 2) (contest 2130). 2/8 problems verified against sample I/O. Difficulty range: 800-2600.

8 items

Codeforces Round 1040 (Div. 2)

Type: Div. 2 | Problems: 8 | Verified: 2/8 | Rating range: 800-2600 | Time: 12m 27s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Submission is All You Need	800	greedy, math	1m 16s	✓
B	Pathless	1100	constructive-algorithms	1m 38s	✗
C	Double Perspective	1300	constructive-algorithms, dsu, greedy	1m 8s	✓
D	Stay or Mirror	1600	data-structures, greedy	1m 46s	✗
E1	Interactive RBS (Easy Version)	1900	binary-search, constructive-algorithms, interactive	2m	✗
E2	Interactive RBS (Medium Version)	2000	binary-search, bitmasks, constructive-algorithms	1m 42s	✗
E3	Interactive RBS (Hard Version)	2300	interactive	1m 37s	✗
F	Permutation Blackhole	2600	dp	1m 20s	✗

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

CF 2130F - Permutation Blackhole

We are asked to count permutations that produce a given scoring pattern in a dynamic coloring process. Think of it as a row of white cells indexed from 1 to $n$.

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

CF 2130E3 - Interactive RBS (Hard Version)

We are asked to reconstruct a hidden sequence of parentheses of length $n$ using an interactive oracle. The sequence contains only '(' and ')' characters and is guaranteed to have at least one opening and one closing bracket.

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

CF 2130E2 - Interactive RBS (Medium Version)

We are given a hidden sequence of parentheses of length n, containing at least one '(' and one ')'. The sequence is regular in the sense that some of its contiguous substrings are valid bracket sequences.

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

CF 2130E1 - Interactive RBS (Easy Version)

In the original interactive problem there is a hidden bracket sequence consisting of '(' and ')'. We may ask queries about selected positions, and the judge returns the number of regular bracket substrings in the constructed string.

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

CF 2130D - Stay or Mirror

We are given a permutation of length $n$, which means an array containing every integer from $1$ to $n$ exactly once. For each element in this permutation, we are allowed to either leave it as is or replace it with a "mirrored" value defined by $2n - pi$.

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

CF 2130B - Pathless

We are given an array of integers where each element is either 0, 1, or 2, and a target sum s. Alice wants to start at the first element and move either left or right, step by step, until she reaches the last element.

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

CF 2130C - Double Perspective

We are given a set of integer pairs, each representing both a segment on a number line and an edge in a graph. Our goal is to select a subset of these pairs to maximize the difference between the total length of covered integers, called $f(S')$, and the number of nodes that…

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

CF 2130A - Submission is All You Need

We are given a multiset of non-negative integers, which we can think of as a bag of numbered tiles. Our goal is to repeatedly choose subsets of tiles and increase a score using one of two rules: either add the sum of the chosen tiles to the score, or add the minimum excluded…