CHILLS - Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author: Smit Mandavia
Tester: Felipe Mota
Editorialist: Vichitr Gandas

DIFFICULTY:

EASY

PREREQUISITES:

Observation, Greedy, Median

PROBLEM:

Given a city with n houses. Each house is located at a distinct positive integer coordinate a_1, a_2, … a_n. The chef is planning to create k hills in the city. Note that two hills cannot be present at the same location but the location of hills and houses can overlap and each hill will also be at any real integer coordinate.
Each citizen would want to travel to the farthest hill from his house. Help the Chef find the minimum sum of distance traveled by everyone.

QUICK EXPLANATION:

The distance sum is minimum when the median of the hills is same as median of the houses and only the starting position of hills matter because the hills should be located with 1 unit distance to minimize the distance sum.

EXPLANATION:

Observations

  1. The distance sum is minimum when the median of the hills is same as median of the houses.
  2. Also we should place all hills nearby median hence placing them at unit distance is best choice.
  3. So only starting position of hills matters, other hills follow it by unit distances.

Solution

Now there can be two possible medians for the houses, which would be a[n/2] and a[(n-1)/2]. As we will place the hills at unit distances and want to make the medians same, we should match the left median of houses with left median of hills and right median of the houses with right median of the hills.
Hence for the median a[n/2], we will start placing the hills from a[n/2] - k/2 and for the median a[(n-1)/2], we will start placing the hills from a[(n-1)/2]-(k-1)/2.

Fun Fact: Both medians are always symmetric and both of them gives same answer.

Also if first hill is at position x, the last hill will be at position x+k-1 considering we are putting all hills continuously at unit distances. So i-th house citizen will travel D_i = max(abs(x-a[i]), abs(x+k-1-a[i]) distance to visit farthest hill.

Finally find sum of distances for any of two possible starting hill choices a[n/2] - k/2 and a[(n-1)/2]-(k-1)/2. As answer is always same for both choices.

Why only median choices are optimal

Consider all 4 cases and try to prove them —

  1. n and k both even
  2. n even and k odd
  3. n odd and k even
  4. n and k both odd

This way we can easily prove that, in all 4 cases, we will get the two median choices as a[n/2] and a[(n-1)/2].

TIME COMPLEXITY:

O(n) per test case

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>

# define pb push_back 
#define pii pair<int, int>
#define mp make_pair
# define ll long long int

using namespace std;
 
const int maxn = 1e5, maxk = 1e5, maxt = 10, maxv = 1e9, minv = 1;

int main()
{   
    int t; cin >> t;
    while(t--){
        int n, k; cin >> n >> k;
        int a[n + 1]; a[0] = 0;
        for(int i = 1; i <= n; i++)cin >> a[i];
        int l1 = -1, l2 = -1;
        if(n % 2 == 0){
            l1 = a[n / 2] - (k + 1) / 2 + 1;
            l2 = a[n / 2 + 1] - (k + 1) / 2 + (k % 2);
        }else{
            l1 = a[(n + 1) / 2] - (k + 1) / 2 + 1;
            l2 = a[(n + 1) / 2] - (k + 1) / 2 + (k % 2);
        }       
        ll val1 = 0, val2 = 0;
        for(int i = 1; i <= n; i++){
            val1 += max(abs(a[i] - l1), abs(a[i] - (l1 + k - 1)));
            val2 += max(abs(a[i] - l2), abs(a[i] - (l2 + k - 1)));
        }
        ll ans = min(val1, val2);
        cout << ans << endl;
    }
} 
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
long long TEN(int p){ long long r = 1; while(p--) r *= 10; return r; }
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = readIntLn(1, 10);
	while(t--){
		int n = readIntSp(1, TEN(5)), k = readIntLn(1, TEN(5));
		vector<int> a(n);
		for(int i = 0; i < n - 1; i++)
			a[i] = readIntSp(1, TEN(9));
		a[n - 1] = readIntLn(1, TEN(9));
		for(int i = 1; i < n; i++)
			assert(a[i - 1] < a[i]);
		vector<int> cand;
		cand.push_back(a[n / 2 - 1] - k / 2);
		cand.push_back(a[n / 2] - k / 2);
		long long ans = 1ll<<60;
		for(int c : cand){
			int l = c, r = c + k - 1;
			long long cur = 0;
			for(int i = 0; i < n; i++){
				cur += max(abs(a[i] - l), abs(a[i] - r));
			}
			ans = min(ans, cur);
		}
		cout << ans << '\n';
	}
	assert(getchar() == -1);
	return 0;
}
Editorialist's Solution
/***************************************************
 
@author: vichitr
Compiled On: 25 Apr 2021
 
*****************************************************/
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
 
using namespace std;
 
void solve(){
    int n, k; cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
 
    int m1 = a[n / 2] - k / 2;
    int m2 = a[(n - 1) / 2] - (k - 1) / 2;
 
    ll v1 = 0, v2 = 0;
   
    for(int i = 0; i < n; i++){
        int l = m1, r = m1 + k - 1;
        v1 += max(abs(a[i] - l), abs(a[i] - r));
        l = m2, r = m2 + k - 1;
        v2 += max(abs(a[i] - l), abs(a[i] - r));
    }
 
    ll ans = min(v1, v2);
    assert(v1 == v2);
    cout << ans << '\n';
}
 
signed main()
{
    int t = 1;
    cin >> t;
    for(int i = 1; i <= t; i++)
    {
        solve();
 
    }
    return 0;
}
6 Likes

In case you didn’t get this exact idea, here’s what I did.
By intuition, all the K hills should be consecutive so only starting hill matters.
Assume we put start hill at -10^9 and slowly move to 10^9
As we record the distance sum whilst moving, we can say, by intuition, it forms a \text{U-Shaped curve }.
Either extreme would give a large cost but somewhere in the middle will be optimum.
Hence ternary-search on start position!
Try implementing before seeing the code.

The code
void solve(){
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (int&x: v) cin >> x;
    auto f = [&](ll mid) {
        int start = mid;
        int end = mid + k - 1;
        ll c = 0;
        for (auto&x: v) {
            c += max(end - x, x - start);
        }
        return c;
    };
    ll lo = -1e9, hi = 1e9;
    while (hi - lo > 2) {
        // put all k consecutive and start point as mid;
        ll m1 = lo + (hi - lo)/3;
        ll m2 = hi - (hi - lo)/3;
        if (f(m1) < f(m2)) hi = m2;
        else lo = m1;
    }
    ll ans = INF;
    for (int i = lo; i <= hi; ++i) {
        ans = min(ans, f(i));
    }
    cout << ans << nl;
}
6 Likes

Ternary search is really a nice solution!!! Thanks for sharing @bennyjoseph!

1 Like

First time I also think ternary -search can work here… after see your comment now i am sure about that… thanks man
#sorry for poor English

Thank you, I was trying something like this too. Found my mistake. Really nice solution.

really great intution .i missed this first

why ternary search. can’t we use binary search