Construction
This page provides a brief introduction to construction problems.
Introduction
Construction problems are a common type of problem in programming contests.
In terms of form, the answer to such problems often exhibits a certain regularity, allowing it to be obtained relatively easily even as the problem scale increases rapidly.
This requires considering how the growth of the problem scale affects the answer and whether this effect can be generalized. For example, when designing a dynamic programming approach, one must consider the impact of transitioning from one state to its successor.
Characteristics
A prominent feature of construction problems is their high degree of freedom. That is, there may be many ways to construct a solution for a given problem, but there is usually a simpler construction that satisfies the conditions. This may seem like a relaxation of requirements, making the problem easier. However, often this high degree of freedom leads to a lack of clear direction, making it difficult to know where to start.
Another characteristic of construction problems is their flexible and varied forms. There is no universal solution or pattern that can solve all construction problems, and it is even difficult to identify commonalities in problem-solving approaches.
Example Problems
The following examples will help readers appreciate the conceptual depth of construction problems and provide inspiration for solving them. It is recommended to think deeply before reading the solutions, and everyone is welcome to share interesting construction problems.
Example 1
Codeforces Round #384 (Div. 2) C.Vladik and fractions
Construct a set of \(x,y,z\) such that for a given \(n\), \(\dfrac{1}{x}+\dfrac{1}{y}+\dfrac{1}{z}=\dfrac{2}{n}\) is satisfied.
Solution Approach
The construction method can be inferred from the second sample case.
Clearly, \(n,n+1,n(n+1)\) is a valid set of solutions. Specifically, when \(n=1\), there is no solution because \(n+1\) and \(n(n+1)\) are equal in this case.
As for how the construction idea arises, it likely comes from observing the sample cases and a bit of number sense. This problem is not difficult for those with strong mathematical intuition.
Example 2
Luogu P3599 Koishi Loves Construction
Task1: Determine whether it is possible to construct a permutation of \(1\dots n\) of length \(n\) such that its \(n\) prefix sums are pairwise distinct modulo \(n\).
Task2: Determine whether it is possible to construct a permutation of \(1\dots n\) of length \(n\) such that its \(n\) prefix products are pairwise distinct modulo \(n\).
Solution Approach
For task1:
When \(n\) is odd, it is impossible to construct a valid solution.
When \(n\) is even, a sequence of the form \(n,1,n-2,3,\cdots\) can be constructed.
First, we can observe that \(n\) must appear at the first position of the sequence; otherwise, the two prefix sums before and after \(n\) appears would be equal modulo \(n\).
Then, we consider how to construct the entire sequence:
Consider obtaining the original sequence by constructing the prefix sum sequence. It can be seen that the differences between any two prefix sums must not be equal modulo \(n\), because the difference sequence of the prefix sums corresponds to the original permutation.
Therefore, we attempt to construct the sequence such that the prefix sum sequence modulo \(n\) is:
It is not difficult to see that this perfectly satisfies all constraints.
For task2:
When \(n\) is a composite number other than \(4\), it is impossible to construct a valid solution.
When \(n\) is a prime number or \(4\), a sequence of the form \(1,\dfrac{2}{1},\dfrac{3}{2},\cdots,\dfrac{n-1}{n-2},n\) can be constructed.
First, consider when a solution exists:
Clearly, there is no solution when \(n\) is composite. For a composite number, there exist two numbers \(p,q\) smaller than \(n\) such that \(p\times q \equiv 0 \pmod n\), e.g., \((3\times6)\%9=0\). Then, once both \(p\) and \(q\) have appeared, the prefix products will remain \(0\) thereafter. Hence, there is no solution for composite numbers. Specifically, we note that \(4=2\times 2\), but there are no \(p,q\) satisfying the condition, so a valid solution exists for \(4\).
We consider how to construct this sequence:
Using a similar idea as in task1, we find that \(1\) must appear at the first position of the sequence; otherwise, the two prefix products before and after \(1\) appears would be equal. Moreover, \(n\) must appear at the last position, because all prefix products after \(n\) appears are \(0\) modulo \(n\). Analyzing the given sample cases reveals that all samples have a valid solution where the prefix products modulo \(n\) are \(1,2,3,\cdots,n\). Therefore, we can construct the sequence described above to satisfy this condition. We only need to prove that these \(n\) numbers are pairwise distinct.
We observe that these numbers are the inverses of \(1 \cdots n-2\) plus \(1\), hence they are all distinct. This solves the problem.
Example 3
AtCoder Grand Contest 032 B
Given an integer \(N\), construct an undirected graph with \(N\) nodes. Let the nodes be numbered \(1\ldots N\), and it must satisfy the following conditions:
- It is a simple connected graph.
- There exists an integer \(S\) such that for any node, the sum of the indices of its adjacent nodes is \(S\).
The input guarantees that a solution exists.
Solution Approach
By analyzing cases for \(n=3,4,5\), we can find a construction idea.
Construct a complete \(k\)-partite graph, ensuring that the sums of the indices in each part are equal. Then the \(S\) for each node is the same, equal to \(\dfrac{(k-1)\sum_{i=1}^{n}i}{k}\).
If \(n\) is even, we can pair them front and back, i.e., \(\{1,n\},\{2,n-1\}\cdots\)
If \(n\) is odd, we can take \(n\) alone as one group, and pair the remaining \(n-1\) numbers, i.e., \(\{n\},\{1,n-1\},\{2,n-2\}\cdots\)
The connectivity of the constructed graph for \(n\ge 3\) is easy to verify and will not be elaborated here.
This solves the problem.
Example 4
BZOJ 4971「Lydsy1708 Monthly Contest」Memory of a Backpack
After a day of hard work, Xiao Q fell asleep. In his dream, he recalled his first year in university when he learned about the 01 knapsack problem. Back then, as a freshman, Xiao Q solved a simple 01 knapsack problem. The problem was as follows:
Given \(n\) items, with volumes \(v_1,v_2,…,v_n\) respectively, calculate the number of ways to select some items (possibly none) such that the total volume is exactly \(w\). Since the answer could be very large, you only need to output the answer modulo \(P\).
Due to long hours of late-night problem solving, he only saw \(w\) and \(P\) in the sample input, and the sample output was \(k\). He couldn't see how many items there were or what their volumes were. Until he woke up, Xiao Q still hadn't seen \(n\) and \(v\). Please write a program to help Xiao Q recall the original sample input.
Solution Approach
This problem is one of the construction problems with the highest degree of freedom. This leads to a lack of direction and difficulty in getting started.
First, it is not hard to see that the modulus is irrelevant. Since we can freely construct the data, we can always make the number of solutions not exceed the modulus.
Through unconventional thinking, we consider constructing \(n\) small items with cost \(1\) and several large items with cost greater than \(\dfrac{w}{2}\).
Since at most one large item can be taken, each large item with cost \(x\) contributes \(\dbinom{n}{w-x}\) to the number of solutions.
Let \(f_{i,j}\) denote the minimum number of large items needed when there are \(i\) items of cost \(1\) and the number of solutions is \(j\).
Use dynamic programming to precompute \(f\). Calculations show that it is sufficient to precompute all values for \(i\le 20\).
This solves the problem.
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用