### sid9406's blog

By sid9406, history, 4 days ago,

I was solving problem C from the Google kickstart Round H and this problem requires me to solve the below task :-

There are n points on the x-axis and two or more points can coincide . We want to arrange these n points on x axis such that they become adjacent. Each movement of 1 unit has cost of 1 unit . What is the minimum cost of doing this activity ?

My approach :- Sort the points and fix the position of the median point(if n is even you can fix any median) , then centre all other points around this median .

can somebody explain why this approach is incorrect and if you know the correct approach pls share.

Thanks

• +6

 » 4 days ago, # |   +2 The correct approach is right next to the problem under the "Analysis" tab.
 » 4 days ago, # |   +3 As it has been pointed out already, there is analysis available so you may check it for details and proof, but tl;dr is "After sorting, instead of taking median of X[i], take median of X[i]+i".An example to show why your current approach doesn't work is:1 1 3Optimal solution is to do 1->2 to get 1 2 3 in a single move, however by fixing median 1 and trying to achieve 0 1 2 you'll get 2 moves.
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 Thanks, but i think you meant X[i] — i instead of X[i] + i