Codeforces Round 1073 (Div. 1)

8 problems from Codeforces Round 1073 (Div. 1) (contest 2190), difficulty 1200-3300. 1/8 solutions verified against sample I/O.

8 items

Codeforces Round 1073 (Div. 1)

Div. 1 | 8 problems | 1/8 verified | Difficulty 1200-3300 | 16m 47s

# Problem Rating Tags Accepted Time ✓
A Sorting Game 1200 constructive-algorithms, games, greedy 17,109 1m 53s
B1 Sub-RBS (Easy Version) 1400 combinatorics, constructive-algorithms, dp 10,660 3m 3s
B2 Sub-RBS (Hard Version) 1900 dp, games, implementation 3,179 3m 32s
C Comparable Permutations 2300 greedy, implementation, interactive 1,290 1m 49s
D Prufer Vertex 2500 combinatorics, dsu, number-theory 950 2m 45s
E Median Permutation 3200 combinatorics 235 1m 38s ✓
F Xor Product 3300 bitmasks, dp 92 57s
G Maximize Determinant 3300 graphs 96 1m 10s
Practice › Codeforces Solutions › Codeforces Round 1073 (Div. 1) ›

CF 2190G - Maximize Determinant

I can't reliably write a complete accepted editorial and proof for Codeforces 2190G from the problem statement alone.
codeforces competitive-programming graphs Jun 7, 2026
Practice › Codeforces Solutions › Codeforces Round 1073 (Div. 1) ›

CF 2190D - Prufer Vertex

We start with a forest. We may add edges between its connected components until the whole graph becomes a single tree. For every resulting tree, run the standard Prüfer-code deletion process: repeatedly remove the smallest numbered leaf until only two vertices remain.
codeforces competitive-programming combinatorics dsu number-theory probabilities trees Jun 7, 2026
Practice › Codeforces Solutions › Codeforces Round 1073 (Div. 1) ›

CF 2190E - Median Permutation

Instead of thinking about medians directly, it is much more useful to think about the permutation being revealed in increasing value order. Suppose we process the values of a permutation from 1 to n. When value x is processed, its position becomes "active".
codeforces competitive-programming combinatorics Jun 7, 2026
Practice › Codeforces Solutions › Codeforces Round 1073 (Div. 1) ›

CF 2190F - Xor Product

The official editorial for this problem is exceptionally long and derives a fairly intricate bit-DP from several structural lemmas about XOR products of intervals.
codeforces competitive-programming bitmasks dp Jun 7, 2026
Practice › Codeforces Solutions › Codeforces Round 1073 (Div. 1) ›

CF 2190C - Comparable Permutations

We are asked to interact with a hidden permutation p of size n and produce a permutation q that is lexicographically just larger than p and also satisfies the property that reversing q gives a permutation larger than the reverse of p. The catch is that we never see p directly.
codeforces competitive-programming greedy implementation interactive sortings two-pointers Jun 7, 2026
Practice › Codeforces Solutions › Codeforces Round 1073 (Div. 1) ›

CF 2190B2 - Sub-RBS (Hard Version)

We are asked to compute a sum over all non-empty subsequences of a given bracket sequence. Each subsequence has a “score” defined as the length of its longest regular bracket subsequence that is strictly “better” than itself.
codeforces competitive-programming dp games implementation strings Jun 7, 2026
Practice › Codeforces Solutions › Codeforces Round 1073 (Div. 1) ›

CF 2190B1 - Sub-RBS (Easy Version)

We are given a regular bracket sequence s. A regular bracket sequence (RBS) is one where every prefix contains at least as many '(' as ')', and the total numbers of opening and closing brackets are equal.
codeforces competitive-programming combinatorics constructive-algorithms dp greedy strings two-pointers Jun 7, 2026
Practice › Codeforces Solutions › Codeforces Round 1073 (Div. 1) ›

CF 2190A - Sorting Game

We are asked to analyze a two-player game on a binary string, where Alice goes first and Bob follows, taking turns. On their turn, a player may select any strictly non-increasing subsequence of the string and rearrange it to be non-decreasing.
codeforces competitive-programming constructive-algorithms games greedy Jun 7, 2026