Muhammad_mhs's blog

Help on CSES Problem!
By Muhammad_mhs, history, 4 years ago, In English

Stick Lengths In this problem , sort the array and I have to make all sticks size equal to array[n/2] ( n/2 = median ) then answer should be the minimum. But why I choose median index. Can anyone explain, Please ? Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

These kind of problems get solved by finding the medium element. Assume the stick lengths to be points on the X0 axis. We need to move all points into a single one while having the shortest possible distance sum of moving.

That single point is at a location where left of it are the same number of points as right of it. Because if we got more points on one of the sides we could move the point into that direction by one unit, which would decrease the sum of distances on that side by the number of elements. And increases the sum on the other side by the number of elements on the other side.

So, to find the point with minimum sum we need to move it in direction of the half with more points until both halfes are same.

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

You can think about it following way : If you move to the left or to the right from n/2, try to see the change in cost.

Spoiler

What about moving to the left.

Spoiler

Similarly to the right.

→ Reply