2023 Sun Yat-sen University Collegiate Programming Contest, Onsite
12 problems from 2023 Sun Yat-sen University Collegiate Programming Contest, Onsite (contest 104819), difficulty -. 12/12 solutions verified against sample I/O.
2023 Sun Yat-sen University Collegiate Programming Contest, Onsite
Special | 12 problems | 12/12 verified | Difficulty - | 11m 23s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | SUN YAT-SEN University | 50s | ✓ | |||
| B | Lowest Common Ancestor | 1m 4s | ✓ | |||
| C | Triangle | 52s | ✓ | |||
| D | Cross the Storm | 1m 9s | ✓ | |||
| E | Travel | 57s | ✓ | |||
| F | Four K3 | 1m 3s | ✓ | |||
| G | Polynomial | 56s | ✓ | |||
| H | Polygon | 45s | ✓ | |||
| I | Dislike | 1m 7s | ✓ | |||
| J | Count | 1m 3s | ✓ | |||
| K | Nim X2 | 48s | ✓ | |||
| L | Function | 49s | ✓ |
CF 104819J - Count
We are asked to look at all possible labelled trees on $n$ vertices and compute a single numeric value for each tree: the sum of distances over all unordered pairs of vertices. This value is often called the Wiener index of the tree.
CF 104819L - Function
We are given a positive integer $a$. We want to construct a function $f$ on positive integers such that applying it twice behaves like multiplication by $a$, meaning that starting from any value $x$, if we apply $f$ once and then again, we land exactly on $a cdot x$.
CF 104819K - Nim X2
We are given several independent games. Each game consists of a number of piles of stones. Two players alternate turns, starting with Mandy.
CF 104819I - Dislike
We are given a permutation of length $n$, and for any contiguous subarray we look at its maximum element. For a fixed permutation, we compute a global value $G(S)$, which is the sum of these maxima over all $n(n+1)/2$ subarrays.
CF 104819G - Polynomial
We are given a sequence of integers, and this sequence is being modified through point updates. After each modification, we need to compute a value that comes from a rather unusual counting process involving polynomials.
CF 104819H - Polygon
We are given a collection of stick lengths and asked whether it is possible to pick exactly k of them so that they can serve as sides of a simple polygon.
CF 104819F - Four K3
We are given an undirected simple graph and asked to count how many subgraphs are exactly isomorphic to a fixed six-vertex pattern called “Four K3”. Although the diagram is not written in text, the structure is describable in words.
CF 104819D - Cross the Storm
We are given a linear chain of islands from 1 to n. Consecutive islands are connected by directed edges from i to i+1, and each such edge has a fixed cost.
CF 104819E - Travel
We are given a directed acyclic graph where each node represents a city and each city has a numeric charm value. The traveler must go from city 1 to city n along directed roads. The graph structure guarantees there are no cycles, so every valid route is a simple path in a DAG.
CF 104819B - Lowest Common Ancestor
We are given a rooted tree with vertex 1 as the root. Each vertex has a depth, defined as how many vertices lie on the path from the root to that vertex.
CF 104819C - Triangle
We are given a collection of identical right triangles with side lengths 3, 4, and 5. Each triangle is a rigid tile, and we are allowed to place multiple copies on a plane without overlap.
CF 104819A - SUN YAT-SEN University
We are given a single lowercase string and asked to count how many of its substrings contain the pattern "sysu" as a subsequence. A substring is defined by choosing a contiguous segment of the string, while a subsequence allows skipping characters without changing order.