Good Bye 2018

Solutions for Good Bye 2018 (contest 1091). 5/8 problems verified against sample I/O. Difficulty range: 800-3200.

8 items

Good Bye 2018

Type: Special | Problems: 8 | Verified: 5/8 | Rating range: 800-3200 | Time: 37m 43s

Problem	Name	Rating	Tags	Solve Time	Verified
A	New Year and the Christmas Ornament	800	brute-force, implementation, math	7m 48s	✓
B	New Year and the Treasure Geolocation	1200	brute-force, constructive-algorithms, greedy	1m 18s	✓
C	New Year and the Sphere Transmission	1400	math, number-theory	3m 42s	✓
D	New Year and the Permutation Concatenation	1700	combinatorics, dp, math	3m 36s	✗
E	New Year and the Acquaintance Estimation	2400	binary-search, data-structures, graphs	4m 22s	✗
F	New Year and the Mallard Expedition	2600	constructive-algorithms, greedy	1m 32s	✓
G	New Year and the Factorisation Collaboration	3200	interactive, math, number-theory	5m 45s	✗
H	New Year and the Tricolore Recreation	3200	games	9m 40s	✓

Practice › Codeforces Solutions › Good Bye 2018 ›

CF 1091H - New Year and the Tricolore Recreation

Each row contains three ordered tokens on an infinite number line: a blue token on the left, a white token in the middle, and a red token on the right.

Practice › Codeforces Solutions › Good Bye 2018 ›

CF 1091G - New Year and the Factorisation Collaboration

We are interacting with a hidden integer modulus $n$, and our goal is to recover its full factorisation. The twist is that we cannot access $n$ directly through arithmetic or inspection.

Practice › Codeforces Solutions › Good Bye 2018 ›

CF 1091E - New Year and the Acquaintance Estimation

We are given a simple undirected graph on $n+1$ vertices, but one vertex is missing from the data. Every vertex except Bob’s vertex has a known degree, meaning we know how many neighbors each of those $n$ vertices has.

Practice › Codeforces Solutions › Good Bye 2018 ›

CF 1091A - New Year and the Christmas Ornament

We are given three piles of ornaments: yellow, blue, and red. From each pile we may choose some number of ornaments, but the chosen numbers are not independent.

Practice › Codeforces Solutions › Good Bye 2018 ›

CF 1091C - New Year and the Sphere Transmission

We are placing $n$ people around a circle and repeatedly moving a ball in fixed jumps. Starting from person $1$, we choose a step size $k$. Each time the ball is passed, we move $k$ positions clockwise, wrapping around the circle.

Practice › Codeforces Solutions › Good Bye 2018 ›

CF 1091D - New Year and the Permutation Concatenation

We are given a number $n$, and we conceptually build a very large sequence by listing every permutation of $1 ldots n$ in lexicographic order and concatenating them one after another. Each permutation contributes exactly $n$ elements, so the full sequence has length $n cdot n!$.

Practice › Codeforces Solutions › Good Bye 2018 ›

CF 1091F - New Year and the Mallard Expedition

We are given a long one-dimensional route made of consecutive segments. Each segment has a length and a terrain type, either grass, water, or lava. Bob starts just before the first segment and wants to reach the far end after the last segment.

Practice › Codeforces Solutions › Good Bye 2018 ›

CF 1091B - New Year and the Treasure Geolocation

We are given a set of obelisks on a 2D plane and a set of clues that indicate vectors from obelisks to a hidden treasure. Each obelisk has exactly one clue, but the mapping is scrambled, so we do not know which clue belongs to which obelisk.