Codeforces Round 1082 (Div. 1)

9 problems from Codeforces Round 1082 (Div. 1) (contest 2201), difficulty 1300-3500. 1/9 solutions verified against sample I/O.

9 items

Codeforces Round 1082 (Div. 1)

Div. 1 | 9 problems | 1/9 verified | Difficulty 1300-3500 | 21m

#	Problem	Rating	Tags	Accepted	Time	✓
A1	Lost Civilization (Easy Version)	1300	data-structures	11,027	4m 30s
A2	Lost Civilization (Hard Version)	1700	data-structures, dp	5,078	2m 58s
B	Recollect Numbers	1700	constructive-algorithms	4,944	1m 50s
C	Rigged Bracket Sequence	2000	combinatorics, dp, greedy	1,985	1m 44s
D	Binary Not Search and Queries	2500	data-structures, greedy, implementation	783	1m 36s	✓
E	ABBA Counting	2900	fft, math, number-theory	277	2m 41s
F1	Monotone Monochrome Matrices (Medium Version)	2900	data-structures, hashing	269	1m 51s
F2	Monotone Monochrome Matrices (Hard Version)	2800	constructive-algorithms, data-structures, hashing	397	1m 56s
G	Codeforces Heuristic Contest 1001	3500	constructive-algorithms	65	1m 54s

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

CF 2201G - Codeforces Heuristic Contest 1001

We are given a grid of size $n times n$ where each cell can be thought of as a vertex labeled by its row and column $(r,c)$. Two vertices are connected if the squared Euclidean distance between them is exactly 13.

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

CF 2201F2 - Monotone Monochrome Matrices (Hard Version)

We start with an $n times n$ grid that is completely empty, and we gradually paint some cells black. After each paint operation, we must decide whether the current black-white pattern avoids a very specific forbidden configuration involving two rows and two columns.

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

CF 2201F1 - Monotone Monochrome Matrices (Medium Version)

We are maintaining an $n times n$ grid that starts completely empty in the sense that every cell is white. Over time, we flip certain cells to black, one at a time, and after each flip we must decide whether the current black-white pattern satisfies a structural restriction…

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

CF 2201E - ABBA Counting

We are given a string T of even length n, consisting of the characters 'a', 'b', and '?'. The question asks us to count all possible strings S that match T wherever T specifies a character (i.e., S[i] = T[i] when T[i] is not '?

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

CF 2201D - Binary Not Search and Queries

We are given a sequence of integers and a set of queries that modify elements of the sequence. After each modification, we are asked to compute two values derived from the sequence: the maximum length of two subarrays that are permutations of each other, and how many pairs of…

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

CF 2201A1 - Lost Civilization (Easy Version)

We are given a sequence of integers that has been generated by a very simple algorithm: start with some initial sequence of length m, and repeatedly choose an element and insert its value plus one immediately after it until the sequence reaches length m + k.

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

CF 2201C - Rigged Bracket Sequence

We are given a well-formed bracket string, meaning it behaves like a correctly nested sequence of parentheses. From this string, we choose some positions to form a subsequence, and then we perform a cyclic right shift on the characters located at those chosen positions.

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

CF 2201A2 - Lost Civilization (Hard Version)

The problem gives us a mysterious sequence generated by an ancient algorithm. Starting from a short sequence of length m, the algorithm repeatedly inserts a new number xi + 1 after any chosen element xi until the sequence reaches length m+k.

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

CF 2201B - Recollect Numbers

We are given $2n$ cards where each number from $1$ to $n$ appears exactly twice. The cards are initially face down, and in each turn, the player flips two cards. If the flipped cards show the same number, they are removed; otherwise, they are flipped back.