2019 Summer Petrozavodsk Camp, Day 2: 300iq Contest 2 (XX Open Cup, Grand Prix of Kazan)
11 problems from 2019 Summer Petrozavodsk Camp, Day 2: 300iq Contest 2 (XX Open Cup, Grand Prix of Kazan) (contest 102331), difficulty -. 11/11 solutions verified against sample I/O.
2019 Summer Petrozavodsk Camp, Day 2: 300iq Contest 2 (XX Open Cup, Grand Prix of Kazan)
Special | 11 problems | 11/11 verified | Difficulty - | 44m 52s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Apollonian Network | 3m 39s | ✓ | |||
| B | Bitwise Xor | 6m 7s | ✓ | |||
| C | Counting Cactus | 2m 54s | ✓ | |||
| D | Determinant | 3m 8s | ✓ | |||
| E | Easy Win | 3m 46s | ✓ | |||
| F | Fast Spanning Tree | 4m 36s | ✓ | |||
| G | Grammarly | 2m 51s | ✓ | |||
| H | Honorable Mention | 2m 59s | ✓ | |||
| I | Interactive Vertex | 3m | ✓ | |||
| J | Jiry Matchings | 7m 30s | ✓ | |||
| K | K-pop Strings | 4m 22s | ✓ |
CF 102331C - Counting Cactus
We have a simple undirected graph on at most 13 vertices. We choose a subset of its edges, while keeping the whole vertex set, and ask whether the resulting spanning graph is a cactus. A cactus is connected, and no edge may belong to two different simple cycles.
CF 102331F - Fast Spanning Tree
We have a weighted set of vertices and a list of indexed edges. Initially there are no graph edges, so every vertex is its own connected component.
CF 102331G - Grammarly
The graph has one vertex for every distinct non-empty substring of the input string s. From a substring t of length L, an edge goes to every distinct substring of t of length L-1.
CF 102331B - Bitwise Xor
We have an array of up to (300000) integers, each using at most 60 bits, and a threshold (x). A subsequence is considered good when every pair of selected array elements has XOR at least (x).
CF 102331K - K-pop Strings
We need to count strings of length (n) over an alphabet of 35 characters, namely the digits 1 through 9 and the lowercase letters. A string is valid if it contains no tandem repeat whose length is at least (n-k).
CF 102331J - Jiry Matchings
We have a weighted tree with (n) vertices. A matching is a set of edges such that no two selected edges share an endpoint. For every (k=1,2,ldots,n-1), we need the maximum possible sum of edge weights among all matchings containing exactly (k) edges.
CF 102331I - Interactive Vertex
We are given a tree with up to (200,000) vertices. Somewhere in this tree there is one hidden special vertex (u). We know the entire tree, but not (u), and we must discover it through interactive queries. A query chooses a vertex (x) and a set of vertices (V).
CF 102331H - Honorable Mention
For each query ((l,r,k)), we look only at the subarray (al,ldots,ar). We must choose exactly (k) nonempty pairwise disjoint contiguous pieces of that subarray and maximize the sum of all elements covered by those pieces. The pieces may be adjacent.
CF 102331E - Easy Win
For every inserted edge, we know its two endpoints, the number of stones on it, and a positive value representing how much we earn if that edge is included in our chosen graph.
CF 102331D - Determinant
We have a connected undirected graph and need the determinant of its adjacency matrix modulo (998244353). The graph has up to (25,000) vertices and (500,000) edges, but the unusual condition involving (k+1) vertices is the real structural constraint.
CF 102331A - Apollonian Network
The graph starts as a triangle and is repeatedly expanded by choosing a triangular face, inserting a new vertex into it, and connecting the new vertex to all three vertices of that triangle.