2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules)
Solutions for 2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules) (contest 1468). 8/14 problems verified against sample I/O. Difficulty range: 800-2900.
2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules)
Type: ICPC/IOI | Problems: 14 | Verified: 8/14 | Rating range: 800-2900 | Time: 44m 52s
| Problem | Name | Rating | Tags | Solve Time | Verified |
|---|---|---|---|---|---|
| A | LaIS | 2200 | data-structures, dp, greedy | 4m 33s | ✓ |
| B | Bakery | 2900 | data-structures, dsu | 2m 17s | ✗ |
| C | Berpizza | 1400 | data-structures, implementation | 6m 7s | ✓ |
| D | Firecrackers | 1700 | binary-search, sortings | 3m 41s | ✗ |
| E | Four Segments | 800 | greedy | 2m 24s | ✓ |
| F | Full Turn | 1700 | geometry, hashing, number-theory | 2m 1s | ✓ |
| G | Hobbits | 2500 | binary-search, geometry | 2m 11s | ✗ |
| H | K and Medians | 2200 | constructive-algorithms, greedy, math | 2m 29s | ✗ |
| I | Plane Tiling | 2500 | geometry, implementation, math | 2m 45s | ✗ |
| J | Road Reform | 1800 | dsu, graphs, greedy | 9m 15s | ✓ |
| K | The Robot | 1600 | brute-force, implementation | 1m 32s | ✓ |
| L | Prime Divisors Selection | 2700 | binary-search, greedy, math | 1m 44s | ✓ |
| M | Similar Sets | 2300 | data-structures, graphs, implementation | 2m 4s | ✗ |
| N | Waste Sorting | 900 | greedy, implementation | 1m 49s | ✓ |
CF 1468J - Road Reform
The problem presents a country with n cities connected by m bidirectional roads. Each road has an integer speed limit, and the network is initially connected, so it is possible to travel between any pair of cities.
CF 1468N - Waste Sorting
Monocarp needs to throw away several items of different types into three containers with fixed capacities. The first container accepts only paper items, the second only plastic, and the third all other types.
CF 1468M - Similar Sets
We are given multiple collections of integers, each collection considered a set. Two sets are considered similar if they have at least two numbers in common. The goal is to find any pair of similar sets or report that none exists.
CF 1468L - Prime Divisors Selection
We are given a set of up to 1000 distinct large integers, and we must pick exactly k of them. After picking, each chosen number must be assigned a prime divisor, one prime per number. The assignment is considered valid if every chosen number is divisible by its assigned prime.
CF 1468K - The Robot
We have a robot moving on an infinite 2D grid, starting at the origin (0, 0). It receives a sequence of movement commands: 'L' for left, 'R' for right, 'U' for up, and 'D' for down.
CF 1468I - Plane Tiling
We are asked to construct a set of $n$ integer points $(xi, yi)$ such that every integer point $(x, y)$ in the plane can be written in exactly one way using one of these chosen points plus an integer combination of two fixed direction vectors.
CF 1468H - K and Medians
We are given a sequence of integers from 1 to n and an odd integer k. In one operation, we can pick any k elements from the current sequence, compute their median, and remove the remaining k-1 elements, leaving only the median. We repeat this operation any number of times.
CF 1468G - Hobbits
Working
CF 1468F - Full Turn
We have a set of points on a plane, each representing a person, with each person initially looking at another point. Everyone rotates clockwise continuously, completing a full turn, and we are asked to count the number of distinct pairs of people who ever make “eye contact.
CF 1468E - Four Segments
We are given four segment lengths and we want to use them as the sides of a shape made only from horizontal and vertical segments.
CF 1468C - Berpizza
We process a sequence of events in a pizzeria. Every time a query of type 1 m appears, a new customer arrives. Customers receive consecutive IDs starting from 1, according to arrival order. Each customer also has a predicted spending value m.
CF 1468D - Firecrackers
A hooligan and a guard stand in a one dimensional corridor. Every second, the hooligan acts first, then already dropped firecrackers may explode, then the guard moves one step toward the hooligan. The hooligan owns several firecrackers.
CF 1468A - LaIS
We are asked to find the length of the longest subsequence of an array such that the sequence is "almost increasing." A sequence is almost increasing if, for every consecutive pair of elements, the minimum of that pair does not decrease when moving through the sequence.
CF 1468B - Bakery
We are asked to compute a measure of stale bread at a bakery over multiple days. Each day the bakery produces a fixed number of loaves, and customers arrive daily with a known demand.