Need help in SNAKEEAT problem!! Binary Search (please help)!!

Hello, Here’s the problem link problem SnakeEat. Please read the question first. I’ll give you my quick explanation of my approach to this problem.
My Java solution My C++ Solution

So, first I sorted the array in ascending order.
Let’s say for example we have snakes length

3 5 9 10 12 15 18 21 and Q = 16

Now we will do a binary search to get the point where the snakes already greater or equal to 16.
Because in the above array of snakesLength we already have value 18 & 21 which is greater or equal to 10. We will not worry about those value now. we know that we already have 2 snakes that are longer than the value of K.
Now, we have to look at first six values of the array

3 5 9 10 14 15

(0 1 2 3 4 5) index

so we will do a binary search again to get the middle value of this array which is index 2. Now we calculate the sum of all elements after index 2(inclusive) so that will be 9 + 10 + 14 + 15 ==> 48. So, now we know that we need (164)-48 ==> 16 snakes to feed all these 4 snakes but we only have 2 snakes(index 0 and index 1). So, we go to the right with binary search, we get the index 3 so now 10 + 14 + 15 ==> 39, and we need (163)-39 ==> 9 snakes, but we only have 3 snakes(index 0,1,2) so we go to the right now index will be 4 and that will be 14 + 15 ==> 29 and we need (16*2)-27 ==> 4 and now we have 4 snakes (index 0,1,2,3) and that’s the maximum number we can have. so the answer will be we 2(snakes just fed) + 2(earlier snakes who were already bigger than the value of Q). Answer is 4

My code works for these values but it still gives me time limit exceed can anyone please tell me why is this happening?? Although I made a rough guess for the reason of time limit exceed that if we have 10^9 values it might getting time limit exceed because of taking the sum each time from the middle index to the right!! but I’m not sure. Or is it because long can’t hold the value of the sum because of the constraints because each value can be up to 10^9 and the size of the array can be up to 10^5. Can anyone please help me? Thanks

Just precompute the sum in an array or segment tree this will reduce your code complexity a lot.Long long can hold sum values easily.

1 Like
. Now we calculate the sum of all elements after index 2(inclusive) so that

This will take O(N) time, and its enough to give you a TLE. You can go through my solution, i used the same concept as yours-

https://www.codechef.com/viewsolution/13691858

1 Like

long long int can hold value upto 10^18.

1 Like

How did you reduce your time complexity? Is there any logic you added?

Now we calculate the sum of all elements after index 2(inclusive) so that — So, what will be the best way to do that without getting tle?

I used long long still getting tle, so now we know that’s not the issue

Can you please explain in detail about computing the sum in an array or segment tree? Thanks

I’m not familiar with trees yet, I’m just a beginner

Sorry, I was in class. Regarding your query, firstly i calculated the index after which all snakes are of length >=k. We can directly add ans to it. Then I binary search for the index i such that, snakes needed to make length of all snakes after index i longer than k <= excess snakes (which we can be eaten up by snakes).

The main point where my code differs from yours is that i pre-computed the sum of all elements till index i and can simply re-use it. You are calculating it again and again and this is causing TLE if array is big.

1 Like

You can do it a bit more easily by using lower_bound and upper_bound functions. Read them up if you dont know about them, they often come in handy :slight_smile:

1 Like

“In algorithms, precomputation is the act of performing an initial computation before run time to generate a lookup table that can be used by an algorithm to avoid repeated computation each time it is executed.”
How did you precompute the sum? "The main point where my code differs from yours is that I pre-computed the sum of all elements till index i " how did you find the index i before doing binary search, is it the middle element? Please can you explain me? can you explain the logic where you precompute the sum? Thank you

Precomputing the sum upto index i is easy. We maintain an array, where arr[i] is sum of all elements from index 0,1,2…i. Now lets say i want sum of all elements from index [2,8]. Its arr[8]-arr[1]. Use this concept and precompute.

I am doing binary search for index i, as i said here Then I binary search for the index i such that, snakes needed to make length of all snakes after index i longer than k <= excess snakes (which we can be eaten up by snakes)

1 Like

@vijju123 wouldn’t this be index [2,8]. Its arr[8]-arr[1].

this be index [2,8]. Its arr[8]-(arr[1]+arr[0])?
Or I think I misundertood
is that what you mean

Let’s say we have array 5 10 15 20 25 30

SO the sum array will be (arr) 5 15 30 50 75 105?

so, do we now do binary search on sum array?

No, we are using the sum array in calculation. This is to avoid this part-

Now we calculate the sum of all elements after index 2(inclusive) so that will be 9 + 10 + 14 + 15 ==> 48

Computing sum of elements upto some index i can take lot of time if array is large. We are technically saving all the time taken by your loop-

for(int i = (int) lastIndex;i>=median;i--)
				sum+=snakesLength[i];

Binary search is done on original array. Wherever we need things like sum etc. we refer to our second array where we stored stuff, so that we can save going through original array again and again.

1 Like

Thank you so much now i understand

Glad The query stands resolved :slight_smile: . Precomputation, when possible, can make the problem easier. One really awesome example is sieve of erastothenes.

//