OCPC Fall 2024 Day 2 Jagiellonian Contest (The 3rd Universal Cup. Stage 35: Kraków)
12 problems from OCPC Fall 2024 Day 2 Jagiellonian Contest (The 3rd Universal Cup. Stage 35: Kraków) (contest 105869), difficulty -. 12/12 solutions verified against sample I/O.
OCPC Fall 2024 Day 2 Jagiellonian Contest (The 3rd Universal Cup. Stage 35: Kraków)
Special | 12 problems | 12/12 verified | Difficulty - | 10m 59s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Suspicious Submissions | 1m 1s | ✓ | |||
| B | ICFC World Finals | 54s | ✓ | |||
| C | Diamonds and the Genie | 1m 4s | ✓ | |||
| D | Money in the Hat | 58s | ✓ | |||
| E | Gambling | 48s | ✓ | |||
| F | Red-Blue MST | 1m 6s | ✓ | |||
| G | Road Trip | 1m 3s | ✓ | |||
| H | Decent Path Around Bajt\u00f3w | 49s | ✓ | |||
| I | Random Remainders | 49s | ✓ | |||
| J | Sumotonic Sequences | 45s | ✓ | |||
| K | Bitter | 55s | ✓ | |||
| L | Empty Triangles | 47s | ✓ |
CF 105869C - Diamonds and the Genie
The grid contains a value in every cell representing diamonds. Jack moves through this grid using only right and down steps, so any path is monotone from the top-left corner to the bottom-right corner. The twist is that we are not optimizing a single simple path in isolation.
CF 105869L - Empty Triangles
We are given a set of points in the plane and multiple queries. Each query gives us three distinct points forming a triangle, and we need to determine whether there exists at least one other point from the set strictly inside that triangle.
CF 105869K - Bitter
We are given a rooted tree where each node represents an element that may carry an identifier, but this identifier is not always “fixed” in how it should be interpreted.
CF 105869J - Sumotonic Sequences
We are working with a sequence that is easier to understand through its differences rather than its raw values. Instead of reasoning directly about the sequence, we look at how each element changes compared to the previous one.
CF 105869I - Random Remainders
We are given an array of positive integers. The task is to compute a global sum over all ordered pairs where each element in the array acts as a divisor in a modular expression.
CF 105869H - Decent Path Around Bajtów
We are working with a graph where each state is a directed edge traversal decision, not just a vertex value. For every vertex $v$, and every neighbor $u$ adjacent to it, we define a quantity $L(v, u)$ which represents the longest possible walk that starts at $v$ and is forced…
CF 105869G - Road Trip
We are given a tree where each edge has an implicit distance, and a fixed parameter $c$ representing how far a car can travel on a full tank. When moving along the tree, a refuelling event is required whenever the remaining fuel is insufficient to continue along the next edge.
CF 105869E - Gambling
We are given a process defined on pairs of positive integers $(a, b)$ with $a < b$. From a state $(a, b)$, the system either terminates immediately with probability $1/2$, or transitions to a new state $(2a, b - a)$ with probability $1/2$.
CF 105869D - Money in the Hat
We are dealing with a process where a set of integers from 1 to n exists, and we randomly select a subset of size k from it. From that subset, we are interested in the maximum element.
CF 105869B - ICFC World Finals
We are given a rooted tree, and the task is to imagine drawing it on a grid under a very specific geometric rule. Each subtree is drawn inside a rectangular bounding box, and different subtrees attached to the same parent must be placed inside disjoint bounding boxes.
CF 105869F - Red-Blue MST
We are given a connected undirected graph where every edge is labeled either red or blue and has a distinct weight. The task is not to compute a single minimum spanning tree, but to understand how spanning trees behave when we constrain how many red edges they contain.
CF 105869A - Suspicious Submissions
We are given a collection of strings that are already sorted by nondecreasing length. For any two strings where the first one is not longer than the second, we want to decide how many ways we can make them “match” if we are allowed to replace a contiguous block of fixed…