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 ?
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
3 Likes
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
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
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 ?
I solved the problem using the same logic 
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.
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 
Yes, that’s right.
@rahul127 modified solution: CodeChef: Practical coding for everyone
Just missed one mod operation in between
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.
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.
ok thanks.