Codeforces Round 1079 (Div. 1)

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

8 items

Codeforces Round 1079 (Div. 1)

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

#	Problem	Rating	Tags	Accepted	Time	✓
A	Game with a Fraction	1200	games, math	15,791	2m 40s
B	Another Problem about Beautiful Pairs	1600	brute-force, math, two-pointers	8,565	1m 18s	✓
C1	Interactive Graph (Simple Version)	1800	binary-search, combinatorics, dfs-and-similar	3,584	1m 53s
C2	Interactive Graph (Hard Version)	2000	combinatorics, dfs-and-similar, dp	2,516	2m 10s
D	Double Bracket Sequence	2500	data-structures, dp, expression-parsing	992	2m 12s
E1	Fuzzy Concatenation (Easy Version)	2900	binary-search, bitmasks, brute-force	282	2m
E2	Fuzzy Concatenation (Hard version)	3000	binary-search, bitmasks, data-structures	198	1m 35s	✓
F	Indivisible	3300	brute-force, constructive-algorithms, graphs	107	2m 44s

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

CF 2196F - Indivisible

We are asked to construct a graph with a given number of vertices n and edges m such that it cannot be split into two parts where the sums of degrees of each part are equal. The graph must be simple, with no loops or multiple edges.

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

CF 2196E2 - Fuzzy Concatenation (Hard version)

We are given a source string s and a target string t. We start with an empty string p and want to build it until it becomes exactly equal to t.

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

CF 2196E1 - Fuzzy Concatenation (Easy Version)

We are given a source string s and a target string t. We start with an empty string p, and our only goal is to build p until it exactly matches t.

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

CF 2196D - Double Bracket Sequence

We are given a string consisting of round brackets "(" and ")", and square brackets "[" and "]". The string has even length.

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

CF 2196C2 - Interactive Graph (Hard Version)

We are asked to reconstruct a hidden directed acyclic graph (DAG) by interacting with a system that enumerates all paths in lexicographic order. Each query allows us to ask for the $k$-th path.

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

CF 2196A - Game with a Fraction

We are given two integers, $p$ and $q$, representing a fraction $frac{p}{q}$. Alice and Bob play a turn-based game where on each turn a player can decrease $p$ by 1 (if $p 0$) or decrease $q$ by 1 (if $q 1$). Alice goes first.

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

CF 2196C1 - Interactive Graph (Simple Version)

We are given a directed acyclic graph with up to 15 vertices. The edges are unknown, but we are allowed to probe the graph through an oracle. Each query asks for the k-th path in the lexicographically sorted list of all valid directed paths in the graph.

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

CF 2196B - Another Problem about Beautiful Pairs

We are given an array and we want to count pairs of positions where a very specific relationship holds between the values at those positions and their distance in the array.