Chef and Hills solution – Chefland is a 1D1D city where each of the NN houses

Chef and Hills solution

Chef and Hills solution

Chefland is a 1D1D city where each of the NN houses is located at a distinct positive integer coordinate A1,A2,ANA1,A2,…AN. The chef is planning to create KK 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 integer (positive, negative or zero) coordinate. Chef and Hills solution

Each citizen would want to travel to the farthest hill from his house. Travelling will create air pollution and Chef wants to minimise the total pollution in the city. Help Chef find the minimum sum of distance travelled by everyone. In other words, help Chef create the hills at optimal locations, so that the sum of the distance of every house to the hill farthest from it is minimum possible. Chef and Hills solution

Input: Chef and Hills solution

  • First line will contain TT, number of testcases. Then the testcases follow.
  • Each testcase contains two lines of input.
  • First line contains 22 integers N,KN,K separated by a space.
  • Second line contains NN integers A1,A2,,ANA1,A2,…,AN, representing the location of the houses.

Output: Chef and Hills solution

For each testcase, find the minimum possible sum of distances if Chef creates the hills at optimal locations, in a separate line.

Constraints Chef and Hills solution

  • 1T101≤T≤10
  • 1N,K1051≤N,K≤105
  • 1Ai1091≤Ai≤109
  • Ai<Ai+1Ai<Ai+1∀ valid ii

Sample Input: Chef and Hills solution

3
3 1
1 2 3
1 5
1
2 2
1 5

Sample Output: Chef and Hills solution

2
2
5

Chef and Hills solution

Explanation: Chef and Hills solution

TestCase 1: Optimal solution includes creating hill at 22. Its distance from the house at coordinate 11 is 11, and so is its distance from the house at coordinate 33. Its distance from the house at coordinate 22 is 00. Thus, total distance is 1+0+1=21+0+1=2.

TestCase 2: Optimal solution includes creating hills at {1,0,1,2,3}{−1,0,1,2,3}. The farthest hills from the house at coordinate 11 are at coordinates 1−1 and 33. The citizen can choose to travel to any of them, and the distance shall be 22.

TestCase 3: Optimal solution includes creating hills at {1,2}{1,2} or {4,5}{4,5}.

Chef and Hills solution

Program code: Chef and Hills solution

C++

#pragma GCC optimize("Ofast") 
#pragma GCC target("avx,avx2,fma") 
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order(k) returns iterator to kth element starting from 0
// order_of_key(k) returns count of elements strictly smaller than k
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
#define epsi (double)(0.00000000001)
typedef long long int ll;
typedef unsigned long long int ull;
#define vi vector<ll>
#define pii pair<ll,ll>
#define vii vector<pii>
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define min3(a,b,c) min(min(a,b),c)
#define max3(a,b,c) max(max(a,b),c)
#define ff(a,b,c) for(int a=b; a<=c; a++)
#define frev(a,b,c) for(int a=c; a>=b; a--)
#define REP(a,b,c) for(int a=b; a<c; a++)
#define pb push_back
#define mp make_pair
#define endl "\n"
#define all(v) v.begin(),v.end()
#define sz(a) (ll)a.size()
#define F first
#define S second
#define ld long double
//#define INF 2000000000000000000
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define ub upper_bound
#define lb lower_bound
#define setbits(x) __builtin_popcountll(x)
#define trav(a,x) for(auto &a:x)
#define make_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define rev(arr) reverse(all(arr))
#define gcd(a,b) __gcd(a,b);
#define ub upper_bound // '>'
#define lb lower_bound // '>='
#define qi queue<ll>
#define si stack<ll>

const long double PI = acos(-1);

mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}

bool prime[200001];
void SieveOfEratosthenes(){ 
memset(prime, true, sizeof(prime)); 
prime[1]=false;
for(ll p=2; p*p<=200000; p++){
if(prime[p] == true){
for (int i=p*p; i<=200000; i += p)
prime[i] = false;
}
}
return;
}

