Doubt in Consecutive Snakes

I am unable to understand how the function f(x)=∑1≤i≤N|x+(i−1)⋅L−Si| is generated. Can you please explain it in detail? In the editorial it was mentioned straightaway. There has to be some work behind that function. Please help. Thanks in advance.

1 Like

Here x is actually the position from where the line of snakes should start and x is unknown which we need to find in a manner such that the total distance moved by snakes is minimized. for every value of i where i indicate the snakes number.

Eg. For the first snake i=1 f(x)=|x+0-S1| that is the distance the snake 1 will need to move to reach x.

In this way it will sum over all the snakes and then we will find the minimum value of x using ternary search in this unimodal function.


Let’s work on the following situation,




                   X          X+L          X+2*L

Since the starting point of the Snakes is assumed to be X in the answer, firstly snake 1 has to be moved to X. So the distance covered would be |X-S1|.After the 1st snake has been shifted to ‘X’ starting point of the second snake i.e S2 has to be moved to the tail of first snake shifted so far.So the distance covered by the second snake would be |X+L - S2|.

Similarly, S3 has to be shifted to the tail of 2nd snake.
In general,
After (i-1) snakes have been aligned in a line, the tail of the last (i-1 th) snake would be *X+(i-1)L.
This would be the point i-th snakes has to be shifted to.

Hence the distance moved by the i-th snake would be |X+(i-1)*L - Si|.

To minimise total distance moved by all the snakes, we try to minimise this value for all ‘i’ resulting in,

F(X) =\sum_{i=1}^{n} |X + ( i - 1 )* L - Si|

Hope it helps!

1 Like

Thank you so much…

Thank you.