SpongeBobSquarePants's blog

By SpongeBobSquarePants, history, 3 months ago, In English

OK so there is this problem of CSES, Stick Lengths

Brief of problem: Given some numbers, you have to make all numbers equal. You can do + or — any number to any number in array and the overall cost is the sum of all the number changes you make. Example, 1 4 10. If we think to make all elements to 5 cost is abs(1-5)+abs(4-5)+abs(10-5). We have to minimize this cost.

Solution: You find the median and compute the answer. This means that you make all elements equal to median. For example in 1 4 10 => it is 4. So minimum answer is: abs(1-4)+abs(4-4)+abs(10-4) = 3+0+6 => 10

What I thought: Let all the numbers be on x axis. Now I want all the points to be at the smallest distance from one central point so that the overall sum should be minimum. Then I thought that this must be mean. Because mean is the middle value of all the elements, converging all the points to mean would be correct. But no it's not mean, it's median.

My Question: Why median works and mean does not. Please give me an easy explanation. A mathematical reasoning which I can build on my way of thinking. Because I am not able to understand why it doesn't work for mean.

Counter example: Let's say we have, 1 2 1005 The mean is = (1+2+1005)/3 => 336. So cost is abs(1-336)+abs(2-336)+abs(1005-336) => 1338 The median is 2. So cost is abs(1-2)+abs(2-2)+abs(1005-2) => 1004 So median works and that is how I basically cheated and solved the question but it doesn't satisfy that inner feeling of why.

PS: Please help and please explain in a light language.

Read more »

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