China Collegiate Programming Contest 2021, Qualification Round (Online), Rematch
11 problems from China Collegiate Programming Contest 2021, Qualification Round (Online), Rematch (contest 103492), difficulty -. 11/11 solutions verified against sample I/O.
China Collegiate Programming Contest 2021, Qualification Round (Online), Rematch
Special | 11 problems | 11/11 verified | Difficulty - | 8m 43s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Median Problem | 1m | ✓ | |||
| B | Kanade Doesn't Want to Learn CG | 50s | ✓ | |||
| C | GCD on Tree | 48s | ✓ | |||
| D | Primality Test | 42s | ✓ | |||
| E | Monopoly | 43s | ✓ | |||
| F | Nun Heh Heh Aaaaaaaaaaa | 48s | ✓ | |||
| H | Subpermutation | 52s | ✓ | |||
| I | Public Transport System | 46s | ✓ | |||
| J | Bigraph Extension | 42s | ✓ | |||
| K | Jumping Monkey | 47s | ✓ | |||
| L | Contest Remake | 45s | ✓ |
CF 103492K - Jumping Monkey
We are given a tree where each node has a distinct weight. From any starting node, a monkey is allowed to jump to another node if that destination node is the maximum-weight node along the unique simple path between the two nodes.
CF 103492L - Contest Remake
We are asked to construct as many distinct “cards” as possible, where each card is actually a non-empty set of positive integers. Every set has a cost constraint: the sum of all numbers inside the set must not exceed a given limit $C$.
CF 103492J - Bigraph Extension
We are given a bipartite graph with two fixed sets of vertices, each containing exactly n vertices. The vertices are already split into set A and set B, and every existing edge connects one vertex from A to one vertex from B.
CF 103492H - Subpermutation
We are given a construction called a full permutation sequence of length n, which is formed by listing every permutation of the numbers from 1 to n exactly once, in lexicographical order, and concatenating them into a single long array.
CF 103492I - Public Transport System
We are given a directed graph where each edge represents a transport route between two cities. Every route has a base cost and a discount parameter. A traveler starts from city 1 and may follow any directed path to reach other cities.
CF 103492F - Nun Heh Heh Aaaaaaaaaaa
We are given multiple strings, and for each string we must count how many subsequences form a very specific structure. A valid subsequence is constructed in two phases. First, it must contain the fixed string nunhehheh as a subsequence in order.
CF 103492E - Monopoly
We are given a circular board with n tiles, each tile contributing a fixed integer value when we step on it. Starting before the first tile, we begin at tile 1 and move deterministically to tile 2, then 3, and so on, wrapping back to 1 after n.
CF 103492D - Primality Test
We are given a positive integer x, and we construct a value using primes around it. First, we define f(x) as the smallest prime strictly greater than x, so it is the next prime after x.
CF 103492A - Median Problem
We are given a rooted tree with nodes numbered from 1 to n. Each node u must be assigned a distinct value au forming a permutation of 1 to n. In addition to these a-values, each node also has a derived value bu.
CF 103492B - Kanade Doesn't Want to Learn CG
We are given a fixed projectile path described by a downward-opening parabola $y = ax^2 + bx + c$. A ball starts far to the left and moves strictly to the right along this curve. In the plane, there are two geometric objects.
CF 103492C - GCD on Tree
We are given a tree where each node stores an integer value. The tree structure never changes, but the value at a node can be updated during the process. Alongside updates, we must answer queries that ask about all pairs of nodes in the tree.