2023 Edition

Day 1

G. Constructing an MST with Product Weights (Easy)

We are given a sequence (a) (with (|a_i| \le 10^6)), and we must build an undirected graph on (n) vertices ((n \le 2\cdot 10^5)) where the weight of edge ((i,j)) equals (a_i a_j). The goal is to compute the weight of the minimum spanning tree.

First, sort (a); this has no effect on the graph. Consider the case where all (a_i \ge 0). Due to Kruskal’s greedy rule, if we ever add an edge ((x,y)), the edges ((1,x)) and ((1,y)) must have been added already, meaning (x) and (y) are already connected. Thus the optimal MST connects vertex 1 to every other vertex, giving the cost (a_1 \cdot \sum_{i=2}^n a_i).

With negative numbers, the reasoning is similar. The answer becomes the smallest negative value multiplied by the sum of all positives, plus the largest positive value multiplied by the sum of all negatives. The overall complexity can be linear.

K. Counting Or Set Outcomes

Given a sequence (a) of length (n) ((n \le 2 \cdot 10^5)) with (0 \le a_i < 2^m), (m \le 30), we define the result of a sequence as follows: start with (x = 0); traverse the sequence; if (x | a_i \ne 2^m - 1), set (x \gets x | a_i), otherwise do nothing. You may reorder the sequence arbitrarily. How many distinct final values of (x) can appear?

All elements that would drive the cumulative OR to (2^m-1) can be deferred to the end; other elements' relative order doesn’t matter. The problem reduces to splitting the elements into two sets (A) and (B) such that the bitwise OR of (A) is not (2^m-1), but ORing any element of (B) with (A) yields (2^m-1).

We can enumerate which bit (i) is missing in the OR of (A). Then every element in (B) must have that bit set, and no element in (A) may have it. Checking each candidate takes (\mathcal O(nm)).

L. Minimizing Sum of MEX over Subarrays

Given a permutation (p) of length (n) ((n \le 5 \cdot 10^5)) with some positions filled and some missing, complete the permutation to minimize the sum of (\text{mex}) over all subarrays.

A classic trick decomposes the sum of (\text{mex}) into contributions: the sum equals (\sum_i c_i), where (c_i) counts subarrays that contain all integers (0,1,\ldots,i). To minimize the sum we always place the next smallest number at one of the extremes. Although the choice seems to have aftereffects, those effects effectively cancel out after at most two consecutive decisions, yielding a linear-time solution.

M. Maximizing XOR Sum of (Position + Value)

We need to build a permutation (p) of (n) ((n \le 2 \cdot 10^5)) that maximizes (\bigoplus_{i=1}^n (p_i + i)) and output any such permutation.

Let (d = 2^{\lfloor \log_2 n \rfloor}). The upper bound for the answer is (4d-2) (the sum is always even). Experiments show that reversing a contiguous segment of ([1,2,\dots,n]) always achieves the optimum. The pattern for the reversed segment ([l,r]) depends on (n \bmod 4):

• If (n \equiv 3 \pmod 4): (l = d-1, r = d).
• If (n \equiv 1 \pmod 4): (l = d-2, r = d).
• If (n) is even: start with (l = d-1, r = d). For each increment of (n) by 2, reduce (l) by 2. When (l) becomes negative, halve (r) and set (l = r - 1).

Direct simulation according to this rule passes; a formal proof is omitted here.

P. MST Construction with Bilinear Weights (Hard)

We are given sequences (a) and (b) ((|a_i|, |b_i| \le 10^6)), produce an (n)-vertex complete graph with edge weight (a_i a_j + b_i b_j), and find the MST.

Using Borůvka’s algorithm, the problem reduces to repeatedly performing operations: insert a point ((x,y)); given query ((a,b)), find minimum (a x + b y). Rewrite (a x + b y = b\left(\frac{a}{b} x + y\right)). A Li Chao tree maintaining (\frac{a}{b} x + y) handles these queries efficiently.

Day 2

B. Salesman X

A tree with (n) vertices ((n \le 2 \cdot 10^5)) and (2m) key nodes (x_1,\ldots,x_m,y_1,\ldots,y_m) is given. On day 1 start at node 1, visit all (x_i) in any order and stop at one of them; on day 2 continue from that node, visit all (y_i), and finally go to a given endpoint (s). Minimize total walking cost.

