Behind the Exams: Thailand IOI Team Selection Test 2026
I authored four problems used in the 2026 Thailand IOI Team Selection Test. Their solutions are explained below.
Given a tree of \(N\) vertices where each vertex \(i\) where \(0 \le i < N\) is assigned an array of integers \(C[i]\) whose length is \(S[i]\). You are also given \(Q\) queries, for the \(i^{th}\) query you must answer the number of distinct number and the mode number (if there are many modes, print any) in the concatenation of \(C[w]\) for all vertices w that are on the simple path between vertex \(u_i\) and \(v_i\).
It is guaranteed that
$$ \sum S[i] \le 4 \cdot N \ N, Q \le 10^5 $$
First, consider the case where the tree is a line graph and \(S[i] = 1\). This is the classic distinct count query problem which can be solved by Fenwick tree, offline, in \(O(N \log N)\) or with Mo's algorithm in \(O(N^{1.5})\). Let us disregard the 'output mode' part of the problem for now.
What if the limitation \(S[i] = 1\) is removed? A problem arise: if Mo's algorithm toggle a node whose array is lengthy, too many times, then the complexity becomes \(O(N^2)\). A way to fix this is modifying Mo's algorithm: instead of having each block contain \(\sqrt N\) vertices, we make it such that each block (except the last one) must either contain only one vertex \(x\) satisfying \(S[x]\ > \sqrt N\), or contain some amount of vertices where the sum of the length of attached array of each vertex does not exceed \(\sqrt N\). By performing Mo's algorithm this way, the complexity again results in \(O(N^{1.5})\)
What if the tree is not a line graph? We can use the "Mo's on tree path" technique explained here. But again the complexity breaks, for a small part in the technique that toggles might toggle the LCA of each query. If that LCA is too heavy, the complexity explodes to \(O(N^2)\). There is a fix, but it makes the complexity rises to \(O(N^{\frac53})\), which fortunately passes the time limit. To fix this, we must consider on what conditions the LCA may not be put through this solution: that condition is when it is the LCA of more than \(\sqrt N\) queries and the length of its array exceeds \(\sqrt N\). It is clear that the number of such LCA are not many. In fact, if we allow ourselves to use \(O(N^{\frac53})\) time, then that threshold can be changed to: an LCA is bad if its array length exceeds \(O(N^{\frac23})\). It is clear that there are only \(\cbrt N\) such LCAs. We can run the previous solution to solve queries whose LCA's are not bad. Then we can handle the bad LCA one by one, solving for each bad LCA's queries by the following: we turn on that LCA and run a new instance of Mo's algorithm, but this time the Mo's algorithm needs block size of \(N^{\frac23}\), for that way the time spent by the right pointer (of this Mo's instance) is bounded by \(O(N^{\frac43})\); even if the time spent by the left pointer increases to \(N^\frac23\) per query, that is not a problem for it adds up per query and not per block. If we carefully add up the time of each part, it can be seen that the whole solution has the time complexity of \(O(N^{\frac53})\).
Now, what about maintaining the mode? We can at any time maintain a linked list for each frequency \(List_f\) storing all numbers whose frequency is \(f\). Then adding and removing a vertex is simple, and we can keep a number of what the current maximum frequency is.
Given a connected graph of order \(N\) and size \(M\) where each edge is assigned a weight which fits in a 64-bit integer type, you must maintain the graph given \(Q\) operations, where each one may be:
update(i, x): changes the weight of the \(i^{th}\) edge to be \(x\)query(u, v): print the lowest integer \(w\) if we delete all edges whose weight exceed \(w\), then the two vertices \(u\) and \(v\) remain connected.It is guaranteed that \(N, M, Q \le 100 000\).
First, consider the version where there are no updates. This can be easily solved by finding the minimum spanning tree and solving path maximum on it for each query.
Then consider the version where the graph is a tree; here we need not worry that the minimum spanning tree's structure will be affected by the updates. Hence, we can use heavy-light decomposition to answer path maximum queries and edge weight update queries.
There is a subtask at any time every edge has either the weight \(1\) or \(2\). To solve this we can view the queries as asking whether \(u\) and \(v\) are connected if we only consider the edges with weight \(1\). This can be done offline as it is reduced to the dynamic connectivity problem.
The second to last subtask adds the constraint \(M - N + 1 \le 50 \); that there are at most fifty non-tree edges once we obtain the MST helps a lot. To answer each query, first we build (with respect to the initial minimum spanning tree) the virtual tree (also called auxillary tree) comprised of the vertices which are the endpoints of the non-tree edges, together with two vertices which that query ask about; the edge weights in this virtual tree is set to be the path maximum of the two endpoints that we query from the minimum-spanning-tree (which is maintained by doing heavy-light decomposition on it, like that subtask above). Then we build a small graph that has all the vertices and edges of that virtual tree, together with all the non-tree edges whose weights are the latest current weights. Then we can perform a simple DSU solution on that small graph to obtain the answer. This small graph's order is bounded by 102 hence the solution is fast enough.
To solve the general case, we perform square-root decomposition on the queries, blocking queries to blocks of size \(\sqrt Q\). At the start of each block we divide edges into two groups: those that are updated within the block (active) and those that are not (constant); we build the minimum spanning forest considering only the constant edges. Then to answer each query we perform the trick of the last subtask, except here there are \(O(\sqrt Q)\) non-tree edges.
There exists an infinite two-dimensional plane, initially empty. An engineer is studying and will do \(Q\) operations, where in each operation she eithers
add x1 y1 x2 y2: places a copper wire onto the plane, which will stay fixed in place as a line segment from \(x1, y1\) to \(x2, y2\) which is guaranteed to either be parallel to OX or parallel to OY.query i j: asks whether the \(i^{th}\) and \(j^{th}\) wires are connected.There are at most 100000 operations.
First, consider the case where all wires are added before she asks anything. This can be solved by performing sweeplines and handling the cases where wires overlap and are parallel.
Then to solve the general case, we reduce the problem to the following: build a complete graph where vertices \(i\) and \(j\) are connected by an edge whose weight is the first point in time they become connected (or infinity if no such time exists). A query which is asked at time \(t\) can be answered by asking if the two wires remain connected when we remove all edges whose weights exceed \(t\). Notice that we only need to build the minimum spanning tree of that graph; this can be done by Boruvka's algorithm, where in each of the logN iterations we do two sweeplines for the two axes, and use a min segment tree to fetch optimal edges to add to each component (well, it must also stores second-max to prevent the min edge being in the same component as the one we are querying for). This solves it in \(O(Q \log^2Q)\)