HackerEarth Friendly Neighbors problem solution

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("%dn", 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';
    }
}

HackerEarth Friendly Neighbors problem solution

HackerEarth Friendly Neighbors problem solution.

Second solution

Leave a Reply

Pages

Practice