HackerRank Jim and his LAN Party problem solution

In this HackerRank Jim and his LAN Party problem solution During the Steam Summer Sale, Jim’s N – 1 friends have purchased games, which are numbered from 1 to M. The games are multiplayer. Jim has invited his friends to his basement where they will play by making a LAN-Party.

Each friend has already decided the game he would like to play for the rest of the day. So there will be a group of friends who will play the same game together.

But then, they face a problem: Currently, none of the friends’ PCs are connected. So they have to be connected using the available Q wires. Jim decides to connect friends ui and vi with the ith wire one by one. So he starts with wire 1, then with wire 2 and so on.

A group can start playing their game, only if all the members are connected (if not directly, then there must exist a path connecting them). They want to start playing as soon as possible.

For each game, find out the wire after adding which the group can start playing. It is also possible that a group will never get connected. In such a case, this group starts crying and you should display -1.

HackerRank Jim and his LAN Party problem solution in Python.

import sys

def read():
    l = sys.stdin.readline()
    if l[-1] == 'n': l = l[:-1]
    xs = filter(lambda x: len(x) > 0, l.split(' '))
    return map(int, xs)

n, m, q = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
    gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
    uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
    if len(gs[ix]) < 2:
        res.append(0)
    else:
        res.append(-1)

def find(x):
    if uf[x][0] == x:
        return x
    r = find(uf[x][0])
    uf[x][0] = r
    return r

def union(u, v, ix):
    ur = find(u)
    vr = find(v)
    ur, uh, us = uf[ur]
    vr, vh, vs = uf[vr]
    if uh > vh:
        uf[vr][0] = ur
        uf[ur][2] |= vs
        for g in vs:
            gs[g].discard(vr)
            gs[g].add(ur)
            if res[g] < 0 and len(gs[g]) == 1:
                res[g] = ix + 1
    elif vh > uh:
        uf[ur][0] = vr
        uf[vr][2] |= us
        for g in vs:
            gs[g].discard(ur)
            gs[g].add(vr)
            if res[g] < 0 and len(gs[g]) == 1:
                res[g] = ix + 1
    else:
        uf[vr][0] = ur
        uf[ur][1] += 1
        uf[ur][2] |= vs
        for g in vs:
            gs[g].discard(vr)
            gs[g].add(ur)
            if res[g] < 0 and len(gs[g]) == 1:
                res[g] = ix + 1

for ix in range(q):
    u, v = map(lambda x: x - 1, read())
    union(u, v, ix)
for r in res:
    print(r)

Jim and his LAN Party problem solution in Java.

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

public class Solution {
  
  static int find(int[] uf, int x) {
    while (uf[x] != x) {
      uf[x] = uf[uf[x]];
      x = uf[x];
    }
    return x;
  }
  
  static void iota(int v[], int val) {
    for (int i = 0; i < v.length; i++) {
      v[i] = val++;
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int q = Integer.parseInt(st.nextToken());

    Map<Integer, Integer>[] a = new HashMap[n];
    int[] cnt = new int[n];
    
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; i++) {
      int item = Integer.parseInt(st.nextToken()) - 1;
      a[i] = new HashMap<>();
      a[i].put(item, 1);
      cnt[item]++;

    }
    int[] result = new int[m];
    Arrays.fill(result, -1);
    for (int i = 0; i < m; i++) {
      if (cnt[i] <= 1) {
        result[i] = 0;
      }
    }
    int[] uf = new int[n];
    iota(uf, 0);
    

    for (int i = 0; i < q; i++) {
      st = new StringTokenizer(br.readLine());
      int u = Integer.parseInt(st.nextToken())-1;
      int v = Integer.parseInt(st.nextToken())-1;

      int uu = find(uf, u);
      int vv = find(uf, v);
      if (uu != vv) {
        if (a[uu].size() < a[vv].size()) {
          int temp = uu;
          uu = vv;
          vv = temp;
        }
        uf[vv] = uu;
        for (Map.Entry<Integer, Integer> x: a[vv].entrySet()) { 
          int t = a[uu].getOrDefault(x.getKey(), 0) + x.getValue();
          a[uu].put(x.getKey(), t);
          if (t == cnt[x.getKey()] && result[x.getKey()] == -1) {
            result[x.getKey()] = i+1;
          }
        }
      }
    }

    for (int i = 0; i < result.length; i++) {
      bw.write(String.valueOf(result[i]));

      if (i != result.length - 1) {
        bw.write("n");
      }
    }

    bw.newLine();

    bw.close();
    br.close();
  }
}

Problem solution in C++.

#include <iostream>
#include <vector>
using namespace std;
#define SZ(x) ( (int) (x).size() )
const int MAX_N = 100000 + 1;
int N, M, Q;
int color[MAX_N];
vector<int> cpos[MAX_N];
vector<int> q[MAX_N];
int qu[MAX_N], qv[MAX_N];
int lo[MAX_N], hi[MAX_N];
// implementation of UFDS
int f[MAX_N];
int getf(int x){
  return f[x] == x ? x : f[x] = getf(f[x]);
}
void mergef(int x, int y){
  f[getf(x)] = getf(y);
}
void initf(){
  for(int i = 1; i <= N; i++){
    f[i] = i;
  }
}

void reloadQueries(){
  for(int i = 0; i <= Q; i++){
    q[i].clear();
  }
  for(int i = 1; i <= M; i++){
    q[(lo[i] + hi[i]) / 2].push_back(i);
  }
}

