Codeforces Round 1077 (Div. 1)

8 problems from Codeforces Round 1077 (Div. 1) (contest 2187), difficulty 1300-3500. 0/8 solutions verified against sample I/O.

8 items

Codeforces Round 1077 (Div. 1)

Div. 1 | 8 problems | 0/8 verified | Difficulty 1300-3500 | 15m 1s

#	Problem	Rating	Tags	Accepted	Time
A	Restricted Sorting	1300	greedy, sortings	15,850	3m 14s
B	Shortest Statement Ever			5,276
C	Jerry and Tom	2300	data-structures, dfs-and-similar, dsu	1,369	2m 26s
D	Cool Problem			634
E	Doors and Keys	3500	brute-force, data-structures, dp	325	2m 11s
F1	Al Fine (Maximizing Version)	3100	binary-search, data-structures, divide-and-conquer	212	2m 29s
F2	Al Fine (Counting Version)	3500	dp, trees	70	54s
G	Many Cartesian Trees	3500	greedy, sortings, trees	98	3m 47s

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

CF 2187G - Many Cartesian Trees

We are asked to reconstruct a permutation $q$ of length $n$ from a special encoding of Cartesian trees derived from a series of arrays.

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

CF 2187F1 - Al Fine (Maximizing Version)

We are given two DFS preorder traversals of the same set of vertices {0,1,...,n}. The tree itself is unknown. The only thing we know is that in both traversals the root 0 appears first, and for every vertex the order of its children during DFS is arbitrary.

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

CF 2187F2 - Al Fine (Counting Version)

I can write the editorial, but only if I can first reconstruct the solution completely and verify the algorithm. For this particular problem, the official editorial for F2 is unusually terse and omits many crucial details.

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

CF 2187E - Doors and Keys

We have a sequence of $n+1$ rooms connected by $n$ doors. Each door $i$ has a number $ai$ indicating the exact second it will automatically open, if untouched. Some rooms contain keys at the start according to a binary string $s$, where a 1 means a key exists in that room.

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

CF 2187A - Restricted Sorting

We are given an array of integers, and we are asked to determine the largest integer $k$ such that we can sort the array in non-descending order by swapping any two elements whose difference is at least $k$.

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

CF 2187C - Jerry and Tom

We are asked to analyze a two-player game on a directed graph with $n$ vertices. The graph is almost a chain: for every vertex $u$ from 1 to $n-1$, there is an edge $u to u+1$.