For day 1, the cost to stop at (x_i) equals twice the total edge weight of the Steiner tree of ({1, x_1, \dots, x_m}) minus the distance (d(1, x_i)). The tree cost can be computed by sorting nodes by DFS order and summing distances between consecutive nodes cyclically. We obtain a cost (d_i) for each possible stopping node. Inserting (d_i) into the Steiner tree of day 2 can be done by locating its DFS-order neighbors using binary search.

C. Recovering an Arithmetic Progression

An arithmetic progression (a_i = k i + l) ((a_i \le 10^{18})) of length (n) ((n \le 2 \cdot 10^5)) has (\lfloor (n-1)/2 \rfloor) terms tampered with. Given the multiset of remaining values, determine (k) and (l). A solution is guaranteed.

Since all (a_i) are congruent modulo (k), we examine differences (a_i - a_j). However, values are huge so factoring all differences is impossible. Observe that the step (k) satisfies ((a_i - a_j)/k < n). Hence we only check divisors (d) of (a_i - a_j) such that ((a_i - a_j)/d < n). Experimentally these divisors are few, and checking them suffices.

H. Two PCities

Given an unweighted tree on (n) vertices ((n \le 10^5)) and a graph (G) where an edge exists between two vertices if their tree distance exceeds a constant (k). Answer (q) queries ((q \le 10^5)) about the shortest path in (G) between (u) and (v).

A key observation: whenever a path exists, the shortest path length is at most 3. Determining answers 1 or -1 is straightforward. The challenge is detecting if length 2 is possible, i.e., whether there exists (w) with (dis(u,w) > k) and (dis(v,w) > k).

A divide-and-conquer on edges works: for each partition root, consider (w) from the other side. For a fixed (u), valid (w) form a suffix by depth. The farthest (w) from (v) in that suffix lies on its diameter, which can be maintained efficiently. Complexity (\mathcal O(n \log n)).

An alternative elegant solution: locate the midpoint of the (uv)-path in the tree. One side must be closer to (u) and the other to (v). Maintain diameters for both sides; one side is a subtree (handled by DFS), the other forms a prefix/suffix in DFS order, allowing (\mathcal O(n)-\mathcal O(1)) LCA and level-ancestor queries.

Day 3

B. AND Operations

You have an array (a) ((n \le 2 \cdot 10^5), (a_i < 2^{30})). An operation picks two adjacent elements (i, j) and replaces (a_i) with (a_i & a_j) (order doesn’t matter). The cost is the minimal number of operations to create a zero; if impossible, answer -1. There are (q) queries ((q \le 2 \cdot 10^5)) for subarrays ([l_i, r_i]).

If the subarray already contains 0, cost is 0. Otherwise we must produce a zero first; after that, other values are irrelevant. For a fixed position (i), we can compute the minimum left extension (dp_l) such that extending to the right yields zero. Only (\mathcal O(\log V)) distinct (l) values matter. Queries reduce to finding a minimal (dp)-interval within ([l,r]), solvable via offline scanning.

G. MOD Equation System on a Graph

Given array (b) ((n \le 2 \cdot 10^5)) and (m) edges ((m \le 2 \cdot 10^5)). You start with an array (a) of zeros and may repeatedly increment (a_u) and (a_v) for an edge ((u,v)). Determine whether (b_i \equiv a_i \pmod M) can be achieved for all (i). (M) is given globally, not necessarily prime.

Key observations:

1. If the graph is a forest, the operation is essentially unique; the condition is that sum of (b) on even-depth nodes equals sum on odd-depth nodes.
2. For a bipartite graph, the condition extends to equality of sums between the two parts.
3. If the graph contains an odd cycle, we can adjust values along that cycle. By processing non-cycle parts as forests, the cycle reduces to a single unbalanced position. Operations on an odd cycle can change that position by 2 while leaving others intact. If the unbalanced value is even, or if (M) is odd, a solution exists. The only impossible case is when (M) is even and the parity of the sum of (b_i) is wrong.

2022 Edition

Day 1

I. Forgotten Sequence

Construct the lexicographically smallest sequence (a) ((n \le 2 \cdot 10^5)) subject to (m) constraints of the form (a_x = a_y) or (a_x \ne a_y), or report impossibility.

Use a disjoint-set union (DSU) to handle equalities, then greedily assign the smallest available value to each component.

J. Median Edge Weight on a Path

Given a tree and (q) queries ((n, q \le 2 \cdot 10^5)), each asking for the median of edge weights on the simple path between (u) and (v).

This is a straightforward application of persistent segment trees.

K. Counting Distinct Prefix Maximums

Given an array (a) ((n \le 2 \cdot 10^5)) and (q) queries ((q \le 2 \cdot 10^5)), for each query interval report the number of distinct integers that appear as a prefix maximum when scanning that subarray.

