Problem Digest from THUPC 2023

M – "kejie"

Simply output the string.

puts("kejie");

J – Interval DP on Trees

Each node’s feasible value is an itnerval determined by its children. If any extremal value appears more than once among the children, the parent’s extremal value increases by one.

H – Even-Cycle Coloring

Recursive coloring that guarantees only even cycles share the same color.

solve(l, r, color):
    link([l, mid], [mid+1, r], color)
    solve(l, mid, color + 1)
    solve(mid + 1, r, color + 1)

D – Small Denominator Enumeration

The denominator is bounded, so brute-force enumeration suffices.

A – Limited General-Edge Paths

Any valid path uses at most k "general" edges. Run k rounds of DP restricted to those edges.

B – Greedy Works

Classic greedy strategy; no further detail needed.

K – Nim with XOR Sprague–Grundy

sg(x) = x, so the problem reduces to a straightforward digit DP on binary representations.

F – Column-wise Gaussian Elimination

Columns are independent; model each as a linear system. Gaussian elimination shows only a handful of free variables, so enumerate their assignments and combine results with a knapsack.

L – Circular Sushi (Chairman Tree)

Direct application of a persistent segment tree (Chairman Tree).

C – Inclusion–Exclusion on Forbidden Substrings

For target string sta, the answer is ∑S ∉ Asta PSFS = ∑S PSFS − ∑S ∈ Asta PSFS. Since ∑|Asta| is small, compute the difference efficiently.

I – Base-Tree Decomposition

Repeatedly pick the smallest unvisited vertex u and mark everything reachable from u. Relabel vertices by discovery order, classifying components as cycles, paths, or "rho" shapes. Maintain 0/1 flags for state constraints; implementation is intricate.

Miscellaneous Contest Probelms

xsy5300 – Car Matrix

(Statement omitted; standard matrix counting.)

xsy5301 – Construct "Kou Cao"

(Construction task; details skipped.)

xsy5302 – 2745518585 (Antiak)

(Anti-AK problem; no public statement.)

xsy5074 – Number Theory

(Pure math problem; brief.)

xsy5075 – Pigeon Lake

(Graph with pigeonhole flavor.)

xsy5076 – Domino Tiling

(Domino covering puzzle.)

THUPC 2022 Preliminary Round

A – LCM Graph

Exploit lcm(i, j) = i·j / gcd(i, j). Enumerate d = gcd(i, j); each i links to the first multiple of d in [l, r]. Edge count is O(n log n).

K – Handled by teammate "Tan"

(Solution delegated.)

J – Handled by teammate "Tan"

(Solution delegated.)

D – Swapping X and Y on a Cycle

The sample shows how X, Y fix a cycle. Realize that the swap(X, Y) step needn’t be executed each time—batch all swaps and adjust parity at the end.

B – First-Return Probability Convolution

Let fi,t be the probability of being at vertex i exactly at time t, and gi,t the first-return probability to i after t steps. The answer is the convolution of f and g.

F – Rotating Calipers on a Convex Polygon

Fix the distance of the first vertex to a reference corner in [0, k). As that distance grows monotonically, only O(n) "edge-crossing" events occur. Between events, every vertex’s coordinates are affine functions of the distance; the signed area becomes a quadratic, handled easily.

Fun fact: someone initially mistook the area for an n-degree polynomial.

Codeforces Archive

1322E – Median Mountain Range

(Sweep-line + median maintainance.)

860G – Flowers and Chocolate

(DP on modular arithmetic.)

1147E – Rainbow Coins

(Colorful coin DP with bitmask states.)