Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### Virtual_Contestant's blog

By Virtual_Contestant, history, 5 weeks ago, , Hello everyone, Can anyone just confirm how the graph of cost and the final height (same for all) would look like in this question? What I think is it would be unimodal function (having exactly one minima) but i don't know if it is correct. please tell me so i can edit. i just wanted to know just how graph of total cost for modifying all sticks to some particular same height would look like w.r.t to that height. please please help me https://cses.fi/problemset/task/1074 Comments (6)
»
5 weeks ago, # |
Rev. 2

Lets take an example of 3 sticks only:

$cost(x) = |x-x_0| + |x-x_1| + |x-x_2|$

Lets try to visualise how our cost function will change when x goes from $(-\infty, +\infty)$

$>$ denotes increasing

$<$ denotes decreasing

 Range $x$ $|x-x_0|$ $|x-x_1|$ $|x-x_2|$ $(-\infty, x_0)$ $<$ $<$ $<$ $(x_0, x_1)$ $>$ $<$ $<$ $(x_1, x_2)$ $>$ $>$ $<$ $(x_2, \infty)$ $>$ $>$ $>$
• We see that in every interval,
(number of increasing functions) $>=$ (number of inc functions in previous interval)
• Also, rate of increase for each function is also same (unit for every unit change of x)
• So the overall cost function decreases till count of decreasing functions > count of increasing functions, eventually hits a minima when counts become equal and then starts increasing again. Hence, $unimodal$.
•  » » thanks a lot so just to confirm i can use ternary search to calculate that final height for minimum cost right? i know there is a simple approach as well but i just thought to implement ternary search in a problem.
•  » » » you can just take the median of the array to be your final height as the median minimizes the sum of absolute difference.
•  » » » Yes, I solved it using ternary search
•  » » » » Can you please share the solution? it would be really helpful
•  » » » » » Ternary search approach#include using namespace std; #define int long long #define boost ios::sync_with_stdio(0);cin.tie(0) int n, m, x; vector lengths; int f(int x) { int cost = 0; for(int l: lengths) cost += abs(x-l); return cost; } int ternary_search_minima(int l, int r) { while(r-l > 3) { int m1 = l + (r-l)/3; int m2 = r - (r-l)/3; if(f(m1) < f(m2)) r = m2; else l = m1; } int minima = __LONG_LONG_MAX__; for(int i = l; i <=r ; i++) { minima = min(minima, f(i)); } return minima; } void purple() { cin >> n; for(int i = 0; i < n; i++) { cin >>x; lengths.push_back(x); } cout << ternary_search_minima(0, 10000000000000); } signed main() { boost; int t=1; while(t--) purple(); }