2021-2022 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Solutions for 2021-2022 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) (contest 1666). 4/12 problems verified against sample I/O. Difficulty range: 900-3500.
2021-2022 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Type: ICPC/IOI | Problems: 12 | Verified: 4/12 | Rating range: 900-3500 | Time: 30m 21s
| Problem | Name | Rating | Tags | Solve Time | Verified |
|---|---|---|---|---|---|
| A | Admissible Map | 3300 | - | 1m 53s | ✓ |
| B | Budget Distribution | 3300 | - | 1m 54s | ✗ |
| C | Connect the Points | 1800 | brute-force, constructive-algorithms, geometry | 12m 3s | ✗ |
| D | Deletive Editing | 900 | greedy | 1m 44s | ✗ |
| E | Even Split | 2500 | binary-search, constructive-algorithms, greedy | 1m 53s | ✗ |
| F | Fancy Stack | 2200 | combinatorics, dp, implementation | 1m 3s | ✓ |
| G | Global Warming | 3100 | geometry, math | 1m 4s | ✓ |
| H | Heroes of Might | 3500 | math | 47s | ✓ |
| I | Interactive Treasure Hunt | 2200 | brute-force, constructive-algorithms, geometry | 1m 47s | ✗ |
| J | Job Lookup | 2100 | constructive-algorithms, dp, shortest-paths | 1m 46s | ✗ |
| K | Kingdom Partition | 3200 | flows | 2m 8s | ✗ |
| L | Labyrinth | 1800 | dfs-and-similar, graphs | 2m 19s | ✗ |
CF 1666C - Connect the Points
We are given three distinct points on the 2D plane, and we are asked to connect them with segments that are either horizontal or vertical. The segments can only lie along the coordinate axes, meaning each segment has constant x or constant y.
CF 1666L - Labyrinth
We are given a directed graph representing a labyrinth of halls and one-way passages. A traveler starts from a fixed starting hall $s$. We are allowed to choose any other hall $t$ as a meeting point.
CF 1666K - Kingdom Partition
We are asked to partition a kingdom's towns into three districts, A, B, and C, corresponding to Adrian, Beatrice, and Cecilia. Adrian's castle must be in district A, Beatrice's castle in district B, and Cecilia has no castle.
CF 1666J - Job Lookup
We are asked to organize a team of n members into a binary search tree (BST) hierarchy that minimizes communication cost. Each team member has a unique number from 1 to n representing their position in a front-end to back-end spectrum.
CF 1666I - Interactive Treasure Hunt
We are given a grid of size $n times m$ where two treasures are hidden in distinct cells. The goal is to locate both treasures using a combination of two operations: DIG r c and SCAN r c.
CF 1666H - Heroes of Might
We are given a sequence of integer strengths representing heroes. Each hero can defeat monsters of strength equal to their own or weaker.
CF 1666G - Global Warming
In this problem, we are given a set of points on a two-dimensional plane, each representing a temperature measurement at a specific location.
CF 1666F - Fancy Stack
The problem gives us a sequence of integers representing operations on a stack. Each integer can be seen as either pushing a new element onto the stack or performing a "fancy" operation that removes some elements from the top in a way governed by the problem's rules.
CF 1666E - Even Split
We are given a one-dimensional segment representing the entire country, stretching from position 0 to position l. Inside this segment there are n citizens, each located at a distinct integer coordinate ai, sorted in increasing order.
CF 1666D - Deletive Editing
We are given two strings for each test case, an initial word and a target word. We repeatedly perform an operation where we are allowed to choose a character and delete its leftmost occurrence from the current word.
CF 1666B - Budget Distribution
We are asked to distribute extra budget money over several topics, each consisting of a small number of items. For each topic, the optimal relative fractions of money for its items are given, and some money is already assigned to items and cannot be removed.
CF 1666A - Admissible Map
We are given a string over four symbols, each symbol encoding a move in a grid: up, left, down, or right. Any substring of this string can be interpreted as a flattened matrix if we choose a height and width whose product equals the substring length, reading the substring row…