Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round)
8 problems from Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round) (contest 1654), difficulty 800-3500. 5/8 solutions verified against sample I/O.
Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round)
Div. 1+2 | 8 problems | 5/8 verified | Difficulty 800-3500 | 31m 16s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Maximum Cake Tastiness | 800 | brute-force, greedy, implementation | 19,390 | 1m 21s | ✓ |
| B | Prefix Removals | 800 | strings | 16,778 | 3m 8s | |
| C | Alice and the Cake | 1400 | data-structures, greedy, implementation | 14,525 | 1m 57s | ✓ |
| D | Potion Brewing Class | 2100 | dfs-and-similar, math, number-theory | 3,062 | 9m 14s | ✓ |
| E | Arithmetic Operations | 2300 | brute-force, data-structures, graphs | 2,359 | 2m 40s | ✓ |
| F | Minimal String Xoration | 2800 | bitmasks, data-structures, divide-and-conquer | 1,483 | 2m 42s | ✓ |
| G | Snowy Mountain | 2900 | data-structures, dfs-and-similar, graphs | 457 | 4m 24s | |
| H | Three Minimums | 3500 | combinatorics, constructive-algorithms, divide-and-conquer | 100 | 5m 50s |
CF 1654D - Potion Brewing Class
We are given a set of ingredients, each of which must appear in some positive integer quantity in a final mixture. The professor does not provide absolute amounts, but instead gives exactly $n-1$ constraints.
CF 1654H - Three Minimums
We are asked to count permutations of the numbers from 1 to n that satisfy two independent kinds of restrictions. The first restriction is positional and local. We are given a short comparison string s of length m.
CF 1654G - Snowy Mountain
We are given a tree where some vertices are marked as “base lodges”. Every vertex inherits a height equal to its distance from the nearest lodge.
CF 1654B - Prefix Removals
We are repeatedly trimming a string from the front based on a self-referential property of its prefixes. At any moment, we look at the current string and examine all its prefixes starting from the empty one.
CF 1654F - Minimal String Xoration
We are given a string whose length is a power of two, indexed from 0 to $2^n - 1$. The key operation allowed is a global reindexing of the string using bitwise XOR with a fixed mask $j$.
CF 1654E - Arithmetic Operations
We want to change as few array elements as possible so that the final array becomes an arithmetic progression. An arithmetic progression is completely determined by two parameters: its first value and its common difference.
CF 1654C - Alice and the Cake
We are given the final weights of n cake pieces. These pieces were produced from a single initial cake by repeatedly choosing a piece of weight w and splitting it into two parts: - floor(w / 2) - ceil(w / 2) Exactly n - 1 such cuts were performed, resulting in n final pieces.
CF 1654A - Maximum Cake Tastiness
We are given a line of $n$ cakes, each with a weight $ai$. The tastiness of the cake is defined as the sum of two adjacent pieces. We are allowed to reverse one contiguous subsegment of cakes at most once and then measure the tastiness.