Good Bye 2020

Solutions for Good Bye 2020 (contest 1466). 7/9 problems verified against sample I/O. Difficulty range: 800-3400.

9 items

Good Bye 2020

Type: Special | Problems: 9 | Verified: 7/9 | Rating range: 800-3400 | Time: 27m 35s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Bovine Dilemma	800	brute-force, geometry, math	1m 38s	✓
B	Last minute enhancements	800	dp, greedy	4m 57s	✓
C	Canine poetry	1300	dp, greedy, strings	2m 11s	✓
D	13th Labour of Heracles	1500	data-structures, greedy, sortings	2m 27s	✓
E	Apollo versus Pan	1800	bitmasks, brute-force, math	1m 14s	✓
F	Euclid's nightmare	2100	bitmasks, dfs-and-similar, dsu	1m 53s	✓
G	Song of the Sirens	2600	combinatorics, divide-and-conquer, hashing	2m 56s	✗
H	Finding satisfactory solutions	3300	combinatorics, dp, graphs	8m 20s	✓
I	The Riddle of the Sphinx	3400	binary-search, data-structures, interactive	1m 59s	✗

Practice › Codeforces Solutions › Good Bye 2020 ›

Practice › Codeforces Solutions › Good Bye 2020 ›

CF 1466H - Finding satisfactory solutions

We are given n agents and a permutation of n items representing an optimal assignment, where agent i receives item A[i]. Each agent initially owns a unique item corresponding to their index. A preference profile assigns a ranking of all items for each agent.

Practice › Codeforces Solutions › Good Bye 2020 ›

CF 1466I - The Riddle of the Sphinx

We are given a hidden array of length n. Each element is an integer in the range [0, 2^b - 1]. We never see the values directly. Instead, we can repeatedly choose an index i and a number y, and ask whether a[i] y.

Practice › Codeforces Solutions › Good Bye 2020 ›

CF 1466G - Song of the Sirens

We start with a short string $s0$. Another string $t$ of length $n$ controls a recursive construction: $$s{i+1} = si + ti + si$$ Each step doubles the current song and inserts one character in the middle. Queries ask for a level $k$ and a pattern $w$.

Practice › Codeforces Solutions › Good Bye 2020 ›

CF 1466F - Euclid's nightmare

We are given a collection of binary vectors of length $m$, where each vector contains at most two positions set to 1. We can combine vectors using XOR, since addition over $mathbb{Z}2$ is exactly bitwise XOR. From all possible XORs of subsets of these vectors, we form a set $T$.

Practice › Codeforces Solutions › Good Bye 2020 ›

CF 1466B - Last minute enhancements

The task asks us to maximize the diversity of a song, where the song is represented as a sequence of positive integers (notes). The diversity is simply the number of distinct notes in the sequence.

Practice › Codeforces Solutions › Good Bye 2020 ›

CF 1466D - 13th Labour of Heracles

We are given a tree whose vertices carry weights. For every value of $k$ from $1$ to $n-1$, we may assign one of $k$ colors to each edge. Edges with the same color form a subgraph.

Practice › Codeforces Solutions › Good Bye 2020 ›

CF 1466C - Canine poetry

We are given a sequence of lowercase letters representing a poem. Cerberus dislikes any palindromic sequence of length two or more. Our task is to determine the minimal number of letter changes needed so that the poem contains no palindromes longer than one character.

Practice › Codeforces Solutions › Good Bye 2020 ›

CF 1466A - Bovine Dilemma

We are asked to count the number of distinct areas of triangular pastures that can be formed using trees as vertices. One tree is fixed at point (0,1) above the x-axis. The remaining trees are positioned along the river, which we model as the x-axis, at coordinates $(xi, 0)$.