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