Bubble Cup 14 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred, Div. 1)
Solutions for Bubble Cup 14 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred, Div. 1) (contest 1599). 1/10 problems verified against sample I/O. Difficulty range: 2000-3200.
Bubble Cup 14 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred, Div. 1)
Type: Div. 1 | Problems: 10 | Verified: 1/10 | Rating range: 2000-3200 | Time: 24m 39s
| Problem | Name | Rating | Tags | Solve Time | Verified |
|---|---|---|---|---|---|
| A | Weights | 2600 | constructive-algorithms, greedy, two-pointers | 8m 19s | ✗ |
| B | Restaurant Game | 3100 | - | 1m 38s | ✗ |
| C | Bubble Strike | 2000 | combinatorics, math, probabilities | 1m 44s | ✗ |
| D | Bubble Popping | 3200 | - | 40s | ✗ |
| E | Two Arrays | 3200 | data-structures, matrices | 2m 32s | ✗ |
| F | Mars | 2700 | hashing | 2m 23s | ✗ |
| G | Shortest path | 2700 | brute-force, geometry, math | 2m 25s | ✗ |
| H | Hidden Fortress | 2100 | interactive, math | 1m 46s | ✗ |
| I | Desert | 2700 | data-structures, graphs | 1m 35s | ✗ |
| J | Bob's Beautiful Array | 2600 | bitmasks, brute-force, greedy | 1m 37s | ✓ |
CF 1599J - Bob's Beautiful Array
We are given an array $B$ that is claimed to be the result of a strange process applied to some unknown original array $A$.
CF 1599A - Weights
The previous solution collected all indices where a[i] != sorted(a)[i]. That works in many cases, but fails when: 1. The array has repeated elements. 2. Sorting would reorder elements without changing their relative positions (stable sort).
CF 1599I - Desert
We are given a graph with a fixed set of vertices and a sequence of edges ordered from 1 to M. The task is not about the full graph at once, but about all contiguous edge segments in this sequence.
CF 1599H - Hidden Fortress
We are working on a huge integer grid, and somewhere inside it lies a hidden axis-aligned rectangle. We are not allowed to enter this rectangle directly.
CF 1599G - Shortest path
We are given a set of points on a plane. All but one of these points lie perfectly on a single line, and one point is off that line. You start at a specified point and need to visit every point at least once, moving along straight lines.
CF 1599F - Mars
We are given a list of city positions on a circular Martian colony where cities are numbered modulo $10^9+7$. Each query asks whether it is possible to connect all cities in a given subarray using roads of a fixed length $D$.
CF 1599E - Two Arrays
We are given two arrays, A1 and A2, each with N integers, and a sequence of Q queries that modify these arrays or ask for a sum over a Fibonacci transformation of their element-wise sums.
CF 1599D - Bubble Popping
Codeforces 1599D: Bubble Popping
CF 1599C - Bubble Strike
We are asked to determine how many maps Johnny must study to ensure that the probability he ends up playing on a studied map is at least $P$. The game process is as follows: from $N$ total maps, three are randomly presented, and each player discards one map.
CF 1599B - Restaurant Game
I’m sorry, but I can’t reliably reconstruct a complete correct editorial and accepted implementation for this 3100-rated problem from the problem statement alone.