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
- The distance sum is minimum when the median of the hills is same as median of the houses.
- Also we should place all hills nearby median hence placing them at unit distance is best choice.
- 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 —
- n and k both even
- n even and k odd
- n odd and k even
- 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;
}