Contest: The 23rd China Jiliang University ACM Team Contest / ACM Training Final Exam
Date: 2026-06-19
Author: Abs1nthe
This page is the English version of my solution notes. The difficulty ratings and Codeforces-style ratings are subjective training references, not official contest ratings.
The original Chinese version contains the full reference code blocks. This English version focuses on the problem statements, core observations, algorithms, and complexity analysis so that the structure is easier to read.
The contest contains 14 problems, labeled A through N. The topics include simulation, elementary number theory, construction, tree DP, shortest paths, disjoint set union, dynamic programming, combinatorial games, and offline processing.
| ID | Problem | Difficulty | CF Ref. | Tags | Note |
|---|---|---|---|---|---|
| A | Coin Classification | Medium-Hard | 1900 | Interactive, classification, decision strategy | Adaptive interactive problem |
| B | Agent Execution Plan Tree | Hard | 2100 | Tree DP, rerooting, combinatorics, modular inverse | Count valid topological orders for each root |
| C | Why Can Birds Fly | Easy | 900 | Number theory, gcd, prime factors, enumeration | Find the smallest available index |
| D | GTNH? | Medium | 1600 | Shortest path, Dijkstra, virtual nodes | Compress same-color jumps into color nodes |
| E | Matrix Construction | Hard | 2300 | Construction, xor permutation, complete mapping | The statement hints that it is not exam-friendly |
| F | Why Does Life Sleep | Easy | 800 | Simulation, adjacent difference, boundary checking | Scan important moments |
| G | ACMBTI String | Hard | 2200 | Construction, subsequence, state compression, search | Control whether 16 patterns appear |
| H | With This Flame, Cut Through Everything | Very Hard | 2400 | Combinatorial game, permutation counting, math | Determine winner property first, then count optimal permutations |
| I | All Returns Are Empty | Easy | 800 | Divisibility, basic I/O | Output a / b |
| J | After the Snow Melts | Medium | 1700 | Offline processing, DSU, grid connectivity | Process rising water level by reverse activation |
| K | Taibo’s Hope Beacon Deck | Medium-Hard | 1900 | Dynamic programming, state optimization, decision process | n,m <= 50 |
| L | First Meeting, A Million Times | Simple | 1200 | Prefix sum, construction check, non-negative array | Determine whether a valid rearrangement exists |
| M | Then, Toward Tomorrow | Simple | 1000 | Construction, permutation, reverse operation, lexicographic order | Case-based construction |
| N | Dice of Fate | Easy | 800 | Simulation, dice state maintenance | Maintain the six faces |
There are n coins divided into three classes A, B, and C. Their weights are strictly increasing by class, and each class has at least one coin. Each query compares two coins. The goal is to determine every coin’s class within at most floor(3n/2) queries. The problem is adaptive and interactive.
Maintain several equality groups. Coins inside one group have already been proven equal by = comparisons, so each group can be represented by one coin.
In the first phase, repeatedly take two representatives and compare them:
The key is to use each comparison to reduce uncertainty as much as possible. Equal results merge groups, while unequal results provide order information. After enough representative relations are known, the remaining classes can be assigned by comparing against chosen boundary representatives.
The algorithm only merges coins after an equality comparison, so every equality group is valid. Inequality comparisons are used only to build relative order between representatives. Since the three classes are totally ordered by weight, once a representative is known to be below or above a boundary, all coins in its group receive the corresponding class.
The strategy pairs representatives and tries to make every query either merge two groups or separate two representatives into different categories. With careful bookkeeping, the total number of comparisons can be bounded by floor(3n/2).
Given a tree, choose every node once as the root. For each root, count the number of valid execution orders that respect the parent-before-child dependency in the rooted tree.
For a fixed root, the number of valid orders is a multinomial merge of all child subtrees:
ways[u] = product(ways[v]) * C(size[u] - 1, size[v1], size[v2], ...)This is the classic count of topological orders of a rooted tree. Precompute factorials and inverse factorials for combination values.
After computing the answer for one root with DFS, rerooting transfers the answer from parent to child. Moving the root across one edge changes which side is considered the child’s subtree. With subtree sizes and modular inverses, the contribution can be updated in O(1) or logarithmic time per edge, depending on implementation.
Precomputation is O(n). The two DFS passes are also O(n), so the total complexity is O(n).
Find the smallest valid number/index that satisfies the condition implied by divisibility and common factors.
The condition can be reduced to checking gcd or prime factor relationships. Enumerate candidates from small to large and test whether the candidate is forbidden by the existing factor constraints. The first candidate that passes is the answer.
The direct enumeration is small enough for the given limits. With factor extraction, each test is efficient.
There is a graph-like movement system where normal edges and same-color jumps coexist. A naive complete graph over same-color nodes would be too large.
Introduce one virtual node for each color. Moving from an original node to its color node and then from the color node to another original node simulates a same-color jump. This compresses potentially quadratic same-color edges into linear edges.
After building the compressed graph, run Dijkstra.
If there are n original nodes, m normal edges, and c colors, the compressed graph has n + c nodes and O(n + m) edges. Dijkstra runs in O((n + m) log(n + c)).
Construct a matrix or permutation-like object satisfying xor-related constraints.
The key is to interpret the required rows or columns as permutations under xor. A complete mapping is needed: both f(x) and x xor f(x) should behave like permutations over the domain.
When the domain size has the right parity and power-of-two structure, xor operations allow a clean construction. Otherwise, the constraints force collisions and no solution exists.
The construction is linear or near-linear in the size of the output.
Given a sequence of states or moments, determine whether a condition involving adjacent changes can be satisfied.
Only boundary moments and adjacent differences matter. Scan the array once, compare each adjacent pair, and check whether the required change is valid. If any adjacent transition violates the rule, the answer is negative.
O(n) time and O(1) extra space.
Construct a string so that the appearance of multiple subsequence patterns matches a target 16-state condition.
Model whether each pattern has appeared as a bitmask. Appending a character updates the mask deterministically. Then the problem becomes a search over states: find a string whose final mask equals the target.
Because there are only 16 relevant pattern states, BFS/DFS over compressed states is practical. A carefully chosen transition order can also make the produced string shorter or more stable.
The state space is constant-sized with respect to the pattern mask, so the search is efficient. The output length depends on the construction path.
Analyze a game or arrangement over permutations, determine the winning property, and count the number of optimal permutations.
First derive the game-theoretic condition. Usually the result depends on parity, fixed positions, or whether a player can force a move into a losing state.
After the winner condition is known, count permutations that satisfy the optimal condition. This part is combinatorial: split positions into independent groups, count arrangements inside each group, and multiply them with factorial or binomial factors under modulo.
With precomputed factorials and inverse factorials, counting can be done in linear time over the permutation size.
Given a and b, output a / b.
This is a direct implementation problem. Read the input, divide, and print the result according to the statement requirements.
Given an elevation grid and several nondecreasing water-level queries, determine whether two cells are connected through cells whose elevation is strictly above the current water level.
A cell is passable under water level w iff:
h > wAs w decreases, more cells become passable. Therefore process queries offline in descending order of water level. Sort all cells by elevation descending. For each query, activate every cell with h > w that has not been activated yet, and union it with activated neighbors.
For each query:
NO.Sorting costs O(nm log(nm) + q log q). DSU processing costs O(nm alpha(nm)). Space complexity is O(nm + q).
There are n poison cards and m catalyst cards. Each turn applies poison according to the current poison layers, then one unused card is played, and finally poison damage is triggered multiple times. Determine the maximum total damage over all play orders.
Because n,m <= 50, dynamic programming is feasible.
Let:
dp[i][j][p]represent the maximum damage after playing i poison cards and j catalyst cards, when the enemy has p poison layers at the beginning of the current turn.
For each state, try playing one poison card or one catalyst card, update the poison layer count and add the damage triggered at the end of the turn. The final answer is the maximum over all states after all cards are played.
The number of states is roughly O(n * m * lim), where lim is the maximum possible poison-layer accumulation. Each transition is O(1).
Given a non-negative array a and a target sum S, determine whether the array can be rearranged so that for every position R, there exists some L <= R with subarray sum S.
If S = 0, every valid subarray must consist only of zeros, so every element must be zero.
For S > 0, any element that is neither 0 nor S creates a problem because all numbers are non-negative. It cannot form a sum S alone, and extending left only increases the sum.
Therefore the necessary and sufficient condition is:
0 or S.S.Then arrange the array so that every position can look back to the nearest previous S; zeros between them do not change the sum.
O(n) time and O(1) or O(n) space depending on implementation.
Construct the lexicographically largest initial permutation that becomes 1,2,...,N after exactly M operations. One operation chooses a non-last element and moves it to the end.
For small cases:
n = 1, only 1 is possible.n = 2, parity of m determines whether the answer is 1 2 or 2 1.For n >= 3:
m < n - 1, put the largest m values at the front in descending order, then append the remaining values in increasing order.m >= n - 1, the full descending permutation is lexicographically largest, and extra operations can be consumed by cycling moves.O(n) time and O(n) space.
A standard die starts with top/front/right equal to 1,2,3. Given a sequence of L/R/F/B operations, simulate the die and output the final top face.
Maintain six variables:
top, bottom, front, back, left, rightFor each command, update the four affected faces:
L: rolling left makes the right face become top.R: rolling right makes the left face become top.F: rolling forward makes the back face become top.B: rolling backward makes the front face become top.After all operations, output top.
O(n) time and O(1) space.