2022 China Collegiate Programming Contest (CCPC) Guangzhou Onsite
13 problems from 2022 China Collegiate Programming Contest (CCPC) Guangzhou Onsite (contest 104053), difficulty -. 10/13 solutions verified against sample I/O.
2022 China Collegiate Programming Contest (CCPC) Guangzhou Onsite
Special | 13 problems | 10/13 verified | Difficulty - | 14m 36s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Alice and Her Lost Cat | 57s | ✓ | |||
| B | Ayano and sequences | 53s | ✓ | |||
| C | Customs Controls 2 | 44s | ||||
| D | Digits | 2m 8s | ||||
| E | Elevator | 1m 2s | ✓ | |||
| F | Equations | 1m 5s | ✓ | |||
| G | Game | 1m 8s | ✓ | |||
| H | GameX | 47s | ✓ | |||
| I | Infection | 52s | ✓ | |||
| J | Math Exam | 2m 7s | ||||
| K | Middle Point Graph | 1m 15s | ✓ | |||
| L | Station of Fate | 53s | ✓ | |||
| M | XOR Sum | 45s | ✓ |
CF 104053M - XOR Sum
We are given a sequence of length $k$, where each element $ai$ is a non-negative integer bounded by $m$. For any such sequence, its value is defined as the sum over all pairs where the second index does not exceed the first, of the bitwise XOR of the pair: $$sum{i=1}^{k}…
CF 104053J - Math Exam
The solution answers all parts, but part (b) is incorrect and breaks subsequent reasoning. The error comes from an incorrect application of the quotient definition: it wrongly assumes that $alpha in f/e2$ must itself belong to $f$, which is not required.
CF 104053L - Station of Fate
We are given a scenario where $n$ distinct people are to be arranged into $m$ labeled stations, and each station holds a queue. A queue here is not just a set, but an ordered list, so the internal ordering of people inside each station matters.
CF 104053K - Middle Point Graph
Each vertex of a connected undirected graph is turned into a random point in 3D space. The coordinates of a vertex are independent uniform real numbers in the unit cube, so every vertex gets a completely independent random position.
CF 104053I - Infection
We are given a tree with n nodes. One node is chosen as the initial infection source, and that choice is random but weighted: node i is selected with probability proportional to ai.
CF 104053G - Game
Two players repeatedly build up numbers by multiplying chosen integers. Alice controls set $A$, Bob controls set $B$. Both start with values $alpha = 1$ and $beta = 1$. On every Alice move she picks any element from $A$ and multiplies it into $alpha$.
CF 104053D - Digits
The solution answers all parts, but part (b) is incorrect and breaks subsequent reasoning. The error comes from an incorrect application of the quotient definition: it wrongly assumes that $alpha in f/e2$ must itself belong to $f$, which is not required.
CF 104053H - GameX
We are given an initial set of distinct non-negative integers. Two players, Alice and Bob, take turns inserting arbitrary integers into this set. Each player makes exactly k moves, so in total 2k new numbers are added.
CF 104053F - Equations
We are given a function defined for a modulus $m$: we look at the linear congruence $$a x equiv b pmod m$$ and define $f(a,b,m)$ as the smallest non-negative integer $x$ that satisfies it, or $0$ if no solution exists.
CF 104053E - Elevator
We are given several elevators, each starting from floor 1 but not at the same time. Every elevator moves upward at a constant speed of one floor per second, so once it starts at time $xi$, it reaches floor $f$ exactly at time $xi + (f-1)$ if nothing interferes.
CF 104053A - Alice and Her Lost Cat
We are given a rooted tree where vertex 1 is the starting point and every node represents a position the cat could have passed through. The cat moves from the root down the tree without revisiting any node, so its path is simply some root-to-leaf path.
CF 104053B - Ayano and sequences
We are working with an array a that assigns each position i a label a[i]. In addition, there are two auxiliary arrays b and c, both initially zero.
CF 104053C - Customs Controls 2
All operations are in the family algebra of Exercise 203. For families $f,g$, the quotient is $$f/g = {alpha mid forall beta in g,; alpha cup beta in f ;text{and}; alpha cap beta = varnothing},$$ and the remainder is $$f bmod g = f setminus (g sqcup (f/g)).