Educational Codeforces Round 58 (Rated for Div. 2)

Solutions for Educational Codeforces Round 58 (Rated for Div. 2) (contest 1101). 5/7 problems verified against sample I/O. Difficulty range: 1000-2400.

7 items

Educational Codeforces Round 58 (Rated for Div. 2)

Type: Div. 2 | Problems: 7 | Verified: 5/7 | Rating range: 1000-2400 | Time: 33m 51s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Minimum Integer	1000	math	5m 4s	✓
B	Accordion	1300	greedy, implementation	1m 13s	✓
C	Division and Union	1500	sortings	6m 57s	✗
D	GCD Counting	2000	data-structures, dfs-and-similar, dp	4m 55s	✓
E	Polycarp's New Job	1500	implementation	4m 23s	✓
F	Trucks and Cities	2400	binary-search, dp	1m	✓
G	(Zero XOR Subset)-less	2300	math, matrices	10m 19s	✗

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

CF 1101G - (Zero XOR Subset)-less

We are given a sequence of integers, and we want to cut it into consecutive chunks. Every element must belong to exactly one chunk, and every chunk must be non-empty. After splitting, we look at all possible non-empty collections of these chunks.

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

CF 1101E - Polycarp's New Job

We are processing a growing collection of rectangular banknotes. Each time a note is added, it stays forever. Later we receive queries asking whether all notes seen so far can be placed inside a given rectangular wallet.

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

CF 1101C - Division and Union

We are given several independent test cases. Each test case provides a collection of closed segments on a number line. The task is to assign every segment to one of two groups such that no segment in one group overlaps with any segment in the other group.

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

CF 1101A - Minimum Integer

Each query describes a forbidden interval on the number line and a fixed step size. We are asked to find the smallest positive integer that is a multiple of a given number $d$, but lies strictly outside the interval $[l, r]$.

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

CF 1101D - GCD Counting

We are given a tree where each node carries an integer label. For any two vertices, consider the unique simple path between them. Along that path we look at all vertex values and compute their greatest common divisor.

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

CF 1101F - Trucks and Cities

We have a sequence of cities arranged along a single road at increasing distances from the origin. Each truck travels from a starting city to a destination city along this road. The trucks consume fuel linearly with distance and start with a full tank.

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

CF 1101B - Accordion

We are given a string containing letters and a few special characters: [, ], :, and The constraints tell us that the string can be up to 500,000 characters long.