MAXPRODU - EDITORIAL

taran_1407 · October 29, 2018, 3:32am

PROBLEM LINK:

Setter: Arjun Arul and Praveen Dhinwa
Tester: Rajat de and Jatin Yadav
Editorialist: Taranpreet Singh only. xD

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Mathematical skills and Proofs. Knowledge of Differentiation would be advantageous.

PROBLEM:

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.

EXPLANATION

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

x*(y-1)*[x*(y-2)-(x-1)*(y-1)]

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] = 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[i]+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.

Proof Section

See proof this and this as well as any good proof by differentiation for the problem “Maximize product of K numbers whose sum is fixed”.

Time Complexity

Time complexity is O(K) per test case.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed.

husainas · October 29, 2018, 10:00pm

I have also used the same approach for my solution. Can anyone please point out where i went wrong.
I got 50 points. My answer was giving wrong answer in only one set of test cases.
CodeChef: Practical coding for everyone
This is the link for my code.
Thanks in advance.
@admin @taran_1407

harshmmodi · October 29, 2018, 11:30pm

I used a bit different approach although the intention is still the same - To keep the elements as close to each other as possible.

For N < K(K+1)/2*, result is -1

For N >= K(K+1)/2:

Initialize the array num of size K as num[i] = i (1-based indexing).
Let P = N - K(K+1)/2* Now, add floor(P/K) to all the elements.
So, till now, all the elements are consecutive integers and sum of elements is K(K+1)/2 + floor(P/K) * K which equals K(K+1)/2 + (P/K) * K - (P mod K) which after simplification is N - (P mod K).
Now to make the sum of elements equal to N, we start from the last (i.e. Kth) element and add 1 to (P mod K) elements.
Once we have the elements, the final answer is calculated.

beginner_1111 · October 30, 2018, 12:50am

Literally when I was solving this problem , I did not find a mathematical approach rather I used observations from the examples provided and few extra examples. Let us take an example Ex1 :10 3, here we have to write 10 as sum of three unique numbers. 10=1+2+7 ,10=2+3+5, 10=1+4+5 ,10=1+3+6 … now finding the product of the expression mentioned in the question we get the maximum value for 2,3,5 ,Ex2: 13 3 here also there are some possible combinations out of which the triplet (3,4,6) gives the maximum value.

Observations: What did u observe p:) ? ,I observed that out of all possibilities the combination which has largest smallest element will be the answer … In case of a tie it should with largest second smallest element and so on…

This give me an idea of Binary search , First search the largest starting element of the sequence , then reduce n=n-element and k=k-1 , now the range becomes (element+1)…(n-element) with k decremented.

Now how does my check function of binary search look like let us say we are expecting X to be the starting point and we know then X+(X+1)+…(X+k-1)<=Current n here k is modified k not the original k. How to check the above sum it is simply sum of first (X+k-1) numbers -sum of first X-1 numbers.

Now we have our sequence and apply the formula given in the question to get the final answer. Be cautious when doing mod operations.

Trivial Case: if n is <(k)*(k+1)/2 the answer does not exist else there is an answer

Link: CodeChef: Practical coding for everyone

l_returns · October 30, 2018, 9:55am

I have a different approach.
Time Complexity O(k*log(n)).
I have divided problem into a subproblem.

Sub-Problem :

Find maximum value such that we can find k-1 distinct values greater than the value we give as answer such that their sum is less than equal to n.

