The 2023 ICPC Asia Hong Kong Regional Programming Contest (The 1st Universal Cup, Stage 2:Hong Kong)
12 problems from The 2023 ICPC Asia Hong Kong Regional Programming Contest (The 1st Universal Cup, Stage 2:Hong Kong) (contest 104172), difficulty -. 12/12 solutions verified against sample I/O.
The 2023 ICPC Asia Hong Kong Regional Programming Contest (The 1st Universal Cup, Stage 2:Hong Kong)
ICPC/IOI | 12 problems | 12/12 verified | Difficulty - | 10m 57s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | TreeScript | 53s | ✓ | |||
| B | Big Picture | 53s | ✓ | |||
| C | Painting Grid | 44s | ✓ | |||
| D | Shortest Path Query | 50s | ✓ | |||
| E | Goose, Goose, DUCK? | 51s | ✓ | |||
| F | Sum of Numbers | 52s | ✓ | |||
| G | Paddle Star | 55s | ✓ | |||
| H | Another Goose Goose Duck Problem | 1m | ✓ | |||
| I | Range Closest Pair of Points Query | 1m 11s | ✓ | |||
| J | Dice Game | 50s | ✓ | |||
| K | Maximum GCD | 1m 12s | ✓ | |||
| L | Permutation Compression | 46s | ✓ |
CF 104172L - Permutation Compression
We are given a permutation of length $n$, which means it is a rearrangement of numbers from $1$ to $n$. From this permutation, we want to end up with a smaller sequence of length $m$, consisting of distinct values, and we are told exactly which values must survive.
CF 104172K - Maximum GCD
We are given an array of positive integers. We are allowed to repeatedly modify individual elements using an operation of the form “replace a value by its remainder when divided by some chosen positive integer”.
CF 104172I - Range Closest Pair of Points Query
We are given a fixed set of points on a 2D plane, stored in an array order from 1 to n. Each query specifies a contiguous segment of this array, and asks for the closest pair of distinct points whose indices both lie inside that segment.
CF 104172J - Dice Game
We are given a game built around a perfectly uniform n-sided dice whose faces contain all integers from 0 to n − 1 exactly once. The game has two stages. First, Putata rolls the dice and obtains a value x. After seeing x, Budada gets a single decision.
CF 104172H - Another Goose Goose Duck Problem
We are simulating a very simple but constrained decision process over time. A player encounters an event every fixed number of seconds, and at each encounter they may or may not be able to act depending on whether a cooldown has finished.
CF 104172G - Paddle Star
We are given a two-segment motion starting from a point. First a segment of fixed length $l1$ is drawn from the origin, producing a point $Y$. From $Y$, a second segment of fixed length $l2$ is drawn to a final point $Z$.
CF 104172E - Goose, Goose, DUCK?
We are given a sequence of n geese arranged in a line, where each goose is associated with a task type ai. A “plan” is chosen by selecting a contiguous segment of geese, meaning an interval [l, r], and only those geese participate in completing their tasks.
CF 104172F - Sum of Numbers
We are given a sequence of digits, each digit between 1 and 9, written as a single string. We are allowed to insert exactly k plus signs into this string, splitting it into k+1 contiguous groups.
CF 104172D - Shortest Path Query
We are given a directed acyclic graph where every edge goes from a smaller indexed node to a larger indexed node, with an additional guarantee that the gap between endpoints is small. Each edge is either black or white. From vertex 1, we can reach every other vertex.
CF 104172A - TreeScript
We are given a rooted tree where nodes are numbered from 1 to n and each node i (except the root) has a parent pi with pi < i. This means the tree is already given in a constructive order, where every node appears after its parent.
CF 104172B - Big Picture
We are given a grid that is slightly larger than the standard one, with $(n+1)$ rows and $(m+1)$ columns. Each cell of this grid is independently determined to be black or white, but the way black cells appear is not given directly per cell.
CF 104172C - Painting Grid
We are asked to construct a binary grid with $n$ rows and $m$ columns, where each cell is either white (0) or black (1). The grid must satisfy two structural constraints that enforce global uniqueness in both directions. First, every row must be distinct from all previous rows.