ll gcdExtended(ll a, ll b, ll *x, ll *y){
if(a == 0){
*x = 0;
*y = 1;
return b;
}
ll x1, y1;
ll gcd = gcdExtended(b%a, a, &x1, &y1);
*x = y1 - (b/a) * x1;
*y = x1;
return gcd;
}

ll modInverse(ll a, ll m){
ll x, y;
ll g = gcdExtended(a, m, &x, &y);
ll res = (x%m + m) % m;
return res;
}

ll binary_Search(vector<ll>&arr,ll key){
ll l=0,r=arr.size()-1;
ll ans;
while(l<=r){
ll mid=(l+r)/2;
ll value=arr[mid];
if(value>key){
r=mid-1;
}else if(value==key){
return mid;
}else{
l=mid+1;
}
}
return -1;
}

ll power(ll x,ll y,ll p){
ll res = 1;
x = x % p;
if (x == 0) return 0;
while (y > 0){ 
if (y & 1) 
res = (res*x) % p;
y = y>>1;
x = (x*x) % p;
}
return res;
}

const int N=1e5+5;
const ll INF=1e18;

void solve(){
int n,k;
cin >> n >> k;
vector<ll> v(n);
for(int i=0 ; i<n ; i++) cin >> v[i];
ll ans=0;
ll med=(n-1)/2;
for(int i=0 ; i<n ; i++){
if(n%2){
if(k%2){
ans+=max(abs(v[med]-k/2-v[i]),abs(v[med]+k/2-v[i]));
}else{
ans+=max(abs(v[med]-k/2+1-v[i]),abs(v[med]+k/2-v[i]));
}
}else{
if(k%2){
ans+=max(abs(v[med]-k/2-v[i]),abs(v[med]+k/2-v[i]));
}else{
ans+=max(abs(v[med]-k/2+1-v[i]),abs(v[med]+k/2-v[i]));
}
}
}
cout << ans << endl;
}

int main(){
fast;
//freopen ("auxiliary.in","r",stdin);
//freopen ("auxiliary.out","w",stdout);
int test=1;
cin >> test;
while(test--){
solve();
}
return 0;
}

JAVA

 

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb=new StringBuilder();
int t=Integer.parseInt(bu.readLine());
while(t-->0)
{
String s[]=bu.readLine().split(" ");
int n=Integer.parseInt(s[0]),k=Integer.parseInt(s[1]);
int a[]=new int[n],i;
s=bu.readLine().split(" ");
for(i=0;i<n;i++) a[i]=Integer.parseInt(s[i]);
ArrayList<Integer> mids=new ArrayList<>();
if(n%2==1) mids.add(a[n/2]);
else
{
int mp=a[(n-1)/2]+a[(n-1)/2+1];
if(mp%2==1) mids.add(mp/2);
else {mids.add(mp/2); mids.add(mp/2+1);}
}

long ans=Long.MAX_VALUE;
for(int x:mids)
{
int l=x,r=x,k2=k; k--;
while(k>=2)
{
l--; r++;
k-=2;
}
if(k==1)
{
ans=Math.min(ans,calculate(a,l-1,r));
ans=Math.min(calculate(a,l,r+1),ans);
}
else ans=Math.min(ans,calculate(a,l,r));
k=k2;
}
sb.append(ans+"\n");
}
System.out.print(sb);
}

static long calculate(int a[],int l,int r)
{
long ans=0;
for(int x:a)
ans+=Math.max(Math.abs(l-x),Math.abs(r-x));
return ans;
}
}

PYTHON

from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
m=a[n//2]
ans1=0
k-=1
k1=m+k//2+(k%2)
k2=m-k//2
for i in range(n//2+1):
ans1+=abs(a[i]-k1)
for i in range(n//2+1,n):
ans1+=abs(a[i]-k2)
ans2=0
k1=m+k//2
k2=m-k//2-(k%2)
for i in range(n//2):
ans2+=abs(a[i]-k1)
for i in range(n//2,n):
ans2+=abs(a[i]-k2)
# print(ans1,ans2)
print(min(ans1,ans2))

 

Chef and Hills solution

Also read : Flower Sequence solution codechef 2021 

Leave a Comment