Codeforces Round 548 (Div. 2)

Solutions for Codeforces Round 548 (Div. 2) (contest 1139). 6/6 problems verified against sample I/O. Difficulty range: 800-2500.

6 items

Codeforces Round 548 (Div. 2)

Type: Div. 2 | Problems: 6 | Verified: 6/6 | Rating range: 800-2500 | Time: 8m 42s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Even Substrings	800	implementation, strings	1m 8s	✓
B	Chocolates	1000	greedy, implementation	1m 27s	✓
C	Edgy Trees	1500	dfs-and-similar, dsu, graphs	1m 26s	✓
D	Steps to One	2300	dp, math, number-theory	1m 39s	✓
E	Maximize Mex	2400	flows, graph-matchings, graphs	1m 48s	✓
F	Dish Shopping	2500	data-structures, divide-and-conquer	1m 14s	✓

Practice › Codeforces Solutions › Codeforces Round 548 (Div. 2) ›

CF 1139D - Steps to One

We repeatedly choose a random integer from 1 to m, independently and uniformly. After each choice, we look at the gcd of all numbers chosen so far. The process stops as soon as this gcd becomes 1. We must compute the expected number of chosen integers.

Practice › Codeforces Solutions › Codeforces Round 548 (Div. 2) ›

CF 1139E - Maximize Mex

Each student belongs to exactly one club and has a potential value. On a given day, some students have already left their clubs permanently. From the remaining students, we may choose at most one student from each club. The chosen students form the contest team.

Practice › Codeforces Solutions › Codeforces Round 548 (Div. 2) ›

CF 1139F - Dish Shopping

We are asked to determine how many dishes each person in a city can buy given multiple constraints. Each dish has a price, a minimum standard requirement, and a beauty value. Each person has an income and a preferred beauty.

Practice › Codeforces Solutions › Codeforces Round 548 (Div. 2) ›

CF 1139B - Chocolates

We have a set of chocolate types, each with a limited stock. Our goal is to pick a number of chocolates from each type so that the total number of chocolates is maximized.

Practice › Codeforces Solutions › Codeforces Round 548 (Div. 2) ›

CF 1139C - Edgy Trees

We have a tree whose edges are colored either red (0) or black (1). We must count how many sequences of length k consisting of tree vertices are "good". For a sequence [a₁, a₂, ...

Practice › Codeforces Solutions › Codeforces Round 548 (Div. 2) ›

CF 1139A - Even Substrings

We are given a string of digits from 1 to 9. Our task is to count how many substrings, defined by any contiguous range of indices, represent even numbers. A substring is even if its last digit is even, since the number’s parity is determined entirely by the last digit.