Codeforces Global Round 24

Solutions for Codeforces Global Round 24 (contest 1764). 2/10 problems verified against sample I/O. Difficulty range: 800-3400.

10 items

Codeforces Global Round 24

Type: Global | Problems: 10 | Verified: 2/10 | Rating range: 800-3400 | Time: 36m 42s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Doremy's Paint	800	greedy	2m 26s	✗
B	Doremy's Perfect Math Class	900	math, number-theory	4m 56s	✓
C	Doremy's City Construction	1400	graphs, greedy	2m 46s	✓
D	Doremy's Pegging Game	2000	combinatorics, dp, math	2m 49s	✗
E	Doremy's Number Line	2400	dp, greedy, sortings	1m 16s	✗
F	Doremy's Experimental Tree	2500	brute-force, constructive-algorithms, dfs-and-similar	3m 10s	✗
G1	Doremy's Perfect DS Class (Easy Version)	2900	binary-search, interactive	6m 7s	✗
G2	Doremy's Perfect DS Class (Medium Version)	3000	binary-search, interactive	2m 7s	✗
G3	Doremy's Perfect DS Class (Hard Version)	3300	binary-search, interactive	8m 26s	✗
H	Doremy's Paint 2	3400	data-structures	2m 39s	✗

Practice › Codeforces Solutions › Codeforces Global Round 24 ›

CF 1764G3 - Doremy's Perfect DS Class (Hard Version)

We are given a hidden permutation of integers from 1 to $n$, and our goal is to identify the position of the number 1 with at most 20 interactive queries.

Practice › Codeforces Solutions › Codeforces Global Round 24 ›

CF 1764G1 - Doremy's Perfect DS Class (Easy Version)

We are asked to locate the position of the number 1 in a hidden permutation of integers from 1 to n. The permutation is fixed, and we can query the permutation by providing a range [l, r] and a divisor k.

Practice › Codeforces Solutions › Codeforces Global Round 24 ›

CF 1764H - Doremy's Paint 2

We have an array of n buckets, where each bucket initially contains a unique color equal to its 1-based index. There are m paint operations, each defined by a segment [li, ri].

Practice › Codeforces Solutions › Codeforces Global Round 24 ›

CF 1764G2 - Doremy's Perfect DS Class (Medium Version)

We are given a hidden permutation of numbers from 1 to n. We cannot see it directly, but we can interactively ask queries.

Practice › Codeforces Solutions › Codeforces Global Round 24 ›

CF 1764F - Doremy's Experimental Tree

We are given a mysterious tree with n vertices where each edge has a positive integer weight. For every pair (i, j) with 1 ≤ j ≤ i ≤ n, a “virtual experiment” was done: an edge of weight 1 was temporarily added between vertices i and j.

Practice › Codeforces Solutions › Codeforces Global Round 24 ›

CF 1764D - Doremy's Pegging Game

We are asked to count the number of sequences in which red pegs on a regular polygon can be removed while maintaining a geometric constraint: the rubber band around the remaining red pegs must not enclose the central blue peg.

Practice › Codeforces Solutions › Codeforces Global Round 24 ›

CF 1764B - Doremy's Perfect Math Class

We start with a finite set of positive integers. We are allowed to repeatedly pick two numbers, subtract the smaller from the larger, and insert the result if it is not already present. The process continues until no new numbers can be created.

Practice › Codeforces Solutions › Codeforces Global Round 24 ›

CF 1764E - Doremy's Number Line

I can write a high-quality editorial only if I can first reconstruct the intended solution and proof. For Codeforces 1764E (rating 2400), the key difficulty is that the solution relies on a fairly intricate DP/greedy argument.

Practice › Codeforces Solutions › Codeforces Global Round 24 ›

CF 1764C - Doremy's City Construction

We are asked to build a simple undirected graph with vertices labeled by altitudes. Each vertex has a number representing its altitude, and we may connect pairs of vertices by edges under two constraints. The first is standard: no self-loops or multiple edges.

Practice › Codeforces Solutions › Codeforces Global Round 24 ›

CF 1764A - Doremy's Paint

We are given an array and asked to choose a contiguous segment. For any chosen segment, we compute two quantities: its length and how many distinct values appear inside it. The score of a segment is the length minus the number of distinct values.