Constructive Problems
This page gives a brief introduction to constructive problems.
Introduction
Constructive problems are a common type of contest problem.
In form, the answer to such a problem usually follows some pattern, so the answer may still be fairly easy to obtain even as the problem size grows rapidly.
Solving one therefore means thinking about how growth in the problem size affects the answer, and whether that effect generalizes. When designing a dynamic programming solution, for example, you have to consider what effect the transition from a state to its successor states has.
Characteristics
A striking feature of constructive problems is their high degree of freedom: a problem may admit many different constructions, but there will be a fairly simple one that meets the requirements. This looks like a relaxation that makes the problem easier, but very often it is exactly this freedom that leaves you without a clear line of attack and with no idea where to start.
Another feature of constructive problems is that they are flexible in form and endlessly varied. No general method or standard trick solves all of them; it is hard even to find what their solutions have in common.
Example problems
The examples below are meant to give you a feel for some of the ideas behind constructive problems and to suggest ways of thinking. Think each problem through before reading its solution. You are also welcome to share interesting constructive problems.
Example 1
Codeforces Round #384 (Div. 2) C. Vladik and fractions
Given \(n\), construct three pairwise distinct positive integers \(x,y,z\) such that \(\dfrac{1}{x}+\dfrac{1}{y}+\dfrac{1}{z}=\dfrac{2}{n}\).
Approach
The second sample shows how to construct the answer.
Split \(\dfrac{2}{n}\) into \(\dfrac{1}{n}+\dfrac{1}{n}\), then write the second term as \(\dfrac{1}{n+1}+\dfrac{1}{n(n+1)}\). So \(n,n+1,n(n+1)\) is a valid solution. As a special case, there is no solution for \(n=1\), because the reciprocals of three distinct positive integers sum to at most \(1+\dfrac{1}{2}+\dfrac{1}{3}<2\).
Example 2
Luogu P3599 Koishi Loves Construction
Task 1: decide whether there is a permutation of \(1\dots n\), of length \(n\), whose \(n\) prefix sums are pairwise distinct modulo \(n\), and construct one if there is.
Task 2: decide whether there is a permutation of \(1\dots n\), of length \(n\), whose \(n\) prefix products are pairwise distinct modulo \(n\), and construct one if there is.
Approach
For \(n=1\), both tasks are solved by the permutation \([1]\). Assume \(n>1\) from here on.
Task 1:
When \(n\) is odd, no valid solution can be constructed; when \(n\) is even, a sequence of the form \(n,1,n-2,3,\cdots\) works.
First, \(n\) must be the first element of the sequence: otherwise the prefix sums just before and just after \(n\) would land in the awkward position of being equal modulo \(n\).
Next, consider how to construct the whole sequence:
We obtain the original sequence by constructing its sequence of prefix sums. The differences of adjacent prefix sums (together with the first term) must be pairwise distinct modulo \(n\), because the difference array of the prefix sum sequence is the original permutation.
So we try to construct the sequence so that its prefix sums modulo \(n\) are
A sequence of this form satisfies all the constraints perfectly.
Task 2:
When \(n\) is a composite number other than \(4\), no valid solution can be constructed; \(n=4\) is handled separately with \([1,3,2,4]\). When \(n\) is prime, a sequence of the form \(1,\dfrac{2}{1},\dfrac{3}{2},\cdots,\dfrac{n-1}{n-2},n\) works, where division means multiplying by the inverse modulo \(n\) and then taking the representative in \([1,n]\).
First, when does a solution exist?
There is no solution when \(n\) is a composite number other than \(4\). For a composite number there are two smaller numbers \(p,q\) with \(p\times q \equiv 0 \pmod n\), for example \((3\times6)\bmod 9=0\). Once both \(p\) and \(q\) have appeared, every prefix product of the sequence is \(0\) from then on, so composite numbers other than \(4\) have no solution. The exception is \(4=2\times 2\): no such \(p,q\) exist, so a valid solution exists.
Now for the construction of the sequence:
By the same reasoning as in Task 1, \(1\) must be the first element of the sequence, since otherwise the prefix products just before and just after \(1\) are equal; and \(n\) must be the last element, because every prefix product from the position of \(n\) onwards is \(0\) modulo \(n\). Looking at the samples given in the problem, we find that every one of them has a valid solution whose prefix products modulo \(n\) are \(1,2,3,\cdots,n\), so we construct the sequence described above to meet this condition. It only remains to prove that these \(n\) numbers are pairwise distinct.
These numbers are the inverses of \(1 \cdots n-2\), each \(+1\), so they are pairwise distinct, and the problem is solved.
Example 3
AtCoder Grand Contest 032 B
Given an integer \(N\), construct an undirected graph with \(N\) vertices, numbered \(1\ldots N\), that satisfies the following conditions:
- It is a simple connected graph.
- There is an integer \(S\) such that, for every vertex, the indices of its adjacent vertices sum to \(S\).
The input is guaranteed to have a solution.
Approach
Analyzing the cases \(n=3,4,5\) suggests a construction.
Construct a complete \(k\)-partite graph whose \(k\) parts have equal sums. Then \(S\) is the same for every vertex, namely
If \(n\) is even, pair the numbers up from the two ends: \(\{1,n\},\{2,n-1\}\cdots\).
If \(n\) is odd, put \(n\) in a group of its own and pair up the remaining \(n-1\) numbers: \(\{n\},\{1,n-1\},\{2,n-2\}\cdots\).
For \(n\ge 3\), it is easy to prove that the graph constructed this way is connected; we omit the proof.
This solves the problem.
Example 4
BZOJ 4971 [Lydsy1708 Monthly Contest] The Knapsack in Memory
After a hard day's work, Little Q fell asleep. He saw himself back in his first days at university, learning the 0-1 knapsack: Little Q, then a first-year newbie, had solved a simple 0-1 knapsack problem. The problem went like this:
Given \(n\) items with volumes \(v_1,v_2,\ldots,v_n\), count the number of ways to choose some of the items (possibly none) so that their total volume is exactly \(w\). Since the answer can be very large, output it modulo \(P\).
After staying up late practicing problems for so long, he could only make out \(w\) and \(P\) in the sample input, and that the sample output was \(k\); he could not see how many items there were, nor what the volume of each item was. Even when he woke up, Little Q had not made out \(n\) and \(v\). Write a program to help Little Q recall the sample input.
There are multiple test cases, with \(50\le w\le20000\), \(1\le P\le2^{30}\) and \(0\le k\le\min(20000,P-1)\). You must output \(1\le n\le40\) items, with \(1\le v_i\le20000\).
Approach
This is one of the constructive problems with the most freedom, which is why it is so hard to see where to begin.
Since \(k<P\), we can directly construct a set of items for which the number of ways is exactly \(k\).
One construction takes \(i\) small items of volume \(1\) and some large items of volume \(w-t\), where \(1\le i\le20\) and \(0\le t\le i\). Since \(i<w\) and \(w-t\ge w-20>w/2\), every way of filling the knapsack exactly has to choose exactly one large item.
Let \(C\) be the contribution of a large item of volume \(w-t\) to the number of ways; then \(C=\dbinom{i}{t}\), and the contributions of different large items add up. Different items are counted separately even if they have the same volume.
Let \(f_{i,j}\) be the minimum number of large items that gives \(j\) ways when there are \(i\) items of volume \(1\).
Fix \(i\), set \(f_{i,0}=0\) and initialize all other states to \(+\infty\). Compute the unbounded knapsack transition in increasing order of \(j\):
Recording the \(t\) that attains the minimum lets us backtrack to recover the volume \(w-t\) of each large item. Computing this for all \(0\le k\le20000\) gives \(\min_{1\le i\le 20}(i+f_{i,k})\le 29<40\), so this precomputed range is sufficient.
Reference implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | |
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: leoleoasd, yzxoi, Estrella-Explore, Ir1d, partychicken, Marcythm, 24OI-bot, ouuan, fouzhe, H-J-Granger, Henry-ZHR, StudyingFather, NachtgeistW, Xeonacid, Enter-tainer, ksyx, iamtwz, Tiphereth-A, Marquis03, HeRaNO, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.