sid9406's blog

Sitting Side by Side
By sid9406, history, 4 years ago, In English

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

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

The correct approach is right next to the problem under the "Analysis" tab.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks, but i think you meant X[i] — i instead of X[i] + i

    → Reply