Just use binary search

The idea below was mine, but it failed due to a mistake (or floating point error), you can check out my source code (Pascal). 3392195

At first you can check whether (k*(k+1))>2n. If yes, output -1, for reasons clear below.

You can obviously see, that the number of pipelines at the end are,

1+s_1-1+s_2-1+....s_j-1=n.

So s_1-1 + s_2-1 + .... + s_j-1 = n-1

And 2=<s_i<=k, for all i, 1<=i<=j

So the problem reduces to : Find the minimum number of integers j in range [1..k-1] to make n-1, without taking any one twice.

Now, my idea was to use the biggest numbers in order (ie, k-1, then k-2,...etc.), till the sum of the taken numbers exceeded the part that must be taken after that point.

I mean the following steps *

i) Set k=k-1

ii) Set n=n-1

iii) Set ans=0

iv) if ((k*(k+1)) div 2) <n then output -1  

v) while (n>k) 

                a)       n=n-k

                b)       k=k-1

                c)       ans=ans+1

vi) if n=0 then output ans else output ans+1

• Pseudo code might have errors.

But the above algo is quite time consuming for extreme cases, say, if the input is 5000000050000001 100000001 ( you can easily understand why? :) )

Now, to improve it. In the above what we are effectively doing is to find the point at which the inequality in the while loop ( ie, n>k) goes false. If the loop would have been executed, then k would have value, say k-a. So the following inequality holds true.

n-(k-1 + k-2 + .... k-a+1) < k-a.

Solving this inequality, you will get some bound for a, isn't it?

But notice, the expression:

n-(k-1 + k-2 + ... k-a+1 + k-a)

is quadratic in a, ie its in terms of a^2.

So its solution ( by Shreedharacharya's method :) ) will involve squares and square roots ( You can have a look at my soln, or its C++ version 3408435 ) . And square roots, as you know, are notorious operations, floating point errors are quite common. So, I feel, some care is needed in implementing this routine.

But remember, I might be wrong. After all, my rating speaks :) :( Any errors, please tell me, perhaps here, or perhaps in the Talks section of cf.

Look at this one. This will help you. 3388662

Also my code will help you...I think it's simple binary search. 3410336

Look at this one 3390590