Hello people . Many of you might have used a ternary search to solve the question ( by intuition ) , I have a solution that proves why your intuition was right. I will solve the problem without ternary search. So lets start from scratch .

- Lets first of all
( 1 <= i <= n ) . Its quite intuitive why the actual order of the snakes will be the sorted order.**sort all the values Si in increasing order**

Now let us suppose X is a variable that indicates the starting point of the snakes ( It is the same X that is being referred to in the question ) . The starting points of the snakes would be X , X + L , X + 2*L ,…

- Let us form a function that we need to minimise . The function will be as such in terms of variable X.
- F( X ) = \sum_{i=1}^{n} |X + ( i - 1 )* L - Si|
- Reframing the above function , It can be written as :
- F( X ) = \sum_{i=1}^{n} |X - [ Si - ( i - 1 )*L ] |

If u can recall some of your High School Mathematics , you very well know how to plot a graph for a function like :

F(X) = | X - a | + | X - b | + | X - c | + … where a <= b <= c

- Let Y be a new array where
= ***Yi****[ Si - ( i - 1 )**, ( 1 <= i <= n) .*L ]* - Now for the given question ***we will sort once again all the values Yi *** , ( 1 <= i <= n ). in increasing order.
- So , F( X ) = \sum_{i=1}^{n} |X - Yi |
- Now this question completely transforms to the High School question .

Now the task is just to find the minimum value of this function in the range * a* <=

*<= **

**X****( b - n*l )**

- X <= Y[ 1 ] : F(X) = [\sum_{i=1}^{n} Yi] - n*x
- X >= Y [ 1 ] and X <= Y[2] : F(X) = [\sum_{i=2}^{n} Yi ] - [\sum_{j=1}^{1} Yj ] - ( n - 2) * X
- So finally U can make the formula for each range :
- X >= Y [ i ] and X <= Y[i + 1 ] : F(X) = [\sum_{j=i+1}^{n} Yj ] - [\sum_{j=1}^{i} Yj ] - ( n - 2*i) * X

This function is a *** CONVEX FUNCTION *** … ( Look at the coefficient of X ,i.e , (2*i - n ) , which becomes positive as i increases . Hence , ternary search works .

However ,*** You dont need a ternary search *** , u can just evaluate the values of the function for all Yi

where , a <= Yi <= ( b - n*l) . Also check for the end points a and b-n*l .

You can have a look at my solution for a better understanding .

link:Solution