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
The correct approach is right next to the problem under the "Analysis" tab.
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 3
Optimal 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.
Thanks, but i think you meant X[i] — i instead of X[i] + i