Educational Codeforces Round 47 (Rated for Div. 2)

7 problems from Educational Codeforces Round 47 (Rated for Div. 2) (contest 1009), difficulty 800-2400. 5/7 solutions verified against sample I/O.

7 items

Educational Codeforces Round 47 (Rated for Div. 2)

Div. 2 | 7 problems | 5/7 verified | Difficulty 800-2400 | 19m 17s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Game Shopping	800	implementation	12,310	1m 26s	✓
B	Minimum Ternary String	1400	greedy, implementation	10,719	2m 39s
C	Annoying Present	1700	greedy, math	5,557	3m 45s	✓
D	Relatively Prime Graph	1700	brute-force, constructive-algorithms, graphs	6,658	1m 55s
E	Intercity Travelling	2000	combinatorics, math, probabilities	3,363	3m 58s	✓
F	Dominant Indices	2300	data-structures, dsu, trees	7,743	1m 59s	✓
G	Allowed Letters	2400	bitmasks, flows, graph-matchings	1,064	3m 35s	✓

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

CF 1009G - Allowed Letters

We are given a string made only from the first six lowercase letters. We are allowed to rearrange its characters arbitrarily by swapping any positions any number of times, so effectively we can treat it as a multiset of letters with full permutation freedom.

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

CF 1009E - Intercity Travelling

We are given a road split into $n$ unit segments, and each segment has a “base fatigue cost” $ai$ that applies when Leha starts a fresh driving session.

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

CF 1009F - Dominant Indices

We are working with a rooted tree where vertex 1 is considered the root. For every vertex $x$, we conceptually look at all nodes in its subtree and group them by their distance from $x$ in terms of edges downward in the tree.

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

CF 1009C - Annoying Present

We start with an array of length $n$ that initially contains only zeros. Bob performs $m$ operations. Each operation is defined by a pair $(x, d)$, and Bob is allowed to pick a center position $i$ in the array.

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

CF 1009D - Relatively Prime Graph

We are asked to build a simple undirected graph on vertices numbered from 1 to n. The graph must have exactly m edges, must be connected, and must avoid both self-loops and repeated edges.

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

CF 1009B - Minimum Ternary String

We are given a string made only of digits 0, 1, and 2. We are allowed to repeatedly swap adjacent pairs if they are 0 and 1 in either direction, or 1 and 2 in either direction.

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

CF 1009A - Game Shopping

The shop presents a line of games, each with a fixed price, and Maxim walks through them strictly from left to right.