void answerQuery(int c){
  bool connected = true;
  for(int i = 1; i < (int) cpos[c].size(); i++){
    connected &= getf(cpos[c][i]) == getf(cpos[c][i - 1]);
  }
  int mid = (lo[c] + hi[c]) / 2;
  if(!connected){
    lo[c] = mid + 1;
  } else {
    hi[c] = mid;
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin >> N >> M >> Q;
  for(int i = 1; i <= N; i++){
    cin >> color[i];
    cpos[color[i]].push_back(i);
  }
  for(int i = 1; i <= M; i++){
    lo[i] = 0, hi[i] = Q;
  }
  for(int i = 1; i <= Q; i++){
    cin >> qu[i] >> qv[i];
  }
  for(int times = 25; times >= 0; times --){
    initf();
    reloadQueries();
    for(int i = 0; i <= Q; i++){
      if(i > 0)
    mergef(qu[i], qv[i]);
      for(int j = 0; j < SZ(q[i]); j++){
    answerQuery(q[i][j]);
      }
    }
  }
  for(int i = 1; i <= M; i++){
    if(lo[i] > Q){
      cout << -1 << 'n';
    } else {
      cout << lo[i] << 'n';
    }
  }
  return 0;
}

Problem solution in C.

#include<stdio.h>
long findparent(long a, long connected[])
{
    if( connected[a] == a )
    {
        return a;
    }
    return findparent(connected[a], connected);
}
int checkparent(long arr[], long x, long N, long connected[])
{
    long i, val = arr[x], parent = findparent(x, connected);
    for( i = 1 ; i <= N ; i++ )
    {
        if( i != x && arr[i] == val && findparent(i, connected) != parent )
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    long N, M, Q, i, x, y, *arr, *connected, *step, *cnt, *cnt1, *ans, *par;
    scanf("%ld %ld %ld", &N, &M, &Q);
    arr = (long*)malloc(( N + 1 ) * sizeof(long));
    connected = (long*)malloc(( N + 1 ) * sizeof(long));
    memset(connected, 0, (N+1)*sizeof(cnt));
    step = (long*)malloc(( N + 1 ) * sizeof(long));
    memset(step, 0, (N+1)*sizeof(step));
    cnt = (long*)malloc(( M + 1 ) * sizeof(long));
    memset(cnt, 0, (M+1)*sizeof(cnt));
    cnt1 = (long*)malloc(( M + 1 ) * sizeof(long));
    memset(cnt1, 0, (M+1)*sizeof(cnt1));
    ans = (long*)malloc(( M + 1 ) * sizeof(long));
    memset(ans, -1, (M+1)*sizeof(ans));
    par = (long*)malloc(( M + 1 ) * sizeof(long));
    memset(par, -1, (M+1)*sizeof(par));
    for( i = 1 ; i <= N ; i++ )
    {
        scanf("%ld", &arr[i]);
        cnt[arr[i]]++;
    }
    for( i = 1 ; i <= Q ; i++ )
    {
        scanf("%ld %ld", &x, &y);
        if( connected[x] == 0 && connected[y] == 0 )
        {
            if( x < y )
            {
                connected[x] = x;
                connected[y] = x;
                par[arr[x]] = x;
                par[arr[y]] = x;
            }
            else
            {
                connected[x] = y;
                connected[y] = y;
                par[arr[x]] = y;
                par[arr[y]] = y;
            }
            cnt1[arr[x]]++;
            cnt1[arr[y]]++;
        }
        else if( connected[x] != 0 && connected[y] == 0 )
        {
            long parent = findparent(connected[x], connected);
            connected[y] = parent;
            cnt1[arr[y]]++;
            par[arr[y]] = parent;
        }
        else if( connected[x] == 0 && connected[y] != 0 )
        {
            long parent = findparent(connected[y], connected);
            connected[x] = parent;
            cnt1[arr[x]]++;
            par[arr[x]] = parent;
        }
        else
        {
            long parent = findparent(connected[y], connected);
            long parent1 = findparent(connected[x], connected);
            if( parent != parent1 && arr[x] == arr[y] && cnt[arr[x]] != -1 )
            {
                ans[arr[x]] = i;
            }
            step[parent1] = i;
            connected[parent1] = parent;
            par[arr[x]] = parent;
        }
        if( cnt1[arr[x]] == cnt[arr[x]] )
        {
            if( ans[arr[x]] == -1 )
            {
                ans[arr[x]] = i;
            }
        }
        if( cnt1[arr[x]] == cnt[arr[x]] && cnt[arr[x]] == 1 )
        {
            ans[arr[x]] = 0;
        }
        if( cnt1[arr[y]] == cnt[arr[y]] )
        {
            if( ans[arr[y]] == -1 )
            {
                ans[arr[y]] = i;
            }
        }
        if( cnt1[arr[y]] == cnt[arr[y]] && cnt[arr[y]] == 1 )
        {
            ans[arr[y]] = 0;
        }
    }
    for( i = 1 ; i <= N ; i++ )
    {
        int parent = findparent(i, connected);
        int parent1 = findparent(par[arr[i]], connected);
        if( par[arr[i]] != connected[i] )
        {
            if( parent1 == parent && step[par[arr[i]]] != 0 )
            {
                ans[arr[i]] = step[par[arr[i]]];
            }
            else if( parent1 == parent && step[connected[i]] != 0 )
            {
                ans[arr[i]] = step[connected[i]];
            }
            else if( parent1 != parent )
            {
                ans[arr[i]] = -1;
            }
        }
    }
    for( i = 1 ; i <= M ; i++ )
    {
        if( cnt[i] == 1 )
        {
            printf("%ldn", 0);
        }
        else
        {
            printf("%ldn", ans[i]);
        }
    }
    return 0;
}