Mathematical skills and Proofs. Knowledge of Differentiation would be advantageous.
Given N and K, represent N as sum of K distinct numbers so that the product (X_1^2-X_1)*(X_2^2-X_2)* \dots (X_K^2-X_K) is maximized. Print -1, if it is impossible to write N as sum of K distinct positive integers.
SUPER QUICK EXPLANATION
- Rule out the impossible case, when N < K*(K+1)/2. The answer is -1 since we cannot write N as a sum of K distinct elements at all. Otherwise, the answer will always exist.
- It is optimal to choose values X_i so as to converge around N/K while making those elements distinct.
First of all, we can see, that the smallest element, that can be represented using K distinct positive integers is 1+2+\dots K = (K+1)*K/2. This means, that N < K, It is impossible to write N as a sum of K distinct elements.
Now, answer always exist when N \geq (K+1)*K/2.
For this problem, I want to take some examples first.
Consider example N = 7, K = 2.
Three partitions (1,6), (2,5) and (3,4) exist. Calculating the expression, we get 0, 60 and 108 respectively.
Consider another example N = 9, K = 2.
For this example, partitions (1,8), (2,7), (3,6) and (4,5) exist. Value of expression for each partition is 0, 126, 180 and 240.
Consider pair (x,y). Value of expression for this is (x^2-x)*(y^2-y). Suppose we increase x by 1 and decrease y by 1 to get pair (x+1, y-1). The value of expression for this decomposition is ((x+1)^2-(x+1))*((y-1)^2-(y-1)).
Let us take the difference of value of expression for (x+1,y-1) and (x,y). If this difference is positive, it is beneficial to take pair (x+1, y-1) than pair (x,y).
We get the difference as
((x+1)^2-(x+1))*((y-1)^2-(y-1)) - (x^2-x)*(y^2-y)
By taking out common terms, we get
Outer two terms can only be any positive terms, so they do not affect the direction of the difference.
We just need to know whether x*(y-2) - (x-1)*(y-1) is greater than 0 or not. By differentiation, we can see, that this is very similar to Maximizing product when the sum of elements is fixed. The proof is also the same.
Hence, if d = N/K, It will be beneficial to choose pair (x+1,y-1) over (x,y) if x \leq d as, now the x will approach d which we know, is optimal by proof of maximum product with given sum.
Therefore, to maximize product, we need to choose elements as near the middle as possible. The above proof can also be extended to higher dimensions for higher values of K.
Now, we need to choose K distinct near elements. The ideal choice would be to choose some sequence X, X+1, X+2, X+3 \dots X+K-1. We can prove it is optimal, because we cannot find any such pair (x,y) from these elements for which (x+1, y-1) or (x-1, y+1) would be more optimal than (x,y) without violating the distinct element constraint.
But, it is not always possible to represent N as a sum of K consecutive integers.
COnsider example N = 10, K = 3. The solution for this test case is (2,3,5) Even if 4 is skipped. Let’s call 4 a hole for this test case. The reason is, that there are no consecutive K integers which have sum N. In this case, we try to use X+K and remove any one element from [X, X+K-1] so as to make the sum of all elements N. The reason is, that if we choose any other elements, there will be at least two holes.
Lemma: If we consider any partitioning with at least two holes, there will be a better partitioning with at most one hole.
Reason: Suppose we have partitions (2,3,5,7). We can choose (3,7) pair and transform it into (4,6), which, by our proof above, is optimal.
Hence, we know, that the optimal partition will be a consecutive integer range with at most one hole.
For Implementation, this type of partition is easy to construct, for which, you may refer any solution linked below. I am explaining my construction.
A* = i+N/K Since all elements will automatically differ by 1 which is handled by i. Adding N/K implies shifting the sequence by 1 to the right. Like, sequence 1,2,3,4 is shifted to 2,3,4,5 and so on, by N/K steps. Now, Taking N = N \bmod K, We have N < K. We can achieve partition sum as N by changing one element only. Since we want to avoid holes, and increase the sum of partitions by N \bmod K, we replace the element for which A*+N \bmod K = A[K-1]+1 because we add an extra element, 1 greater than the last element, and deleting the element, so as to make the sum N.
After getting the sequence, the Final answer can be easily calculated.
Time complexity is O(K) per test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Feel free to Share your approach, If it differs. Suggestions are always welcomed.