2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Teams Preferred)
14 problems from 2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Teams Preferred) (contest 1250), difficulty 800-3100. 6/14 solutions verified against sample I/O.
2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Teams Preferred)
ICPC/IOI | 14 problems | 6/14 verified | Difficulty 800-3100 | 38m 55s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Berstagram | 1400 | implementation | 4,416 | 7m 25s | ✓ |
| B | The Feast and the Bus | 1800 | brute-force, constructive-algorithms, greedy | 2,799 | 1m 44s | |
| C | Trip to Saint Petersburg | 2100 | data-structures | 1,447 | 1m 50s | |
| D | Conference Problem | 3000 | dp | 216 | 1m 42s | |
| E | The Coronation | 2300 | graphs, implementation | 909 | 1m 40s | |
| F | Data Center | 800 | brute-force, implementation | 8,383 | 2m 26s | ✓ |
| G | Discarding Game | 2300 | dp, greedy, two-pointers | 775 | 1m 59s | |
| H | Happy Birthday | 1500 | math | 4,290 | 4m 10s | ✓ |
| I | Show Must Go On | 3100 | binary-search, brute-force, greedy | 171 | 1m 36s | |
| J | The Parade | 1800 | binary-search, greedy | 3,244 | 1m 59s | ✓ |
| K | Projectors | 3100 | flows, graphs | 319 | 1m 52s | |
| L | Divide The Students | 1500 | binary-search, greedy, math | 4,689 | 7m 8s | ✓ |
| M | SmartGarden | 2500 | constructive-algorithms, divide-and-conquer | 391 | 1m 24s | ✓ |
| N | Wires | 2000 | dfs-and-similar, graphs, greedy | 1,765 | 2m |
CF 1250N - Wires
Each wire connects two contact points, and we say two wires are related if they share at least one endpoint, or if there is a chain of wires where consecutive wires share endpoints.
CF 1250K - Projectors
We are given two sets of time intervals: one set represents lectures, the other represents seminars. Each lecture must be assigned a high-definition projector, while each seminar can use any projector, either HD or ordinary.
CF 1250M - SmartGarden
The garden is an $n times n$ grid where each cell is either a plant that must be watered or a slab that must never be touched. The layout is highly structured: all diagonal cells are slabs, and every cell strictly below the diagonal that touches the diagonal also becomes a slab.
CF 1250G - Discarding Game
We are given two sequences that evolve in lockstep over time. In each round, the human gains some amount of points while the computer also gains points. Both totals accumulate independently across rounds.
CF 1250I - Show Must Go On
We are given a list of dancers, each with a fixed awkwardness value. A “concert” is defined as choosing a subset of these dancers. Not all subsets are allowed: the total awkwardness of a chosen subset must not exceed a limit $k$.
CF 1250E - The Coronation
We are given several binary strings, each representing a necklace. Each position in a string is either 0 or 1, and we interpret this as two types of gems. We are allowed to reverse some of these strings.
CF 1250C - Trip to Saint Petersburg
We are given a collection of projects, each defined by a time interval and a payment. If we choose a trip to Saint Petersburg, we also fix a continuous interval of days during which we stay in the city.
CF 1250B - The Feast and the Bus
We are given a collection of employees, where each employee belongs to exactly one team. The only meaningful structure in the input is the frequency of each team, since employees from the same team must always travel together.
CF 1250D - Conference Problem
We are given several scientists, each staying at the conference for a time interval from day $li$ to $ri$, inclusive. Some scientists explicitly belong to a known country $ci 0$, while others have no country assigned ($ci = 0$).
CF 1250L - Divide The Students
We are given three groups of students determined by their preferred programming language. The task is to split all students into exactly three practice groups. The only restriction is that a single group is not allowed to contain both Assembler fans and C++ fans at the same time.
CF 1250H - Happy Birthday
We are given a collection of digit candles, where each digit from 0 to 9 appears a certain number of times. Each candle can be reused infinitely, so the counts do not deplete when we form numbers.
CF 1250F - Data Center
We are given a target area $n$, and we want to build a rectangle whose sides are integers and whose area is exactly $n$. Every valid rectangle corresponds to choosing two integers $a$ and $b$ such that $a cdot b = n$.
CF 1250A - Berstagram
We are simulating a social media feed where posts continuously swap positions based on incoming likes. Initially, posts are arranged in a fixed vertical order from top to bottom, with post 1 at the top and post n at the bottom.
CF 1250J - The Parade
We are asked to arrange soldiers of various heights into a parade formation with exactly $k$ rows. Each row must have the same number of soldiers, and within a row, no two soldiers can differ in height by more than one.