Offline processing with a reverse sweep and a monotonic stack, combined with a Fenwick tree, yields (\mathcal O((n+q) \log n)).

L. Mex on Blackboard 2

Starting with sequence (a) ((n \le 2000)), perform (k) operations ((k \le 2000)). In each operation, choose a subsequence, compute its (\text{mex}), and append it. Count distinct final sequences modulo (998244353).

If you can achieve (\text{mex} = k), you can achieve all smaller mexs. If you insert a (\text{mex}) that wasn’t the global mex of the whole sequence, the status of numbers above the original mex is unchanged. Precompute a transition (to_i): when (mex = i) and you append (i), what becomes the new mex? Then DP over the number of steps.

M. 01 Tree

A tree of (n) nodes ((n \le 5 \cdot 10^5)) must be colored black/white, with (k) nodes precolored. Additionally, for each node (i) there is a constraint that node (a_i) and all its children must share the same color. Find any valid assignment.

Using DSU naively might traverse many children repeatedly. But once we merge (a_i) with its children, all of them become a single color; subsequent references to (a_i) only need to merge with (a_i) itself, not its children again. This ensures linear effective complexity.

N. Paken Machine

Given an initial (x), target (t), modulus (p) (prime, (p \le 10^9)), and six constants (a_0,a_1,a_2,b_0,b_1,b_2) (can be 0 or positive). Each step (i) (0-indexed) applies (x \gets (a_{i \bmod 3} x + b_{i \bmod 3}) \bmod p). Find the first step where (x = t), or report impossibility.

Operations repeat every 3 steps. After computing the composite effect of a 3-step block, we can brute-force the remainder modulo 3, and then use BSGS to find the minimal number of full blocks. Special care is needed for cases where coefficients are 0 or 1 to avoid division by zero.

O. Paken Land

For each node (i) in a tree of (n) vertices ((n \le 2 \cdot 10^5)), choose another node (j) to maximize the average edge weight on the simple path from (i) to (j).

Consider the sequence version first: transform averages into slopes as in ABC341G. On a tree, apply edge divide-and-conquer, build a convex hull for one part, and answer queries from the other part. Since queries have no monotonicity, binary search for the optimal slope is needed, giving (\mathcal O(n \log^2 n)).

Day 2

E. Harmony

There are (n) items and (m) colors ((n,m \le 10^5)). Each item has a value (a_i), a color (b_i), and a cost (c_i) to change its color arbitrarily. Answer (q) queries ((q \le 10^5)): with total cost budget (x_i), maximize the minimum value among colors.

Binary searching the answer reduces items to 0/1 values. Colors with more than one item must redistribute their surplus to colors lacking an item. Only (n) possible answers exist; sort items by (a_i) and maintain a balanced BST for decisions.

F. Farthest Node Assignments

Array (a) of length (n) ((n \le 2 \cdot 10^5)) has some entries replaced by -1. Fill them with numbers 1..n such that there exists an unweighted tree where the farthest node from (i) is exactly (a_i). Count valid completions modulo (998244353).

Necessary conditions: (a_i \ne i); the number of distinct values in (a) cannot exceed the number of leaves. These are also sufficient by constructing a star-like tree. Ignoring the leaf-count constraint gives an answer of ((n-1)^t) where (t) is the number of -1's. The extra constraint effectively demands a derangement on the set of colors. Partially filled derangements can be counted with inclusion–exclusion (see CF340E).

G. Worst Town

An interactive problem. The judge holds an undirected graph with (n) vertices ((n \le 200), edges (m \le 300)). You may query a vertex set and learn if it is an independent set. With at most 3200 queries, recover all edges.

Special subtasks: Sub2 — bipartite with odd vertices as left part. Sub3 — for any three vertices (a,b,c), if (ab) is an edge and (bc) is not, then (ac) must be an edge (the graph is a complete (k)-partite graph).

Sub2: Since left side has no edges, for each right vertex use binary search to find its neighbors among left vertices. Costs (\mathcal O(m \log n)). Sub3: Maintain independent sets dynamically. Adding a vertex fails only due to an edge, costing (n+m) queries total.

For the general case, follow Sub3 to partition vertices into independent sets, then apply binary search between each pair of sets. Total queries: (n + m + m \log n).

Day 3

A. Moving Piece

An ((2n+1) \times (2n+1)) grid ((n \le 300)) with cell costs (a_{i,j}) for placing obstacles. Block connectivity between ((1, n+1)) and ((2n+1, n)) at minimum total cost (cannot block the endpoints themselves).

