CSES: Will the graph be unimodal?

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
37:16:56
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

View all →

→ Find user

→ Recent actions

Detailed →

Virtual_Contestant's blog

CSES: Will the graph be unimodal?

By Virtual_Contestant, history, 4 years ago, In English

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

Virtual_Contestant
4 years ago
6

Comments (6)

Write comment?

Jon.Snow

4 years ago, # |

← Rev. 2 →

+11

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$$$.

→ Reply

Virtual_Contestant

4 years ago, # ^ |

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.

→ Reply

killer4639

4 years ago, # ^ |

you can just take the median of the array to be your final height as the median minimizes the sum of absolute difference.

→ Reply

Jon.Snow

4 years ago, # ^ |

Yes, I solved it using ternary search

→ Reply

Virtual_Contestant

4 years ago, # ^ |

Can you please share the solution? it would be really helpful

→ Reply

Jon.Snow

4 years ago, # ^ |

Ternary search approach

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define boost ios::sync_with_stdio(0);cin.tie(0)
 
int n, m, x;
vector<int> 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();
}

→ Reply