@vivek1_007 In Online Solution, could you please explain why you defined prefix sum as
presum[x]=presum[x−1]+(109−l[x])
instead of
presum[x]=presum[x−1]+l[x]
In case of offline solution how to find largest element smaller than K value of current query which we are processing?
As requested, here is a video editorial on this:
Snackdown: SNAKEEAT - Video Editorial
We use the binary search approach here to solve the problem.
Cheers! 
I haven taken a different approach to solve the problem, the idea:
for each number of eaten snakes compute the length of the smallest remaining snake and store it in an array.
All what needs to be done for a query k is to binary search that array for the fist entry >= k and return n-index.
When submitting the solution I encountered the following strange behaviour:
I get a TLE for the original solution (see my solution).
I produced a WA “on purpose” by not considering the last query in the last testcase (see without last query). BUT I get the WA at a time of 0.23 seconds - hence pretty fast. I came to the last solution but optimizing my first one through many steps and the time when I got the WA on purpose constantly decreased (started with 3 seconds and went through 0.99, 0.3 til 0.23).
Can anyone explain this behavior to me? I can’t imagine a single query causing the time difference from 0.23 to TLE. Am I missing something? Or are the times for WA not representative? But somehow they are, because times decreased as I optimized my solution.
Would be glad for any ideas which give some insight on this!
What is presum[0]?
can somebody give me some inputs on online and offline solutions?
I have sorted array outside the query loop and used only binary search inside, can someone tell me why I am getting TLE? link to my code: CodeChef: Practical coding for everyone
Online solution is a solution in which you are answering a query simultaneously as you are accepting them as input OR you are answering each query before accepting next query as input.
Offline solution is a solution in which you are first accepting all the queries as input, then do something with that and then answer queries in one go.
1 Like
So that means I have always written online solutions. But it’s specifically said “Online” or “Offline” sometimes like in GPD. Does it mean anything? Does it add additional constraints? I can’t possibly see any difference in run time myself.
Offline and Online solutions will usually involve completely different strategies. The GPD question mandated an online solution to make sure the only possible strategy followed is that of persistent data structures. 
And yes, if your code got the value of K and immediately printed its answer, before getting the next K value , it was an online solution!
Common examples of offline processing are questions involving mo’s algorithm.
On a side note GPD can be solved online without persistent data structures.
You are sorting the array repetitively unnecessarily every time after each query, thus TLE.
“The most naive solution would be to keep iterating forward from 1 till we reach an element just smaller than K and name this index as cur.”
“For every query having value K, we first find the value of cur by binary searching on length array as it is in increasing order.”
According to the definition of cur mentioned in the editorial, for array
[11,13,13,13,14], cur would be 4^{th} element.
It means that the sample space of binary search is [1, cur] and the difference sum array will give the number of snakes to be fed to snakes in [prev+1, cur] to make their length at least K where prev refers to the largest index smaller than cur which is killed and can also be said that prev smallest snakes will be killed. For more clarity, please read the explanation part.
In most naive solution is the condition i>prev correct?
It won’t work for the case.
N=9
x x x x x 6 6 6 8
k=8
The answer should ideally be 3, but as per the condition (i>prev) the answer would be 5 if we calculate it as N-i.
What exactly we are trying to compute in presum array please explain in more detail. why 109- l[i]?
please explain the condition (prefix > prev)in offline solution. What is its significance.
I have followed 1-based indexing, so you will get 4 as the answer. But, the actual answer is N-i-1, because we are doing an extra iteration. So, you get the answer to be 3. Just updated it.
Can you please refer this link, I have posted a question.
https://discuss.codechef.com/questions/98924/doubt-in-snakeeat-editorial-from-snackdown
I have some more doubts.