Model as a minimum cut on a grid graph with 8-neighbor connectivity. Create a super source connected to the left boundary and a super sink from the right boundary; any source–sink path separates the two points. The shortest path length from source to sink gives the answer.

B. Chmax

Given sequences (a) and (b) ((n,m \le 3000)). For each (b_i) in order, you may pick an index (j) and set (a_j = \max(a_j, b_i)). Count distinct final arrays modulo (998244353).

Sort (b) in descending order. Once a position is modified, it can never be chosen again. Process by value groups. Let (f_{i,j}) be the number of ways having filled values from (i) upward with (j) untouched positions remaining. If there are (d_i) copies of value (i) in (b), transition via (\binom{j}{k} f_{i,j} \to f_{i-1, j-k}) for (k \in [0/1, d_i]). Accounting for the constraint (\min b_i > \max a_i) can be handled by reversing the whole process (adding positions instead of banning them).

C. Permutation of Length 26

Givan string (s) ((n \le 10^5)), first choose a contiguous substring and replace (s) with it, then choose a permutation (p) of 26 letters and apply it to maximize lexicographic order of the resulting string.

We will always pick a suffix. For two suffixes (i) and (j), to compare their best outcomes we need the LCP and character values. The greedy assignment maps each character to the largest unused character, determined by the first occurrence order of characters in the suffix.

Consider the sequence ({k - pre_k}) for positions in the suffix, where (pre_k) is the previous occurrence of the same character (setting occurrences before suffix start to 0). Two strings are equivalent iff these sequence are identical. Using segment tree hashing over this sequence, we can binary search the LCP and compare suffixes in (\mathcal O(n \log n)) or (\mathcal O(n \log^2 n)).

D. Yet Another Balls and Boxes Problem

Array (a) ((n \le 2 \cdot 10^5), (a_i \le 10^5)). Operation: choose (x, y) with (a_x \ge a_y); set (a_x \gets a_x - a_y), (a_y \gets 2a_y). Use at most (2 \cdot 10^6) operations to reduce the array to a single number, or report impossible.

Ideal case: array of (2^k) ones. General approach repeatedly merges pairs of odd numbers, turning them even. If the count of odds is always even, the process converges. If at any point the sum of the array has an odd prime factor that doesn't divide all numbers, a solution is impossible.

A variant allows leaving two numbers. Keep the leftover odd from each round, forming a set of (\mathcal O(\log n)) distinct numbers. Pick three numbers (a<b<c); simulate (b \bmod a) using doubling/subtraction similar to binary exponentiation. Operation count per modulo step is (\mathcal O(\log n)), total operations roughly (\mathcal O(\log^3 n)).

E. Output-Only Construction

Construct two sequences of positive integers of length (10^5) each, such that every integer from 1 to (2 \cdot 10^6) can be expressed as a product (a_x \cdot b_y).

All primes up to (2 \cdot 10^6) (about 150,000 of them) must appear; split them evenly. Additionally, include all integers 1 through 20,000 in both sequences. Any number up to (2 \cdot 10^6) has at most one prime factor above 20,000, guaranteeing a valid product.

I. Prefix OR Sum Minimization

Reorder array (a) ((n, a_i \le 2 \cdot 10^5)) to minimize the sum of prefix ORs.

A greedy approach that always picks the smallest next OR fails because ordering affects how many times a value contributes. Since the value domain is small, DP works: let (dp_m) be the minimum sum when the last prefix OR equals (m). The length of the prefix that ends with OR (m) is exactly the count (c_m) of elements that are subsets of (m) (precomputed via SOS DP).

Transition: (dp_m + (m | a_j) \cdot (c_{m|a_j} - c_m) \to dp_{m|a_j}). Removing the restriction to only OR with existing (a_j) and doing subset DP over masks, correctness is maintained. Enumerating subsets of each mask leads to (\mathcal O(3^{\log V})).

J. Balanced Permutation

Complete a partially filled permutation of length (n) ((n \le 5000)) to minimize (\max |i p_i - j p_j|).

Despite the deceptive constraints, a simple greedy approach that fills positions from the extremes works and passes in linear time.

2021 Edition

Day 2

I. Multiple Swap

Two arrays (a, b) of length (n-1) ((n \le 5 \cdot 10^4)). You may swap (a_i) and (a_j) if (j) is a multiple of (i). Transform (a) into (b) within (10^6) operations, or report impossible.

