Doubt in SNAKEEAT editorial from snackdown?

In editorial of SNAKEEAT problem, can anyone please explain the offline approach in more detail.

I am not getting the logic of this approach, what we are trying to achieve by calculating prefix and significance of the condition (prefix>prev) and also explain why this approach is working.


Try this out.

Just gave it a read. Lol, couldnt make head or tail outta it. Thats beyond my capacity atm i guess :frowning:

Well, basically for each query we have 3 groups of snakes.
Group 1: Snakes that are >= required length. We don’t need to do anything with them. Cur (or, to be more exact, something like N-cur) lets us know how many such snakes do we have. Group 1 is positioned between cur and end of the array.

Group 2: Snakes that are not of the required length yet, but which we will try to lengthen by killing snakes from group 3. Group 2 is positioned between prev and cur.

Group 3: Snakes that we will butcher. Prev lets us know how may of snakes we are going to butcher. Group 3 is positioned between beginning of the array and prev.

Now we can talk about prefix. Prefix is sum of “deficit of length” in group 2, basically it is how many snakes (at least) we must kill so that snakes in group 2 (between cur and prev) are long enough. Since we kill prev snakes, prefix must be <= prev to lengthen all snakes in group 2. So while prefix>prev we will take on each step one (smallest) snake from group 2 and move it in group 3 (represented by increasing prev and decreasing prefix by its “deficit of length”).

When we are moving from one query to the next we will first move cur and shrink group 1 (since some of the snakes that were >= previous K are < current K), moving these snakes from group 1 to group 2 (and updating prefix), then we will move prev (shrinking group 2 and increasing group 3) and updating prefix. Since queries are sorted both prev and cur may only move in one direction.

Where is it mentioned that the queries are sorted? I guess I am missing something here, could you support it with some basic pseudocode?

Essence of having an “offline solution” means that you can collect all queries first, rearrange them, then output in special order afterwards