Solution to Sub problem (O(log(n)):-

Click to view

Binary search over answer will give answer in O(log(n))

How to use this subproblem to solve this problem?

just get first value then do

n-=val;
k=k-1;
#and again apply same algorithm till k>0

This will solve this problem in O(k*log(n)).

#HERE is my accepted solution.

rishi2312 · October 30, 2018, 10:36am

My approach is pretty similar to this one except that I initialize my solution K parts with N/K. For example N=10 , K=3 the three parts will be \lfloor{N/K}\rfloor=\lfloor{10/3} \rfloor = 3.now the rest N\,mod\,K is distributed among the K parts such that the product is maximum. Since all parts of K must be distinct we need to keep each part as close as possible to the N/K.

I observe this by Arithmetic-Geometric mean inequality.

for example if x_1 ,\, x_2, \, x_3 \, ...\,x_k are the K parts of N then according to AM-GM inequality

$\frac{\sum_{i=1}^{i=K}x_i}{K} \le \sqrt[K]{\prod_{i=1}^{i=K}x_i} \$

\Rightarrow \frac{N}{K} \le \sqrt[K]{\prod_{i=1}^{i=K}x_i}

\Rightarrow \big(\frac{N}{K} \big)^K \le \prod_{i=1}^{i=K}x_i

The product will be maximum only if x_1\,=x_2\,=x_3=\,...=x_k

To get the distinct elements, let’s take a pair from the K parts. for N=10 ,K=3 it will be 3,3 adding and subtracting 1 from each we will get 2,4 and third part is itself 3.

the 3 parts are 2,3,4. remaining 10\bmod 3 = 1 will be added to the 3^{rd} part ie. 4 giving the result as 2,3,5.

now for N=99,K=4\,\,\,\lfloor{\frac{99}{4}}\rfloor = 24

so the 4 parts will be 24,24,24,24

to generate distinct values increase and decrease 1 in the first pair and increase-decrease 2 in the second pair ie. 22,23,25,26 and remaining 99 \bmod 4 = 3 parts will be distributed to the 4 parts resulting in 23,24,25,27.

solution link →
https://www.codechef.com/viewsolution/21331971

teut2711 · October 30, 2018, 1:06pm

I tried considering it as a knapsack problem with 1,N as weights and cost as x*x - x but even dynamic knapsack couldn’t help me.

rahul1995 · October 30, 2018, 5:08pm

I used the exact same approach.one missing element in continuous sequence. still got 100%WA. please someone check and tell me what wrong I did.

https://www.codechef.com/viewsolution/21342941

prottoy919 · October 30, 2018, 7:07pm

My approach is like this:

if (K*(K+1))/2 > N, then -1. else if (K*(K+1))/2 = N, then 0. Else ans always exists.

If the ans exists, then we can write n+(n+1)+(n+2)+…+(n+K-1) = N. So this is how I find out the starting number. Suppose, N = 100, K = 7. So n+n+1+n+2+n+3+n+4+n+5+n+6 = 100, so n = 11.

Then I find out the sequence 11,12,13,14,15,16,17. But their sum is 98. So I incremented last two numbers by 1 to make the sum equal to N. Then just calculate the ans.

mazumder7 · October 31, 2018, 10:52am

Can someone please tell me what’s wrong with this code? Seems like I used the same approach but still getting 100% WA. Thanks in advance. Here’s the link.
https://www.codechef.com/viewsolution/21347805

sliver_bug · October 31, 2018, 3:13pm

But what is the exact role of Differentiation in this question, i dont understand?

osho_garg · October 31, 2018, 7:40pm

I don’t understand this editorial. But there was also unofficial editorial of this question which is easy to understand https://discuss.codechef.com/questions/139170/maxprodu-editorial-unofficial?page=1#139371 .

krark · November 4, 2018, 1:24am

Can somebody explain this test case? If N=50 and K=8, this should be the correct partition: [2;3;4;5;6;7;8;15]

The product is 42674688000, which taken mod 1000000007 is 674687706.

The output of the editorialist’s solution is 734911237.

deepakagg500 · November 16, 2018, 12:18am

Please Help I am getting WA in sub-task2 #1
I tried to modify code for overflow problem but i am getting WA
https://www.codechef.com/viewsolution/21628610

jagreetdg · October 29, 2018, 10:09pm

It is due to overflow in the first case of sub task 2 (Assuming it’s that case only). Your answer turns out negative due to that. Mod the value in each iteration of the products and that’ll do.

souradeep1999 · October 30, 2018, 12:23am

This problem can solve with binary search,we can find the first element of the sequece using binary search such that last element must be greater than second last element,now after creating the sequence now if possible we will distribute extra number to atmost X numbers with value 1,(X is calculated value),now we calculate the answer. Link of soln: CodeChef: Practical coding for everyone thnx.

taran_1407 · October 30, 2018, 12:34am

Interesting. Well done. I didn’t think BS can be applied here.

harshmmodi · October 30, 2018, 12:39am

Link to solution: CodeChef: Practical coding for everyone

jagreetdg · October 30, 2018, 10:54am

I exactly had that approach and it scared the hell out of me when the editorial requisite mentioned the word “Differentiation” :\

yadnesh_viper · October 30, 2018, 1:04pm

I think testers’s solution also includes BS approach but it looks overkill for this problem.