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.
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.
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. 
2 Likes
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
But what is the exact role of Differentiation in this question, i dont understand?
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 .
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.
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
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.
1 Like
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.
3 Likes
Interesting. Well done. I didn’t think BS can be applied here.
I exactly had that approach and it scared the hell out of me when the editorial requisite mentioned the word “Differentiation” :\
I think testers’s solution also includes BS approach but it looks overkill for this problem.
1 Like
setter’s solution is same as yours.
You have forgotten to take mod in your last loop.
1 Like
Nice…