Fixed Value Construction: Binary & Fibonacci
Translated to English using AI. For a better reading experience, please visit: https://dk-qwq.github.io/blog/posts/bin-fib-decomposition/
Core Idea: Base Graph + Regulator
Regardless of the fixed-value construction method used, the essence is to construct a logarithmic-level base, and then use a regulator to construct the target fixed value through splitting methods similar to binary or Fibonacci.
1. Binary Decomposition
1. Principle Overview
By observing the value function, construct a base graph of the form $$$f_i = 2 \times f_{i - 1}$$$, obtaining $$$f_i = 2^i$$$. Perform a binary decomposition on the required fixed value, and finally achieve the construction of the fixed value through the regulator.
2. Practice Problems
Codeforces 388B — Fox and Minimal path
Problem Statement Given an integer $$$K$$$ ($$$1 \leq K \leq 10^9$$$), construct an undirected graph such that there are exactly $$$K$$$ paths of the same length from the start vertex to the end vertex.
Solution It is not hard to think of constructing it in the form of diamonds, resulting in $$$2^n$$$ paths of the same length to a single vertex. Then, append paths of fixed lengths respectively so that the lengths of the paths reaching the end vertex are all the same. Finally, perform a binary decomposition on $$$K$$$.
Optimization: How to minimize $$$n$$$? The basic diamond form is still somewhat wasteful. Consider optimizing the base graph into the following form:
The fixed-length paths appended at the end can also reuse chains of length $$$\log_2 V$$$. Through this reuse, the minimum $$$n$$$ can be reduced to the $$$3 \lfloor {\log_2 {V}} \rfloor$$$ level.
Reference submission: https://codeforces.me/contest/388/submission/387215801
AtCoder ABC 108 D — All Your Paths are Different Lengths
Problem Statement Construct a weighted directed graph such that there are exactly $$$L$$$ different paths from $$$1$$$ to $$$N$$$, and their lengths are integers from $$$0$$$ to $$$L - 1$$$.
Solution Assuming we already have paths from $$$S'$$$ to $$$T$$$ with weights in the range $$$[0, 2^{L - 1})$$$, attempt to connect $$$S$$$ and $$$S'$$$ to construct paths from $$$S$$$ to $$$T$$$ with weights in $$$[0, 2^L)$$$.
After trying, we can find that transferring can be completed by adding edges with weights $$$0$$$ and $$$2^{L - 1}$$$ respectively.
By analogy, the number of vertices is $$$2 + \lfloor {\log_2 L} \rfloor = 2 + 19 = 21$$$. Adding a few more edges to optimize away one of the vertices will satisfy the problem requirements.
Reference submission: https://atcoder.jp/contests/abc108/submissions/78452048
2. Fibonacci Decomposition
1. Principle Overview
Construct a Fibonacci sequence of the form $$$F_i = F_{i-1} + F_{i-2}$$$, and split the required fixed value using a reverse-order greedy strategy.
2. Correctness Proof (Zeckendorf's theorem)
Zeckendorf's theorem Any positive integer $$$N$$$ can be uniquely represented as the sum of one or more distinct non-consecutive Fibonacci numbers:
1. Proof of Existence * There exists a $$$k$$$ such that $$$F_k \leq N \lt F_{k+1}$$$, we select $$$F_k$$$. * Since $$$N \lt F_{k + 1} = F_k + F_{k - 1}$$$, we have:
This guarantees that when continuing the greedy decomposition for $$$N'$$$, the next selected Fibonacci number will definitely be less than $$$F_{k-1}$$$, naturally satisfying the non-consecutive condition.
2. Proof of Uniqueness * Lemma: The sum of a subset of non-consecutive Fibonacci numbers no greater than $$$F_n$$$ is strictly less than $$$F_{n + 1}$$$.
- Proof by Contradiction: Assume there are two different decomposition methods for $$$N$$$. Find the largest Fibonacci number whose presence differs between the two sets, denoted as $$$F_k$$$. Without loss of generality, let $$$F_k \in A$$$ and $$$F_k \notin B$$$.
- After removing the common parts greater than $$$F_k$$$ from both sets, the value of the remaining part is denoted as $$$N'$$$.
- At this time, the two decomposition methods for $$$N'$$$ are: $$$N' = F_k + \sum_{F_i \in A, i \lt k} F_i$$$ and $$$N' = \sum_{F_i \in B, i \lt k} F_i$$$.
- According to the lemma, the sum of all non-consecutive Fibonacci numbers less than $$$F_k$$$ in set $$$B$$$ is strictly less than $$$F_k$$$:
- However, in set $$$A$$$, $$$N'$$$ contains at least $$$F_k$$$, meaning $$$N' \geq F_k$$$, which leads to a contradiction. Therefore, the decomposition method must be unique.
3. Practice Problems
2026 Nowcoder Multi-University Training Contest 9A
Problem Statement Let $$$P_1 = 1$$$, and $$$P_v = \sum_{u \rightarrow v} P_u$$$.
We are required to construct a simple undirected graph such that $$$\sum_{u \rightarrow v} (P_u + P_v) = K$$$.
Solution Since it is a simple graph, the edge connection forms should be $$$(i - 2) - i$$$ and $$$(i - 1) - i$$$.
Try this connection method: * For the base graph $$$1, \cdots, b$$$, connect $$$(i - 2) - i$$$ and $$$(i - 1) - i$$$, which yields $$$P_i = F_i$$$. * Let the contribution of the base graph be $$$C_b$$$, then:
Consider how to regulate: * Hanging a node under node $$$i$$$ gives a contribution of $$$2 F_i$$$, which cannot change the parity. * We find that we can adjust the parity minimally by adding a new node connected to base nodes $$$2, 3$$$ to get a contribution of $$$9$$$.
Ultimately we can get: * Find the largest $$$b$$$ such that $$$C_b \leq K$$$. If the remainder is odd, subtract $$$9$$$ first. Divide the remaining even number by $$$2$$$; by Zeckendorf's theorem, it can definitely be decomposed. * If the remainder is odd and less than $$$9$$$, simply let $$$b := b - 1$$$. The required increase in contribution is only $$$3 P_b$$$. Since there is no requirement for them to be non-consecutive, any greedy construction will certainly have a solution.
Suggestions for Selection
- For problems with a small number of vertices, it is recommended to use the binary decomposition method.
- If the problem requires a simple graph and allows a larger number of vertices, it is recommended to use the Fibonacci decomposition method.
- Of course, the best approach is to decide based on the value function of the specific problem.
