Pipeline Question From Codeforces BinarySearch

#1

Hi, I’m Solving this problem in code forces.
http://codeforces.com/contest/287/problem/B

And my idea is that if n is lesser than k we should print 1.

else we should declare an array of sums size of k that sum[k] = sum[k-1] - i(i is the for var that it’s increasing from 0 to k).
and then we perform a binary search on that and with value n and if it’s not we print -1 if it’s we print the index of sum arr.

but the k can be up to 10^9 so the time complexity to declare that sum array if the k be 10^9 will be huge and it will get tle!

How I can make it better or I must change my idea?

#2

It is a problem in which you apply binary search on the answer…solve aggressive cows problem on SPOJ to get an idea of how to tackle these kinds of problems.

1 Like
#3

I know But if i run binary search it will get 10^9 + log(10^9) operations and it will get tle please read the statement of the question and my question also!!!

#4

You have to find a way to do it in log(k) complexity only…try to remove the extra 10^9 term by doing that job in a constant time.

1 Like
#5

Ok thanks i will try, do you have another question like this one?

#6

http://help.topcoder.com/data-science/competing-in-algorithm-challenges/algorithm-tutorials/binary-search/
this is a tutorial on binary search…
Try EKO and BSEARCH1 on SPOJ after aggressive cows for more practice.