Codeforces Round 504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)
7 problems from Codeforces Round 504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) (contest 1023), difficulty 1000-3400. 4/7 solutions verified against sample I/O.
Codeforces Round 504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)
Div. 1+2 | 7 problems | 4/7 verified | Difficulty 1000-3400 | 16m 18s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Single Wildcard Pattern Matching | 1200 | brute-force, implementation, strings | 9,263 | 1m 56s | ✓ |
| B | Pair of Toys | 1000 | math | 11,663 | 1m 52s | ✓ |
| C | Bracket Subsequence | 1200 | greedy | 10,753 | 1m 53s | ✓ |
| D | Array Restoration | 1700 | constructive-algorithms, data-structures | 4,282 | 2m 36s | |
| E | Down or Right | 2100 | constructive-algorithms, interactive, matrices | 2,220 | 2m 14s | |
| F | Mobile Phone Network | 2600 | dfs-and-similar, dsu, graphs | 1,009 | 2m 53s | |
| G | Pisces | 3400 | data-structures, flows, trees | 188 | 2m 54s | ✓ |
CF 1023G - Pisces
We are given a weighted tree where each edge represents a river with a travel time. Fish can move continuously along these edges: traversing an edge of length $l$ takes exactly $l$ days, and fish may also wait arbitrarily at vertices.
CF 1023F - Mobile Phone Network
We are given a connected graph with two types of edges. One set is already fixed by a competitor, each with a known cost. The second set is ours: these edges form a forest, and we are allowed to assign any integer weights to them.
CF 1023D - Array Restoration
We are given a final array of length n that was produced by repeatedly painting segments with increasing labels from 1 to q. During the i-th operation, a chosen segment is overwritten entirely with value i, and later operations can overwrite earlier ones.
CF 1023E - Down or Right
We are given an unknown $n times n$ grid where each cell is either open or blocked. Movement is only allowed from a cell to its right neighbor or its bottom neighbor, and only if the destination cell is open.
CF 1023A - Single Wildcard Pattern Matching
We are given a pattern string s and a target string t. The pattern looks almost like a normal string of lowercase letters, except that it may contain a single special character .
CF 1023C - Bracket Subsequence
We are given a correctly balanced bracket sequence, meaning every prefix of the string never has more closing brackets than opening ones, and in total the counts match perfectly.
CF 1023B - Pair of Toys
We are given a range of toy prices that is completely regular: there are toys priced from 1 up to n, each integer price appearing exactly once. We want to count how many distinct unordered pairs of different toys have a combined price exactly equal to k.