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


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';
}
}