Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022
7 problems from Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022 (contest 1726), difficulty 900-3500. 1/7 solutions verified against sample I/O.
Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022
Div. 1+2 | 7 problems | 1/7 verified | Difficulty 900-3500 | 38m 29s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Mainak and Array | 900 | greedy, math | 36,505 | 4m 32s | ✓ |
| B | Mainak and Interesting Sequence | 1100 | bitmasks, constructive-algorithms, math | 16,838 | 4m 46s | |
| C | Jatayu's Balanced Bracket Sequence | 1300 | data-structures, dsu, graphs | 13,398 | 7m 30s | |
| D | Edge Split | 2000 | brute-force, constructive-algorithms, dfs-and-similar | 4,160 | 3m 56s | |
| E | Almost Perfect | 2400 | combinatorics, fft, math | 1,716 | 4m 48s | |
| G | A Certain Magical Party | 3300 | combinatorics, data-structures, greedy | 365 | 5m 44s | |
| H | Mainak and the Bleeding Polygon | 3500 | binary-search, geometry, implementation | 106 | 7m 13s |
CF 1726H - Mainak and the Bleeding Polygon
We are given a convex polygon described by its vertices in counter-clockwise order. The shape is not arbitrary: every corner is either a right angle or slightly wider than a right angle, but never sharp.
CF 1726G - A Certain Magical Party
We are given a group of $n$ people, each starting with a happiness value $ai$ and a binary personality flag $bi$. We choose a permutation, which represents the order in which they speak.
CF 1726E - Almost Perfect
We are asked to count how many permutations of size $n$ satisfy a very specific structural constraint involving both the permutation and its inverse.
CF 1726D - Edge Split
We are given a connected undirected graph with a small number of extra edges beyond a tree. For each edge, we must decide whether it is colored red or blue.
CF 1726C - Jatayu's Balanced Bracket Sequence
We are given a balanced bracket string of length $2n$. Each position in this string is treated as a vertex in a graph. Two vertices $i$ and $j$ are connected by an undirected edge exactly when the substring from $i$ to $j$ forms a balanced bracket sequence on its own.
CF 1726B - Mainak and Interesting Sequence
We are asked to construct a sequence of positive integers of length $n$ whose sum is fixed to $m$, but with an additional constraint that comes from a peculiar XOR condition applied to value ordering rather than positions.
CF 1726A - Mainak and Array
We are given an array of positive integers. Exactly once, we are allowed to choose a contiguous segment and rotate it cyclically by any amount, which effectively means we can pick any element inside the segment and move it to either end of that segment, while preserving the…