Educational Codeforces Round 62 (Rated for Div. 2)

Solutions for Educational Codeforces Round 62 (Rated for Div. 2) (contest 1140). 6/7 problems verified against sample I/O. Difficulty range: 1000-2700.

7 items

Educational Codeforces Round 62 (Rated for Div. 2)

Type: Div. 2 | Problems: 7 | Verified: 6/7 | Rating range: 1000-2700 | Time: 10m 24s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Detective Book	1000	implementation	1m 21s	✓
B	Good String	1200	implementation, strings	1m 45s	✓
C	Playlist	1600	brute-force, data-structures, sortings	1m 29s	✓
D	Minimum Triangulation	1200	dp, greedy, math	1m 21s	✓
E	Palindrome-less Arrays	2200	combinatorics, divide-and-conquer, dp	1m 18s	✓
F	Extending Set of Points	2600	data-structures, divide-and-conquer, dsu	1m 23s	✓
G	Double Tree	2700	data-structures, divide-and-conquer, shortest-paths	1m 47s	✗

Practice › Codeforces Solutions › Educational Codeforces Round 62 (Rated for Div. 2) ›

CF 1140G - Double Tree

We are given a graph on $2n$ vertices that is highly structured: vertices are split into odd and even indices, and each side forms a tree with the same shape.

Practice › Codeforces Solutions › Educational Codeforces Round 62 (Rated for Div. 2) ›

CF 1140F - Extending Set of Points

We are maintaining a dynamic set of grid points on a large integer lattice. After each insertion or deletion, we are asked to compute not the size of the current set, but the size of its closure under a specific completion rule.

Practice › Codeforces Solutions › Educational Codeforces Round 62 (Rated for Div. 2) ›

CF 1140E - Palindrome-less Arrays

We are asked to count the number of arrays we can construct from a partially specified array of length n, where some elements are missing and represented by -1. Each -1 can be replaced by any integer from 1 to k.

Practice › Codeforces Solutions › Educational Codeforces Round 62 (Rated for Div. 2) ›

CF 1140D - Minimum Triangulation

We are given a regular polygon with n vertices labeled 1 through n in counter-clockwise order. The goal is to divide this polygon into non-overlapping triangles so that the sum of the “weights” of all triangles is minimized.

Practice › Codeforces Solutions › Educational Codeforces Round 62 (Rated for Div. 2) ›

CF 1140B - Good String

We are given a string made only of two symbols, and <. We are allowed to repeatedly perform operations that “push deletions” in a local direction: choosing a removes the character immediately to its right, while choosing a < removes the character immediately to its left.

Practice › Codeforces Solutions › Educational Codeforces Round 62 (Rated for Div. 2) ›

CF 1140C - Playlist

Each song has two attributes: its length t and its beauty b. If we choose some subset of songs, its score is $$(text{sum of lengths}) times (text{minimum beauty})$$ We may choose at most k songs, and we want the maximum possible score.

Practice › Codeforces Solutions › Educational Codeforces Round 62 (Rated for Div. 2) ›

CF 1140A - Detective Book

Ivan’s detective book is structured such that each page introduces a mystery, and the solution to that mystery is revealed on a later page. Concretely, we have a list of integers where the $i$-th integer $ai$ tells us the page that resolves the mystery introduced on page $i$.