Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2)
8 problems from Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2) (contest 1556), difficulty 800-3300. 3/8 solutions verified against sample I/O.
Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2)
Div. 1+2 | 8 problems | 3/8 verified | Difficulty 800-3300 | 41m 34s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | A Variety of Operations | 800 | math | 18,543 | 3m 43s | ✓ |
| B | Take Your Places! | 1300 | implementation | 13,275 | 2m 51s | ✓ |
| C | Compressed Bracket Sequence | 1800 | brute-force, implementation | 6,215 | 4m 31s | |
| D | Take a Guess | 1800 | bitmasks, constructive-algorithms, interactive | 8,584 | 9m 7s | |
| E | Equilibrium | 2200 | data-structures, dp, greedy | 2,989 | 6m 29s | |
| F | Sports Betting | 2500 | bitmasks, combinatorics, dp | 1,420 | 5m 15s | ✓ |
| G | Gates to Another World | 3300 | bitmasks, data-structures, dsu | 446 | 4m 44s | |
| H | DIY Tree | 3300 | graphs, greedy, math | 446 | 4m 54s |
CF 1556H - DIY Tree
We are given a complete weighted undirected graph on $n$ vertices, so every pair of vertices is connected and every edge has a known cost.
CF 1556G - Gates to Another World
We are working on a graph whose vertices are all integers from $0$ to $2^n - 1$. Each vertex represents an $n$-bit binary string, and there is an undirected edge between two vertices if their binary representations differ in exactly one bit.
CF 1556D - Take a Guess
We are given a hidden array of integers, and we cannot access its elements directly. The only way to learn anything about the array is by asking queries on pairs of indices. Each query returns either the bitwise AND or bitwise OR of two elements.
CF 1556E - Equilibrium
We are given two arrays of the same length and a set of queries, each query picking a contiguous segment. Inside a segment, we are allowed to perform a special operation multiple times. Each operation selects an even number of distinct positions inside the segment.
CF 1556F - Sports Betting
We are given a complete tournament where every pair of teams plays exactly one match. The result of each match is random, but biased: team $i$ beats team $j$ with probability proportional to its strength, specifically $frac{ai}{ai + aj}$. Each match outcome is independent.
CF 1556C - Compressed Bracket Sequence
We are given a bracket string, but it is not written explicitly character by character. Instead, it is compressed into blocks.
CF 1556A - A Variety of Operations
We start with two integers, both initialized to zero. We are allowed to repeatedly apply operations that modify them using a freely chosen positive step size each time.
CF 1556B - Take Your Places!
We are given an array of integers, and we are allowed to swap adjacent elements. The goal is to rearrange the array so that no two neighboring elements share the same parity, meaning we want an alternating pattern of even and odd numbers.