The 1st Universal Cup. Stage 21: Shandong

13 problems from The 1st Universal Cup. Stage 21: Shandong (contest 106047), difficulty -. 13/13 solutions verified against sample I/O.

13 items

The 1st Universal Cup. Stage 21: Shandong

Special | 13 problems | 13/13 verified | Difficulty - | 12m 3s

#	Problem	Time	✓
A	Colorful Segments	58s	✓
B	Be Careful 2	1m 1s	✓
C	Connected Intervals	51s	✓
D	DS Team Selection 2	48s	✓
E	Computational Geometry	57s	✓
F	Puzzle: Sashigane	50s	✓
G	Gem Island 2	1m 28s	✓
H	Not Another Path Query Problem	56s	✓
I	Heap	55s	✓
J	Triangle City	44s	✓
K	Are you a bot?	53s	✓
L	Difficult Constructive Problem	53s	✓
M	Trie	49s	✓

Practice › Codeforces Solutions › The 1st Universal Cup. Stage 21: Shandong ›

CF 106047J - Triangle City

The city can be seen as a triangular grid of intersections. The first row has one node, the second has two, and so on until the nth row has n nodes. Each intersection is identified by coordinates $(i, j)$, where $i$ is the row and $j$ is the position inside that row.

Practice › Codeforces Solutions › The 1st Universal Cup. Stage 21: Shandong ›

CF 106047D - DS Team Selection 2

We maintain an array of length n that is being modified by three types of global operations, and we are repeatedly asked for range sums.

Practice › Codeforces Solutions › The 1st Universal Cup. Stage 21: Shandong ›

CF 106047M - Trie

We are given a rooted tree with vertex 0 as the root and vertices 1 through n. Every non-root vertex has exactly one parent, so the structure is already fixed as a rooted tree.

Practice › Codeforces Solutions › The 1st Universal Cup. Stage 21: Shandong ›

CF 106047G - Gem Island 2

We start with $n$ boxes, each initially containing exactly one ball. We then repeat a reinforcement process $d$ times. In each step, we pick one of the existing balls uniformly at random from the entire system.

Practice › Codeforces Solutions › The 1st Universal Cup. Stage 21: Shandong ›

CF 106047L - Difficult Constructive Problem

We are given a binary string where some positions are already fixed as 0 or 1, while others are unknown and marked with ?. We must replace every ? with either 0 or 1. After filling the string, we look at adjacent pairs and count how many times consecutive characters differ.

Practice › Codeforces Solutions › The 1st Universal Cup. Stage 21: Shandong ›

CF 106047K - Are you a bot?

We are given a target array $b$ of length $n$. Our task is not to compute a value from a permutation, but to reconstruct a permutation $a$ of numbers from $1$ to $n$ such that a derived function computed from $a$ matches $b$.

Practice › Codeforces Solutions › The 1st Universal Cup. Stage 21: Shandong ›

CF 106047H - Not Another Path Query Problem

We are given an undirected graph where each edge carries a 60-bit weight. A path between two vertices is evaluated not by summing or minimizing weights, but by taking the bitwise AND of all edge weights along that path.

Practice › Codeforces Solutions › The 1st Universal Cup. Stage 21: Shandong ›

CF 106047E - Computational Geometry

We are given a convex polygon with vertices listed in counterclockwise order. From this polygon, we must choose three vertices, call them $a$, $b$, and $c$, also in counterclockwise order along the boundary.

Practice › Codeforces Solutions › The 1st Universal Cup. Stage 21: Shandong ›

CF 106047B - Be Careful 2

We are working inside an axis-aligned rectangle whose lower-left corner is fixed at the origin and whose upper-right corner is at $(n, m)$. Inside this rectangle there are $k$ forbidden lattice points.

Practice › Codeforces Solutions › The 1st Universal Cup. Stage 21: Shandong ›

CF 106047C - Connected Intervals

We are given a tree with vertices labeled from 1 to n, and these labels also define a linear order. For any interval [l, r], we look at the vertices whose labels lie in this range and consider the subgraph induced by them in the original tree.

Practice › Codeforces Solutions › The 1st Universal Cup. Stage 21: Shandong ›

CF 106047I - Heap

We are given a sequence of values that are inserted one by one into an initially empty binary heap array. Each insertion uses the standard “sift-up” procedure: the new element is appended at the end, and then it is repeatedly swapped with its parent while the heap property…

Practice › Codeforces Solutions › The 1st Universal Cup. Stage 21: Shandong ›

CF 106047F - Puzzle: Sashigane

We are given an $n times n$ grid where every cell is white except for exactly one black cell that must remain uncovered.

Practice › Codeforces Solutions › The 1st Universal Cup. Stage 21: Shandong ›

CF 106047A - Colorful Segments

We are given several test cases, and each test case consists of a collection of segments on the real number line. Every segment covers a closed interval from $li$ to $ri$, and each segment is labeled with one of two colors, either red or blue.