### arius1408's blog

By arius1408, history, 7 weeks ago,

While I'm doing problems on CSES like always, I met with a rather interesting problem : CSES-Stick Lengths. After solving it, I discover there was actually atleast 3 ways to do this problem (all in O(NlogN)): the one I used to AC, other one using Ternary Search, and finally, using a prominent solution that I saw others used. The idea for the third was short : You sort the whole array, take the median (N/2) as the target value and calculate the result using it. Here it how it goes on USACO :

#include <bits/stdc++.h>

using namespace std;

//variables used for the current problem
int n,median;
vector<int> p;
long long ans,cnt;

void solve() {
cin >> n;
p.resize(n);
for (int &x : p){
cin >> x;
}
sort(p.begin(),p.end());
median=p[n/2];
for (const int &x : p){
ans+=abs(median-x); //Calculate the cost to modify the stick length
}
cout << ans << "\n";
return;
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}


After a while of observation, I myself must admit the solution's correctness. But I just couldn't proof it. Can you guys help me with it ?

• 0

 » 7 weeks ago, # |   0 This should help :)
•  » » 7 weeks ago, # ^ |   0 Uh ... I don't think so. At first, I thought there was something related between this problem and the proof for CSES Stick Lengths so I solved it. After that, I still couldn't see the relation. I looked at the editorial, just to be sure, but the solution offered by the author is still unrelated (at least from my point of view). It seem I'm missing something here. Do you mind explain some more ? Sorry but I'm just plain dumb ...
•  » » » 7 weeks ago, # ^ |   0 You can see the exact proof from Stackoverflow
•  » » » » 7 weeks ago, # ^ |   0 Oh nice, thank you very much. Have a good day sir ^_^ !!!