2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
10 problems from 2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred) (contest 1070), difficulty 1300-3000. 4/10 solutions verified against sample I/O.
2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
ICPC/IOI | 10 problems | 4/10 verified | Difficulty 1300-3000 | 1h 3m
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Find a Number | 2200 | dp, graphs, number-theory | 2,614 | 5m 57s | ✓ |
| B | Berkomnadzor | 2400 | data-structures, greedy | 678 | 10m 24s | ✓ |
| C | Cloud Computing | 2000 | data-structures, greedy | 2,294 | 6m 31s | |
| D | Garbage Disposal | 1300 | greedy | 5,233 | 5m 31s | |
| F | Debate | 1500 | greedy | 3,850 | 4m 44s | ✓ |
| G | Monsters and Potions | 2300 | brute-force, dp, greedy | 930 | 3m | ✓ |
| H | BerOS File Suggestion | 1500 | brute-force, implementation | 3,854 | 6m 19s | |
| J | Streets and Avenues in Berhattan | 2300 | dp | 785 | 9m 13s | |
| L | Odd Federalization | 2600 | constructive-algorithms | 381 | 5m 37s | |
| M | Algoland and Berland | 3000 | constructive-algorithms, divide-and-conquer, geometry | 89 | 6m 42s |
CF 1070L - Odd Federalization
We are given an undirected graph of cities and roads. The task is to partition all vertices into some number of groups, and we are allowed to choose how many groups we want.
CF 1070M - Algoland and Berland
We are given two sets of points in the plane, one set belonging to Algoland and the other to Berland. The task is to construct exactly $a + b - 1$ straight line segments, each connecting one Berland city to one Algoland city. Every segment becomes a bidirectional road.
CF 1070J - Streets and Avenues in Berhattan
We are given a grid-like city structure formed by two independent labelings. There are horizontal streets and vertical avenues, and every street intersects every avenue, so each intersection corresponds to a pair consisting of one street and one avenue.
CF 1070H - BerOS File Suggestion
We are given a fixed collection of short file names and a stream of queries. Each query is a short string, and we must determine how many file names contain that string as a contiguous substring.
CF 1070G - Monsters and Potions
We are given a one-dimensional board of length $n$. Each cell can contain a monster with some HP, a potion that increases HP, or be empty. In addition, there are $m$ heroes initially placed on distinct empty cells, each hero starting with its own HP.
CF 1070D - Garbage Disposal
Each day produces some number of garbage units, and every unit must be thrown away either on the day it appears or on the following day.
CF 1070B - Berkomnadzor
We are given a collection of constraints over IPv4 addresses, where each constraint describes a contiguous interval of 32-bit integers. Some intervals are marked as forbidden and some are marked as required to remain accessible.
CF 1070C - Cloud Computing
We are given a timeline of n days. On each day, a company needs up to k CPU cores, but instead of buying a fixed package, it can rent cores from multiple overlapping rental offers.
CF 1070A - Find a Number
We are looking for a positive integer that satisfies two simultaneous constraints. First, it must be divisible by a given integer $d$. Second, when written in decimal form, the sum of its digits must equal a given value $s$.
CF 1070F - Debate
We are asked to choose a subset of people, each having a weight (influence) and one of four “support types” describing whether they support Alice, Bob, both, or neither.