Codeforces Round 583 (Div. 1 + Div. 2, based on Olympiad of Metropolises)
8 problems from Codeforces Round 583 (Div. 1 + Div. 2, based on Olympiad of Metropolises) (contest 1214), difficulty 1100-3200. 6/8 solutions verified against sample I/O.
Codeforces Round 583 (Div. 1 + Div. 2, based on Olympiad of Metropolises)
Div. 1+2 | 8 problems | 6/8 verified | Difficulty 1100-3200 | 25m 6s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Optimal Currency Exchange | 1400 | brute-force, math | 9,492 | 2m 2s | ✓ |
| B | Badges | 1100 | brute-force, math | 11,475 | 5m 4s | ✓ |
| C | Bad Sequence | 1200 | data-structures, greedy | 14,197 | 1m 43s | ✓ |
| D | Treasure Island | 1900 | dfs-and-similar, dp, flows | 7,169 | 3m 29s | ✓ |
| E | Petya and Construction Set | 2000 | constructive-algorithms, graphs, math | 2,863 | 2m 50s | |
| F | Employment | 2700 | greedy, sortings | 502 | 2m 40s | ✓ |
| G | Feeling Good | 3200 | bitmasks, data-structures | 330 | 1m 36s | ✓ |
| H | Tiles Placement | 2800 | constructive-algorithms, dfs-and-similar, trees | 458 | 5m 42s |
CF 1214H - Tiles Placement
We are given a tree with $n$ vertices, where each vertex represents a square in a pedestrian network. Each vertex must be assigned one of $k$ colors.
CF 1214D - Treasure Island
We are given an $n times m$ grid that represents a map. Each cell is either blocked or free. We start at the top-left cell $(1,1)$ and want to reach the bottom-right cell $(n,m)$.
CF 1214E - Petya and Construction Set
We are asked to build a graph on $2n$ labeled vertices using exactly $2n-1$ edges. Since a connected graph with $2n$ vertices and $2n-1$ edges is necessarily a tree, the construction is really about designing a tree on these labeled nodes.
CF 1214B - Badges
We are given three integers describing a small combinatorial setup. There are a fixed number of boys and girls in total, and exactly $n$ participants will attend an event, but we do not know how many of them are boys or girls.
CF 1214F - Employment
We have two multisets of points on a circle of length m. The first set contains the office locations. Office i is located in city a[i]. The second set contains the candidates. Candidate j lives in city b[j].
CF 1214G - Feeling Good
We are given a two-dimensional grid representing a chameleon's body. Initially, all cells are green. Each cell can be either green or blue, and the color may be flipped multiple times. Each flip affects a contiguous horizontal segment of a single row.
CF 1214A - Optimal Currency Exchange
We start with a fixed amount of money in rubles and want to convert it into foreign currency using an exchange office that sells only fixed denominations of dollar bills and euro bills. Each dollar costs a fixed amount in rubles, and each euro also has its own fixed ruble price.
CF 1214C - Bad Sequence
We are given a string of parentheses, like "(()))(" or ")(", and we need to determine whether moving at most one bracket to a different position can make it a correct bracket sequence.