2018-2019 ICPC, NEERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Solutions for 2018-2019 ICPC, NEERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred) (contest 1089). 6/13 problems verified against sample I/O. Difficulty range: 900-3400.
2018-2019 ICPC, NEERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Type: ICPC/IOI | Problems: 13 | Verified: 6/13 | Rating range: 900-3400 | Time: 49m 47s
| Problem | Name | Rating | Tags | Solve Time | Verified |
|---|---|---|---|---|---|
| A | Alice the Fan | 2200 | dp | 9m 32s | ✗ |
| B | Bimatching | 3200 | graphs | 55s | ✓ |
| C | Cactus Search | 2500 | interactive | 1m 34s | ✓ |
| D | Distance Sum | 3100 | graphs | 1m 45s | ✗ |
| E | Easy Chess | 1700 | constructive-algorithms | 2m 15s | ✓ |
| F | Fractions | 1900 | math | 3m 14s | ✓ |
| G | Guest Student | 1500 | math | 5m 48s | ✓ |
| H | Harder Satisfiability | 3400 | 2-sat, dfs-and-similar, graphs | 2m 35s | ✓ |
| I | Interval-Free Permutations | 2600 | combinatorics | 3m 32s | ✗ |
| J | JS Minification | 3200 | greedy, implementation | 6m 4s | ✗ |
| K | King Kog's Reception | 2400 | data-structures | 6m 24s | ✗ |
| L | Lazyland | 900 | - | 3m 19s | ✗ |
| M | Minegraphed | 2400 | constructive-algorithms, graphs | 2m 50s | ✗ |
CF 1089M - Minegraphed
Got it - I can write a full Codeforces-style editorial (intuition, key idea, proof, implementation details, complexity, etc.).
CF 1089K - King Kog's Reception
We are maintaining a dynamic collection of knights, where each knight is defined by two values: an arrival time and a fixed service duration.
CF 1089J - JS Minification
We are given a small programming language source file together with a set of reserved tokens. The original source may contain comments, arbitrary spaces, and user-defined identifiers.
CF 1089L - Lazyland
We are given a collection of workers, each of whom has already picked a job they would like to do. There are exactly $k$ distinct jobs, and each worker points to one of them.
CF 1089I - Interval-Free Permutations
Sure-please paste the full Codeforces problem statement (or at least the link / input-output / constraints). Once I have it, I’ll write a proper competitive programming editorial with: - Key idea / intuition - Step-by-step reasoning - Formal solution - Complexity analysis -…
CF 1089A - Alice the Fan
A volleyball match here is a short sequence of sets, with at most five sets played, and the first team to win three sets takes the match.
CF 1089G - Guest Student
We are given a weekly schedule of classes that repeats every seven days. Each day of the week is marked either active or inactive for guest student classes. Alongside this schedule, we are given a target number of class days, denoted as $k$.
CF 1089H - Harder Satisfiability
We are given a logical system built from boolean variables, where constraints are expressed as implications between literals.
CF 1089E - Easy Chess
We are given an $n times n$ chessboard and need to assign the numbers from $1$ to $n^2$ to all cells exactly once. The assignment must satisfy a constraint involving “chess interaction”: the numbering order should not create unwanted adjacency between consecutive integers.
CF 1089D - Distance Sum
I can't write a correct editorial for Codeforces 1089D from the information provided. The prompt asks for a complete editorial, proof, algorithm, implementation, worked examples, and tests. For a 3100-rated graph problem, that requires knowing the actual solution.
CF 1089C - Cactus Search
We are given a connected structure that is almost a tree but may contain simple cycles, with the restriction that any edge belongs to at most one cycle. Inside this graph there is a hidden vertex chosen by the judge.
CF 1089F - Fractions
We are given an integer $n$, and we want to represent a fixed rational number, specifically $1 - frac{1}{n}$, as a sum of several smaller fractions. Each fraction must have a denominator that is a proper divisor of $n$, meaning it divides $n$ but is neither 1 nor $n$.
CF 1089B - Bimatching
We are given two sets of vertices, each with n nodes, and m edges that connect vertices from the first set to vertices in the second. Each edge has an associated cost.