In this

**HackerEarth Friendly Neighbors problem solution**, HackerEarth City can be represented as an infinite number of houses standing next to each other and numerated starting with 1 from left to right. Recently n people have decided to move in HackerEarth City. They haven't decided which houses to accommodate yet, so they kindly asked for your help.You have n non-empty sets of positive integers S1,S2,...,Sn. The i-th person can live in any house from the set Si. You have to choose a house for each person. More formally, you have to create an array A1,A2,...,An such that for all i, Ai related to Si and Ai denotes the house of the i-th person.

Since all of them are close friends, they always attend their neighbor's birthdays. Let Bi denote the distance between i-th person and the closest neighbor to his left (some person j != i such that Aj < Ai and Aj is maximum). If he doesn't have any such neighbor, we say that Bi = 0. Let Ci equivalently denote the distance to the closest neighbor to his right.

You would like to create A1,A2,...,An in such a way that Sigma B + Sigma C is minimized.

Find and print the minimum possible value of Sigma B + Sigma C.

## HackerEarth Friendly Neighbors problem solution.

`#include<bits/stdc++.h>`

#define pb push_back

#define eb emplace_back

#define mp make_pair

#define fi first

#define se second

#define all(x) (x).begin(), (x).end()

#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

void solve() {

int n;

scanf("%d", &n);

vector<pii> T;

for (int i = 0; i < n; ++i) {

int k;

scanf("%d", &k);

for (int j = 0; j < k; ++j) {

int x;

scanf("%d", &x);

T.eb(x, i);

}

}

int m = (int)T.size();

sort(all(T));

vector<int> cnt(n, 0);

int distinct = 0;

int ans = (int)1e9;

int l = 0, r = 0;

// [l, r)

while (l < m) {

while (r < m && distinct < n) {

if (cnt[T[r].se]++ == 0) {

++distinct;

}

r++;

}

if (distinct == n) {

ans = min(ans, T[r - 1].fi - T[l].fi);

}

if (--cnt[T[l].se] == 0) {

--distinct;

}

l++;

}

printf("%d\n", ans * 2);

}

int main() {

int tt;

scanf("%d", &tt);

while (tt--) {

solve();

}

return 0;

}

### Second solution

`#include <bits/stdc++.h>`

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 14;

int mark[maxn];

int main(){

ios::sync_with_stdio(0), cin.tie(0);

int t;

cin >> t;

while(t--){

int n;

cin >> n;

fill(mark, mark + n, false);

map<int, int> mp;

for(int i = 0; i < n; i++){

int k;

cin >> k;

while(k--){

int x;

cin >> x;

mp[x] = i;

}

}

auto ptr = mp.begin();

int cnt = 0, ans = INT_MAX;

for(auto [x, i] : mp){

if(!mark[i]++)

cnt++;

if(cnt == n){

while(mark[ptr -> second] > 1){

mark[ptr -> second]--;

ptr++;

}

ans = min(ans, x - ptr -> first);

}

}

cout << ans << '\n';

}

}

## 0 Comments