Osijek Competitive Programming Camp, Winter 2024, Day 6: Potyczki Algorytmiczne Contest (The 3rd Universal Cup. Stage 2: Zielona Góra)
13 problems from Osijek Competitive Programming Camp, Winter 2024, Day 6: Potyczki Algorytmiczne Contest (The 3rd Universal Cup. Stage 2: Zielona Góra) (contest 105646), difficulty -. 13/13 solutions verified against sample I/O.
Osijek Competitive Programming Camp, Winter 2024, Day 6: Potyczki Algorytmiczne Contest (The 3rd Universal Cup. Stage 2: Zielona Góra)
Special | 13 problems | 13/13 verified | Difficulty - | 13m 14s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Interesting Paths | 51s | ✓ | |||
| B | Roars III | 52s | ✓ | |||
| C | Radars | 49s | ✓ | |||
| D | Xor Partitions | 57s | ✓ | |||
| E | Pattern Search II | 48s | ✓ | |||
| F | Waterfall Matrix | 55s | ✓ | |||
| G | Puzzle II | 45s | ✓ | |||
| H | Weather Forecast | 50s | ✓ | |||
| I | Mercenaries | 1m 1s | ✓ | |||
| J | Polygon II | 2m 38s | ✓ | |||
| K | Power Divisions | 1m 7s | ✓ | |||
| L | Chords | 47s | ✓ | |||
| M | Balance of Permutation | 54s | ✓ |
CF 105646M - Balance of Permutation
We are given a permutation of numbers from 1 to n, and we define its “cost” as the total displacement of elements from their natural positions, specifically the sum over all positions i of The task is not only to count or optimize this value, but to enumerate permutations…
CF 105646J - Polygon II
We are given several random segment lengths. Each length is not fixed but uniformly random on a continuous interval from zero to twice a parameter attached to that segment. Concretely, the i-th side length Xi is chosen uniformly from the interval [0, 2ai].
CF 105646K - Power Divisions
We are given an array where every element is a power of two. So each value looks like $2^{ai}$, meaning the entire array is just a multiset of bit positions, each element contributing a single set bit in a binary number. We need to split this array into contiguous segments.
CF 105646L - Chords
We are given a circle with an even number of points, and each point is paired with exactly one other point, forming a perfect matching. Each pair defines a chord inside the circle.
CF 105646I - Mercenaries
We are working with a one-dimensional sequence of cities arranged from left to right. Each city represents a starting point for a mercenary, and between consecutive cities there are shops.
CF 105646H - Weather Forecast
We are given a sequence of integers and we want to split it into exactly $k$ contiguous segments. Each segment has an average value, computed as the sum of its elements divided by its length.
CF 105646G - Puzzle II
We are given two binary strings of equal length. Each position contains either 0 or 1. We are also given an integer k, and we are allowed to perform an operation that selects a cyclic segment of length k in the first string and another cyclic segment of the same length in the…
CF 105646D - Xor Partitions
We are given a sequence of integers and we consider every possible way to split it into contiguous segments. Each segment contributes a value equal to the bitwise xor of its elements, and a partition’s score is the product of these segment xors.
CF 105646F - Waterfall Matrix
We are given an $n times n$ matrix that must satisfy a strong monotonicity rule: values never increase when moving right or downward. In other words, every row is nonincreasing left to right and every column is nonincreasing top to bottom.
CF 105646E - Pattern Search II
We are working with an infinite binary string constructed from the Fibonacci word recurrence. Instead of expanding it explicitly, we only rely on its recursive structure and the key property that any sufficiently long segment contains both characters and behaves “mixed” in…
CF 105646B - Roars III
We are given a tree where some vertices initially contain tokens. The twist is that we must evaluate the same movement process for every possible choice of root independently, and for each root compute how many moves can be made under an optimal strategy.
CF 105646A - Interesting Paths
We are given a directed acyclic graph with a fixed start vertex 1 and a fixed end vertex n. The task is not to find a single path, but to construct as long a sequence of valid 1-to-n paths as possible, with a constraint that makes each new path “bring something new” compared…
CF 105646C - Radars
We are given an $n times n$ grid. Every cell has a non-negative cost, and placing a radar in that cell covers a large square region of fixed size that depends on $n$.