2021 Summer Petrozavodsk Camp, Day 3: IQ test (XXII Open Cup, Grand Prix of IMO)
13 problems from 2021 Summer Petrozavodsk Camp, Day 3: IQ test (XXII Open Cup, Grand Prix of IMO) (contest 103469), difficulty -. 10/13 solutions verified against sample I/O.
2021 Summer Petrozavodsk Camp, Day 3: IQ test (XXII Open Cup, Grand Prix of IMO)
Special | 13 problems | 10/13 verified | Difficulty - | 10m 15s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | AND | 46s | ✓ | |||
| B | Bruteforce | 1m 2s | ✓ | |||
| C | Crab's Cannon | 50s | ✓ | |||
| D | Deleting | 48s | ✓ | |||
| E | Eulerian? | 1m 1s | ✓ | |||
| F | Fancy Formulas | 54s | ✓ | |||
| G | Glory Graph | 52s | ✓ | |||
| H | Hamiltonian | 29s | ||||
| I | Intellectual Implementation | 52s | ✓ | |||
| J | Joke | 32s | ||||
| K | K-onstruction | 46s | ✓ | |||
| L | Little LCS | 1m | ✓ | |||
| M | Math | 23s |
CF 103469L - Little LCS
We are given two strings, each of length $2n+1$, over the alphabet ${A,B,C}$ plus wildcard characters ?. Each ? can be replaced independently by any of the three letters.
CF 103469M - Math
Codeforces 103469M: Math
CF 103469K - K-onstruction
We are asked to construct a short integer array such that the number of its subsets whose sum is exactly zero equals a given value K.
CF 103469J - Joke
We are given a fixed permutation $p$ of size $n$, and a partially specified permutation $q$ of the same size. Some positions in $q$ are known, others are zero and must be filled so that the final sequence becomes a valid permutation of $1$ to $n$.
CF 103469I - Intellectual Implementation
We are given a collection of axis-aligned rectangles in the plane. Each rectangle is defined by a closed x-interval and a closed y-interval, so it represents a solid filled region.
CF 103469G - Glory Graph
We are given a complete graph where every pair of vertices is connected by an edge colored either blue or yellow. The input is essentially an $n times n$ symmetric matrix encoded as characters, where each off-diagonal entry tells us the color of an edge.
CF 103469H - Hamiltonian
Codeforces 103469H: Hamiltonian
CF 103469F - Fancy Formulas
We are given a pair of values $(a, b)$ over a finite field modulo a prime $p$. Each query asks for the minimum number of operations needed to transform a starting pair $(ai, bi)$ into a target pair $(ci, di)$, where each operation applies one of two deterministic transformations.
CF 103469E - Eulerian?
We are given a hidden simple undirected connected graph on $n$ vertices. We cannot see its edges directly. Instead, we can query any subset of vertices and receive the number of edges whose both endpoints lie entirely inside that subset. The task is not to reconstruct the graph.
CF 103469D - Deleting
We start with a sequence of labels from 1 to n, arranged in increasing order. The only allowed operation is to pick two adjacent elements in the current sequence, remove them both, and pay a cost that depends on the original labels of the two removed elements.
CF 103469B - Bruteforce
We are given an array of integers that changes over time through point updates. After every update, we need to compute a special “weight” of the array. To compute this weight, we first sort the array in non-decreasing order.
CF 103469C - Crab's Cannon
We are given a target string length l and a set of distinct positions a1, a2, ..., an, each in the range [1, l]. These positions are known to be exactly the palindromic prefix lengths of some unknown string, except that some of them may have been deleted.
CF 103469A - AND
We are given a set of integers that is known to come from some hidden array. The process that produced this set is as follows: take every contiguous subarray of the hidden array, compute the bitwise AND of that subarray, and collect all distinct results.