MAXPRODU - EDITORIAL (Unofficial)

PROBLEM LINK:

Practice
Contest

Author: admin3
Editorialist: admin5

DIFFICULTY:

Easy

PREREQUISITES:

Basic implementation, Greedy

PROBLEM:

You are given two integers N and K, you have to partition N into K distinct positive integers X1 + X2+ … + XK = N.
You have to find the maximum possible value of the product (x1 2−x1)⋅(x22−x2)⋅…⋅(xK2 −xK) and print it modulo 1e9+7.

EXPLANATION:

with K we can get the minimum sum 1 + 2 + 3 … K = K(K+1) / 2*

here we observed that if N < K(K + 1) /2*, we can’t partition N into K distinct positive integers, so the answer will be -1.

Otherwise we need to find out the valid K distinct elements, for doing this

  • first take K elements 1,2,3…K
  • now calculate the difference between N and K * (K + 1) / 2 because we have already taken elements from 1 … K so we got the sum K * (K + 1) / 2
    d = N - (K * (K + 1) / 2)
    now we need this more to get sum equals to N
  • now need equal distribution of d among K elements, So
    c = d / K
    r = d % K (if d is not divisible by K)
  • increase all K chosen elements by c and increase last r elements by 1
  • we got K elements with sum equals to N

Just calculate the answer of calculated K elements and take it’s modulo 1e9+7.

Time Complexity

Time complexity is O(K) per test case.

SOLUTIONS:

Editorialist’s solution can be found
here.

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

4 Likes

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. :slight_smile:
Link of soln: https://www.codechef.com/viewsolution/21272909
thnx.

1 Like

Your solution is pretty nice but I didn’t thought that it can be solve by binary search, when I approach this question :wink:

@souradeep1999 Can you please explain your method in detail? Probably as an answer?

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.
https://www.codechef.com/viewsolution/21320849
This is the link for my code.
Thanks in advance.

Does it mean that for all N and K for which N >= K(K+1)/2, N can be represented as the sum of K distinct positive integers ?

Yes, that’s right.

I used a similar approach with one difference.
Let kch = sum of (1+2+…+k). Then the first digit of the required sequence will always be (1+floor((n-kch)/k)), which will be followed by the next k-1 integers.
Example:
For n = 10, k= 3:
kch = 1+2+3 = 6, First element = 1 + floor((10-6)/3) = 2 => Sequence: 2,3,4
Now take the sum of this sequence and it’s difference with n, and proceed with the suggested approach.

@husainas it giving you wrong answer because of overflow condition.
As per your code …take this line…partitions=(partitions%mod)(dis[i](dis[i]-1))%mod…this produces overflow. so next time handle modulo condition carefully.

partitions= ( partitions%mod ) * ( dis[i](dis[i]-1) )%mod
let x = (partitions%mod)
so your new equation becomes
partitions = (x) * (dis[i] * (dis[i]-1)) %mod;
here x can be at most 10^9+6
and multiplication of (dist[i] * (dist[i]-1)) can be at most in term of 10^18 . so (x)
(dis[i]*(dis[i]-1)) can be (10^9 * 10^18) = (10^27) this condition leads to be overflow.

correct statement:
partitions= ( (partitions%mod) * ( dis[i] * (dis[i]-1) )%mod )%mod

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: https://www.codechef.com/viewsolution/21257220

3 Likes

@the_extractor u can see my answer down

can anyone help me to find the error in my code, i approached the question in exactly the same manner but i am getting WA in Sub-Task-2 , Task #1

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

@rahul127 modified solution: https://www.codechef.com/viewsolution/21337944

Just missed one mod operation in between

i used the same approach all the test case are accepted except one in subtask two’first test cases…anyone can give any suggestion about that …what that different in that test case…thanks
my solution here…
https://www.codechef.com/viewsolution/21330499

Thanks for modifying my solution.

1 Like

my solution only contains Binary search for each values in answer. nothing else.
HERE is discuss link to my answer.

a bit different from yours @souradeep1999

Just because of overflow like @rahul127 solution

In this statement

r = d % K (if d is not divisible by K) - increase all K chosen elements by c and increase last r elements by 1 - we got K elements with sum equals to N

Why not we increase our only last element by d%k to maximize the product ?

For N = 11 and K = 3
If we increase only last element by d % K it will generate max product 360 but if we increase last r elements by 1 we get 480,
Which is maximum.

//