Why does mean NOT work in CSES-Stick Lengths?

help
, ,
1

Here is the link to the problem:
https://cses.fi/problemset/task/1074

2

If you just want a counter example, consider the case 1,2,1005. Here it is optimal to take median value to be final length of sticks rather than taking mean.

2 Likes
3

@lonely_coder12 i tried to do it using median but getting WA on last test case:

`n = int(input())
 b = 0
 arr = sorted(list(map(int, input().split())))
 z = len(arr) 
 med = int(arr[len(arr) // 2])
 for i in set(arr):
     b += abs(i - med)
 print(b)`
4

Corrected Code:

n = int(input())
b = 0
arr = sorted(list(map(int, input().split())))
z = len(arr) 
med = int(arr[len(arr) // 2])
for i in arr:
    b += abs(i - med)
print(b)

@anon58263146 You just need to remove that “set” from your code. It actually removes the duplicate elements, and that is wrong. The reason why your incorrect code worked on the sample test case provided with the problem statement is that the median itself is 2 in that case and |2-2| = 0, so even if you remove duplicate 2 's you still get the correct output.

5

Thanks, i didn’t notice that i used set… :sweat_smile:

6

mean works for the case when the cost is difference square

7

can someone pls tell the intuition behind the approach to this problem? I heard William lin saying “It’s a well-known problem”.

1 Like
8

Its a well known math problem. If you have a list of numbers and want to find the minimum cost to make them same , then you can achieve this by making them all equal to the median of the list.

This book explains it in a very easy to grasp manner.

9

I read this. This book doesn’t explain it that well. Plus, the problem is to find x that minimizes the sum of |a1-x| + |a2-x| + … + |an-x|. In this also, the optimal value turns out to be the median but why? The book says: “It turns out that the optimal choice for x is always the median of the
numbers, i.e., the middle element after sorting … The median is always optimal, because if x is smaller than the median, the sum becomes smaller by increasing x, and if x is larger than the median, the sum becomes smaller by decreasing x. If n is even and there are two medians, both medians and all values between them are optimal choices.” Why?

1 Like
10

you can use the basic quicksort for this
#include<bits/stdc++.h>
using namespace std;

void quicksort(int a[], int l, int r)
{
int pivot=(a[l]+a[r])/2,i=l,j=r;
while (i<j)
{
while (a[i]<pivot) i++; while (a[j]>pivot) j–;
if (i<=j)
{
swap(a[i],a[j]);
i++;
j–;
}
}
if (i<r) quicksort(a,i,r);
if (l<j) quicksort(a,l,j);
}

int main()
{
int n;
cin>>n;
int a[n];
for (int i=0; i<n; ++i) cin>>a[i];
quicksort(a,0,n-1);
int mid=(n-1)/2;
long long cp=0;
for (int i=0; i<mid; ++i)
cp=cp+(a[mid]-a[i]);
for (int i=mid+1; i<n; ++i)
cp=cp+(a[i]-a[mid]);
cout<<cp;
return 0;
}