CONSESNK - Unofficial Editorial

general
,
1

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 sort all the values Si in increasing order ( 1 <= i <= n ) . Its quite intuitive why the actual order of the snakes will be the sorted 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 ) L ] , ( 1 <= i <= n) .
  • 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

6 Likes
2

Please post the editorial for PROTEPOI as well. TIA.

3

This is terrific as it shows how only a finite number (and O(N))) possible solutions need to be checked even though the search space [A,B] is huge. To me that is the biggest lesson here. Very well-explained. May I suggest next time you consider using indexes 0…(n-1) instead of 1…N, that would make your formulas slightly simpler and also match what most people write in code. Thanks!

2 Likes
4

Use the well known fact that the mininimum value of summation of |X-Xi| occurs at the median value of X1, X2, … , Xn.

Link to solution:


[1]


  [1]: https://www.codechef.com/viewsolution/13821629
3 Likes
5

Can anybody point out my mistake in my approach…

1.I created three array one for point which is left of A other for those whose xi+l>B and one for the point which completely lie in interval [A,B]…And sorted all the array.

2.Then i moved the left array starting point i.e which is farthest in left to A and other point of left array end to end to it.similarly for Right array i moved rightmost point to B and then all other point end to end.

3.Now for Middle one i made two case either move all point of midddle array to start point of this array or to the end point.

  1. Then i considered all the case i.e 4 cases to merge three blocks (left,middle and right). and find minimum of all these.

Here is my code link


[1]
 


  [1]: https://pastebin.com/3Z7ZxVqa
6

How did you get the equation f(x) in the first place?
“”“Let us form a function that we need to minimise . The function will be as such in terms of variable X.
F( X ) = ∑ni=1|X+(i−1)∗L−Si| “””" How was it formed?

7

Thank you so much @royappa