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