An Integer Decomposition Problem
There are a lot of integer decomposition problems. Here is one of them: decompose an integer N into k different integers so that the sum of them is N and the multiplication of them is maximized. A vivid version of this problem described below.
Parliament (source: Northeastern Europe 1998): New convocation of The Fool Land’s Parliament consists of delegates. According to the present regulation delegates should be divided into disjoint groups of different sizes and every day each group has to send one delegate to the conciliatory committee. The composition of the conciliatory committee should be different each day. The Parliament works only while this can be accomplished. You are to write a program that will determine how many delegates should contain each group in order for Parliament to work as long as possible.
Input: The input file contains a single integer ( ).
Output: Write to the output file the sizes of groups that allow the Parliament to work for the maximal possible time. These sizes should be printed on a single line in ascending order and should be separated by spaces.
Sample Input
7
Sample Output
3 4
Before introduce the solution, let us review an inequality and the multiplication principle described below.
Theorem 1 (Inequality of Arithmetric and Geometric Means) For any list of nonnegative numbers , we have
and the equality holds if and only if .
Theorem 2 (Multiplication Principle) If a task consists of different operations , and each operation can be done by ways. Then, there are in total different ways to complete the task.
Back to our problem on hand. Assume that all delegates are separated into disjoint groups, each of which has delegates. Then, according to multiplication principle, there are different ways to compose a conciliatory committee. According to the inequality of arithmetric and geometric means, reaches its maximal value when .
Unfortunately, for any and , if , then , and should be an integer. However, the inequality of arithmetric and geometric means does give us some intuition: should be as larger as get close to each other. The following lemmas confirms this intuition. Without loss of generality, assume . Define the of two integers and as the number of integers between them. Denote it by . For example, since there are 6 and 7 between them. If , then we say that and has gap.
Lemma 3 Let when , and are nonnegative integers and . has the maximal value if and only if . Particularly, when , the maximum of is larger than strictly.
Given a increasing sequence of integers , define the number of gaps in as the number of pairs (,) which . For example, sequence has 2 gaps: one between 2 and 5, and the other between 6 and 8.
Lemma 4 reaches the maximal value if and only if there is at most one gap in and that gap is at most 1 if any.
The lemma above tells us that to make as large as possible, the sequence should composed by a list of continous integers , or two segments of continous integers and where . Example: , . Then . If , then . For , .
One natural question is that, given is fixed, how to look for valid sequence which maximize ? Well, by lemmas above, we can assume that where and . So
Or
by assuming where ,
Since is integer and , when is odd, . When is even, , depending on if is larger than half of . By this way, for any and valid , we compute the unique pair of and .
Lemma 5 Given and , the sequence maximizing is unique.
At this point, we can solve the problem as follows: For all possible , compute the and by above way. Then compute their corresponding values, between which we pick the largest one. The algorithm is inefficient since we involve computing the pretty number of many factors (imagine !!). Java and some programming language do provide BigInteger class, but it is time consuming.
The question following is, can we void manipulation on big integers? Yes. To make it, we need some insightful thoughts. From the example given above, it seems that increases and decreases when get larger, but not too large. At least, is not expected and should be voided. In a word, we try to get an as small as possible. The perfect value for would be 2, of course. However, not always we can make it. The good news is, should be 2 or 3.
Lemma 6 Let be the sequence maximinze among all valid sequences. Then is 2 or 3.
Proof: We prove it by contradiction. Assume . Consider the case . By Lemma 4, or . If , we construct a new sequence by replacing with and and keeping others intacted. Note that is a valid sequence, meaning that all elements in it are different and sum to . Then . That’s , which is a contradiction. If , we construct a new valid by replacing and by 2,3 and 5. Since , it contradicts the optimality of . Consider . In this case, we construct the new valid by replacing with two small factors and such that . According to Lemma 5, , yet another contradiction. So . Obviously, if , we can easily construct an valid .
Now, we narrow the search scope to those starting with 2 or 3. Furthermore,
Lemma 7 Let be the sequence maximizing starting from 2 () and starting from 3 (), where and . Let be the length of and be the length of . Then, and .
Proof: Obviously, . and . Combining them, we have
Assume . Then , or . However, since and , it’s impossible. So and then .
The above lemma simply states that if we get two valid sequences, namely, one starting from 2 with length which maximize when , and the other starting from 3 with length which maximize when , and each of them consists of two segments of continguous integers, then latter segment of the one starting from 2 is short than that of the one starting from 3.
This fact leads to following important lemma.
Lemma 8 Let valid start from 3 (). Then maximizes among all valid sequences if and only if or .
Proof: In either case of or , no valid sequence starting from 2 can be constructed according Lemma 7. According to Lemma 6, maximizes . Now assume maximize but . Then, we construct a new valid by replacing with 2 and . Since and , . So . Contradiction.
Now we come to the crux of the problem. We construct a valid sequence starting from where by the following way: start from , we keep adding until adding will make the sum of elements in larger than . Then, we increases each element by 1 in the order of and repeat the process until it sums to . The sequence we finally get is the answer.
array stores the sequence
while
end while
while
if
end if
end while
The next step is to prove the algorithm is correct. Given above lemmas, it’s an easy task.
Proof: Firstly, . Otherwise, the first while loop won’t terminate. So the body of second while loop will be executed at most times. If or , then starts from 3 with the second segment of length 0 or 1, respectively. According to Lemma 8, is optimal. If , we are unable to construct a sequence such that starts from 3 and will the second segment of length at most 1. If , has second segment of length at least 1. According to Lemma 7, we also cann’t construct maximing and starting from 3 with second segment of length at most 1. Combining Lemma 6, the is optimal.
The PDF version of this solution is available here.