National Yang Ming Chiao Tung University 2024 Team Selection Programming Contest
13 problems from National Yang Ming Chiao Tung University 2024 Team Selection Programming Contest (contest 105381), difficulty -. 13/13 solutions verified against sample I/O.
National Yang Ming Chiao Tung University 2024 Team Selection Programming Contest
Special | 13 problems | 13/13 verified | Difficulty - | 12m 8s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Trip Counting I | 1m | ✓ | |||
| B | Trip Counting II | 58s | ✓ | |||
| C | Trip Counting III | 58s | ✓ | |||
| D | Rearrangement | 53s | ✓ | |||
| E | Elimination Game | 50s | ✓ | |||
| F | Destroying Monsters | 52s | ✓ | |||
| G | Graph Coloring Problem | 1m 6s | ✓ | |||
| H | Points Separation | 56s | ✓ | |||
| I | LIS Decrement | 53s | ✓ | |||
| J | Randomized String Matching Algorithm | 1m 5s | ✓ | |||
| K | King's Challenge | 54s | ✓ | |||
| L | The Bag of Forgotten Coins | 1m | ✓ | |||
| M | The Tale of Professor Alya and the H-Index | 43s | ✓ |
CF 105381M - The Tale of Professor Alya and the H-Index
We are given a list of citation counts for a researcher’s papers, already sorted in non-increasing order. Each number represents how many times a particular paper has been cited.
CF 105381L - The Bag of Forgotten Coins
We are given a sequence of coins laid out in a line, where coin k has a fixed value v[k]. We are allowed to pick a subset of these coins, but there is a strict restriction: we cannot pick two coins whose indices differ by exactly one.
CF 105381J - Randomized String Matching Algorithm
We are given two strings, a long text s and a pattern t. We scan every starting position in s where t could fit. For each such position, Tony’s algorithm tries to decide whether the substring is equal to t, but instead of checking all characters, it performs k random probes.
CF 105381I - LIS Decrement
We are given a sequence of integers where each element carries a weight. From this sequence we are allowed to choose any subsequence, meaning we can delete elements while preserving order, and we care about two different quantities computed on that subsequence.
CF 105381G - Graph Coloring Problem
We are given a connected undirected graph where each edge has a weight. For a fixed threshold value $x$, we conceptually “ignore” all edges whose weight is greater than $x$, and only keep edges with weight at most $x$.
CF 105381H - Points Separation
We are given a fixed set of points in the plane, and then multiple query points. For each query point, we must choose a line such that the query point lies strictly on one side of the line and every given point lies strictly on the other side.
CF 105381E - Elimination Game
We start with pebbles labeled from 1 to n, where pebble i has weight i. In each move, two currently available pebbles are selected and passed through one of two devices. One device always returns the lighter of the two inputs, the other always returns the heavier one.
CF 105381B - Trip Counting II
We are given a graph with $n$ nodes where every pair of nodes is potentially connected, but only $m$ of those edges are actually usable. Think of this as a simple undirected graph: each of the $m$ input pairs describes a working two-way road between two countries.
CF 105381C - Trip Counting III
We are given a simple undirected graph with up to 300 vertices, where each input edge is guaranteed to exist and no duplicates appear. The graph represents travel routes between countries.
CF 105381D - Rearrangement
We are given a rectangular grid with $n$ rows and $m$ columns. Each cell contains an integer, and the only operation allowed is to permute values independently inside each column.
CF 105381K - King's Challenge
We are given multiple queries. Each query describes two integers $n$ and $k$, and asks us to work with the number formed by selecting $k$ distinct elements from a set of size $n$, ordered, which is the falling factorial $$P(n,k) = n cdot (n-1) cdot dots cdot (n-k+1).
CF 105381F - Destroying Monsters
We are given several test cases. Each test case describes a set of monsters placed on a number line and a set of weapons. Every monster sits at a single integer coordinate, and multiple monsters can share the same position.
CF 105381A - Trip Counting I
We are working with a complete undirected graph on $n$ countries, but some edges have been destroyed. After these removals, we are left with a simple undirected graph.