Relabel (a) according to (b); the goal becomes sorting (a) with at most (n-1) arbitrary swaps. A generic swap path (i \to f_i \to 2f_i \to 2 \to 2f_j \to f_j \to j), where (f_i) is the smallest prime factor of (i), works. Primes larger than (n/2) can never move, so if such positions differ, it's impossible. Otherwise each swap costs at most 11 operations.

J. Min-Max Sequence Counting

Given (n, m) ((n,m \le 2 \cdot 10^5)), arrays (a) (of 0/1) and (b). Count sequences (c) with values (1..m) satisfying: if (a_i = 0) then (c_i = \min(b_i, b_{i+1})); if (a_i = 1) then (c_i = \max(b_i, b_{i+1})). Modulo (998244353).

Define (dp_{i,j}) as number of ways for prefix length (i) with last value (j). For a max constraint, transition: [ dp_{i,j} = \begin{cases} \sum_{k \le j} dp_{i-1,k} & j = a_i \ [j \le a_i] dp_{i-1,a_i} & \text{otherwise} \end{cases} ] This can be optimized with a segment tree, or observed that the DP array always consists of at most one interval and one point, allowing linear updates.

K. Bracket Inserting

Start with empty string (s). Repeatedly insert () at any position. After (n) insertions produce the given string (t). Count insertion orders modulo (998244353).

Reverse the process: each step deletes a () pair. This corresponds to topological orders of the bracket tree. The number of valid orders equals (\dfrac{n!}{\prod siz_i}).

L. Zigzag Path

Graph with (n) vertices and (m) edges ((n,m \le 10^5)), unique weights. Find a (1 \to n) path where edge weights alternate between increasing and decreasing.

For monotonic increasing paths, use a vertex-splitting technique with prefix/suffix optimization. To handle alternation, keep a state bit and run shortest paths, resulting in (\mathcal O(m)) edges.

M. Deque and Inversions

For a permutation (p), repeatedly insert its elements either at the front or back of an initially empty deque (q). The cost is the number of inversions in the final (q). Sum this minimal cost over all permutations of size (n) ((n \le 10^6)).

Crucially, the greedy choice at each step is independent of future insertions. If (f_i) is the number of preceding elements smaller than (p_i), the minimal inversions added is (\sum \min(f_i, i-1-f_i)). By symmetry, for a fixed (i), the values (f_i) are uniformly distributed across (0..i-1), each occurring exactly (n!/i) times. Summing yields a combinatorial identity that simplifies to a closed form.

N. Polynomial Comparison

Given two polynomials (f(x)) and (g(x)) (degrees (n,m \le 2 \cdot 10^5)), determine the sign of (f(k) - g(k)).

Set (h = f - g). Process coefficients from highest degree downward. Use the identity (x^k = x \cdot x^{k-1}) to propagate values: if the leading coefficient is nonzero, add it (multiplied by (k)) to the next lower degree. As soon as a coefficient becomes large enough in magnitude, it determines the sign of the whole polynomial.

O. Golf

A string (s) ((n \le 2 \cdot 10^5)). A substring is good if it appears exactly once in (s). (q) queries ((q \le 2 \cdot 10^5)): given (l,r), find the smallest length (len) such that there exists a good substring covering ([l,r]).

For each starting position (i), there is a threshold length (a_i) beyond which all substrings are good. Compute (a_i) using suffix array. The query reduces to a range-minimum query over segments, solvable with segment tree sweeping.

Day 3

E. Counting Subarrays with Given LCM

Sequence (a) ((n \le 10^5)), point updates, (q) queries ((q \le 10^5)): how many subarrays have LCM exactly (x)?

A segment tree can maintain (\mathcal O(\log n)) distinct prefix/suffix LCMs per node and merge them in (\mathcal O(\log^3 n)). Alternatively, the total number of distinct LCMs of subarrays containing a fixed index is (\mathcal O(\log^2 n)) because each side contributes (\mathcal O(\log n)). Upon updates, segment tree binary search locates affected intervals, maintaining counts via hash maps.

F. Warp

A chain (1 \dots n) with (m) pairs ((u_i, v_i)). (q) independent queries: if we add one extra edge ((x,y)), compute the sum of shortest path lengths for all (m) pairs. (n,q \le 3 \cdot 10^5).

Classify pairs by relative position to (x,y). There are three cases where only (u_i, v_i) matter, and one where (v_i - u_i) matters. Use five 2D counting queries and two 3D counting queries to aggregate contributions. Complexity (\mathcal O(n \log^2 n)).