Codeforces Round 576 (Div. 1)

Solutions for Codeforces Round 576 (Div. 1) (contest 1198). 4/6 problems verified against sample I/O. Difficulty range: 1600-2900.

6 items

Codeforces Round 576 (Div. 1)

Type: Div. 1 | Problems: 6 | Verified: 4/6 | Rating range: 1600-2900 | Time: 23m 39s

Problem	Name	Rating	Tags	Solve Time	Verified
A	MP3	1600	sortings, two-pointers	2m 46s	✓
B	Welfare State	1600	binary-search, brute-force, data-structures	3m 24s	✓
C	Matching vs Independent Set	2000	constructive-algorithms, graphs, greedy	6m 44s	✗
D	Rectangle Painting 1	2300	dp	4m 34s	✓
E	Rectangle Painting 2	2500	flows, graph-matchings, graphs	4m 14s	✗
F	GCD Groups 2	2900	greedy, number-theory, probabilities	1m 57s	✓

Practice › Codeforces Solutions › Codeforces Round 576 (Div. 1) ›

CF 1198D - Rectangle Painting 1

We are given a binary grid where some cells are black and the rest are already white. Our only operation is to pick any axis-aligned rectangle and repaint every cell inside it to white. Each such operation has a cost equal to the larger of its height or width.

Practice › Codeforces Solutions › Codeforces Round 576 (Div. 1) ›

CF 1198E - Rectangle Painting 2

We are given an extremely large $n times n$ grid, but instead of listing individual black cells, the input describes black regions as up to 50 axis-aligned rectangles. Every cell outside these rectangles is white initially, and inside them is black.

Practice › Codeforces Solutions › Codeforces Round 576 (Div. 1) ›

CF 1198A - MP3

We are given a sequence of sound intensities, each a non-negative integer. Think of it as a time series of sampled audio amplitudes.

Practice › Codeforces Solutions › Codeforces Round 576 (Div. 1) ›

CF 1198C - Matching vs Independent Set

We are given several undirected graphs, each with exactly $3n$ vertices. For each graph, we must construct one of two specific structures of size $n$: either a matching consisting of $n$ edges, or an independent set consisting of $n$ vertices.

Practice › Codeforces Solutions › Codeforces Round 576 (Div. 1) ›

CF 1198B - Welfare State

We are maintaining a dynamic list of balances for a fixed set of citizens. Initially, each citizen has a known amount of money. Then a sequence of events modifies these balances in two different ways.

Practice › Codeforces Solutions › Codeforces Round 576 (Div. 1) ›

CF 1198F - GCD Groups 2

We are given a list of integers and must split it into two non-empty groups. The requirement is not about sums or sizes, but about multiplicative structure: in each group, if you take the greatest common divisor of all its elements, the result must be exactly one.