Codeforces Round 740 (Div. 1, based on VK Cup 2021 - Final (Engine))
6 problems from Codeforces Round 740 (Div. 1, based on VK Cup 2021 - Final (Engine)) (contest 1558), difficulty 1300-3300. 1/6 solutions verified against sample I/O.
Codeforces Round 740 (Div. 1, based on VK Cup 2021 - Final (Engine))
Div. 1 | 6 problems | 1/6 verified | Difficulty 1300-3300 | 24m 56s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Charmed by the Game | 1300 | brute-force, math | 11,495 | 5m 8s | |
| B | Up the Strip | 1900 | brute-force, dp, math | 5,269 | 6m 35s | ✓ |
| C | Bottom-Tier Reversals | 2000 | constructive-algorithms, greedy | 3,714 | 4m 30s | |
| D | Top-Notch Insertions | 2600 | combinatorics, data-structures | 1,133 | 1m 48s | |
| E | Down Below | 3000 | binary-search, dfs-and-similar, graphs | 702 | 1m 49s | |
| F | Strange Sort | 3300 | data-structures, sortings | 511 | 5m 6s |
CF 1558E - Down Below
We are given a graph of caves connected by tunnels, and a hero who starts at cave 1 with some initial power. Every other cave initially contains a monster. The hero’s task is to visit and defeat the monster in every cave at least once.
CF 1558D - Top-Notch Insertions
We are looking at a process that behaves like insertion sort, but instead of only caring about the final sorted array, we care about the exact sequence of “real insertions” it performs while sorting.
CF 1558F - Strange Sort
We are given a permutation that is repeatedly processed by a very specific “two-phase bubble-like” routine. In each iteration, we do not scan all adjacent pairs; instead we alternate between touching only odd edges and only even edges.
CF 1558A - Charmed by the Game
We are given only the final match statistics of a tennis game: Alice has won a individual games and Borys has won b individual games. We do not know the order of these games, and we also do not know who served first. What we do know is that service alternates strictly every game.
CF 1558C - Bottom-Tier Reversals
We are given a permutation of length $n$, where $n$ is always odd. The only operation allowed is to take a prefix of odd length and reverse it. Each operation affects only the first $p$ elements, flipping their order, while the rest of the array remains untouched.
CF 1558B - Up the Strip
We are given a token placed at position $n$ on a vertical line of cells labeled from $1$ at the top to $n$ at the bottom. The goal is to count how many distinct sequences of moves can bring the token from $n$ down to $1$. From a position $x 1$, two types of moves are allowed.