Osijek Competitive Programming Camp, Fall 2023, Day 9: Polish Kids Contest
10 problems from Osijek Competitive Programming Camp, Fall 2023, Day 9: Polish Kids Contest (contest 106307), difficulty -. 10/10 solutions verified against sample I/O.
Osijek Competitive Programming Camp, Fall 2023, Day 9: Polish Kids Contest
Special | 10 problems | 10/10 verified | Difficulty - | 10m 18s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Flips | 1m 2s | ✓ | |||
| B | Tree permutations | 1m 8s | ✓ | |||
| C | Control Areas | 1m 18s | ✓ | |||
| D | Gray Distances | 1m 9s | ✓ | |||
| E | Production Line | 1m 1s | ✓ | |||
| F | Is this Fibonacci | 46s | ✓ | |||
| G | Queries | 1m 3s | ✓ | |||
| H | Gray Rectangles | 52s | ✓ | |||
| I | Coprime vertex cover | 56s | ✓ | |||
| J | Modular Transform | 1m 3s | ✓ |
CF 106307H - Gray Rectangles
The construction starts from a classic Gray code sequence. For each level $n$, we build a permutation $Gn$ of all integers from $0$ to $2^n - 1$. This sequence is then used to define a binary table $Tn$ with $n$ rows and $2^n$ columns.
CF 106307D - Gray Distances
We are given a recursively defined Gray code sequence of length $2^n$. Each integer in this sequence is written in binary, and these binary representations are arranged as columns of an $n times 2^n$ grid.
CF 106307B - Tree permutations
We are given a number $k$, and we are asked to construct a tree on at most 400 vertices such that the number of special permutations of its vertices is exactly $k$. A permutation is considered valid when it preserves adjacency in both directions.
CF 106307F - Is this Fibonacci
We are given a number written as a string, potentially very large, and we are asked to decide whether its value appears in the Fibonacci sequence defined by starting values f0 = 1 and f1 = 1, with every next term formed by summing the previous two.
CF 106307J - Modular Transform
We are given two circular arrays of length $n$, where each entry is a digit from 0 to 4. The array is arranged on a ring, so index $i-1$ and $i+1$ wrap around modulo $n$.
CF 106307I - Coprime vertex cover
We are given an undirected graph with vertices labeled from 1 to n and m edges connecting pairs of vertices. The task is to select a subset of vertices C with two simultaneous properties.
CF 106307G - Queries
We are maintaining two arrays over positions from 1 to n. Both arrays start filled with zeros. Over time, we repeatedly apply operations on segments and occasionally ask for a range maximum on the second array.
CF 106307E - Production Line
We are maintaining an array that changes over time, and we need to support both structural modifications and queries on its current state.
CF 106307C - Control Areas
We are working on a tree where every vertex is assigned a color, called a mafia. These colors change over time. The key difficulty is that a color does not just “occupy” its vertices. Instead, it also occupies additional vertices that lie on paths connecting its own vertices.
CF 106307A - Flips
We are given a grid of size n by m where each cell is either black or white. Time evolves in discrete steps, and at every step the grid is updated simultaneously according to a local rule applied to every 2 by 2 block.