Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth City and Campers problem solution

YASH PAL, 31 July 2024
In this HackerEarth City and Campers problem-solution “Money money MONEY, I want money” thought Alex. “Now how do I get money? Well… I’ll open up a camp!”
Well, unfortunately, things didn’t go so well for Alex’s campers, and now there are N campers wandering around the city aimlessly. You have to handle Q queries; which consist of two groups finding each other and becoming one larger group. After each query, output the difference between the group of largest size and group of smallest size. If there is only one group, output 0. At first, everyone is in their own group.
Also note, if the two campers in the query are already in the same group, print the current answer, and skip merging the groups together.
HackerEarth City and Campers problem solution

HackerEarth City and Campers problem solution.

#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
set <PII> keep;
int parent [100005];
int sz[100005];
int findset (int a)
{
if(parent[a]==0)return a;return parent[a]=findset(parent[a]);
}
void merge (int a,int b)
{
int k = findset(a), kk = findset(b);
if(k==kk)return;
parent[k]=kk;
keep.erase(PII(sz[kk], kk));
keep.erase(PII(sz[k], k));
sz[kk]+=sz[k];
keep.insert(PII(sz[kk],kk));
}
int main()
{
ios_base::sync_with_stdio(0);
int N, Q; cin >> N >> Q;
for (int g=1;g<=N;g++)keep.insert(PII(1, g)),sz[g]=1;
for (int g=0; g<Q; g++)
{
int a, b; cin >> a >> b;
merge(a, b);
set <PII> :: iterator ending = keep.end(); ending--;
set <PII> :: iterator beginning = keep.begin();
cout << (*ending).first-(*beginning).first << 'n';
}
return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5;
const int maxq = 1e5;
const int lim = 1e5 + 1;

struct cmp
{
bool operator() (const pair<int, int>& a, const pair<int, int>& b)
{
return a.second < b.second;
}
};

int n, q;
vector<int> parent(lim);
vector<int> size(lim);
multiset<pair<int, int>, cmp> S;

void init(int n)
{
for (int i = 1; i <= n; i++)
{
parent[i] = i;
size[i] = 1;
S.insert(make_pair(i, 1));
}
}

int ancestor(int a)
{
if (parent[a] != a)
parent[a] = ancestor(parent[a]);
return parent[a];
}

void merge(int a, int b)
{
a = ancestor(a);
b = ancestor(b);

if (a == b)
return;

if (size[b] > size[a])
swap(a, b);

S.erase(S.find(make_pair(a, size[a])));
S.erase(S.find(make_pair(b, size[b])));

size[a] += size[b];
parent[b] = a;

S.insert(make_pair(a, size[a]));
}

int main()
{
scanf("%d%d", &n, &q);

assert(1 <= n and n <= maxn);
assert(1 <= q and q <= maxq);

init(n);

for (int i = 0; i < q; i++)
{
int a, b;
scanf("%d%d", &a, &b);

assert(1 <= a and a <= n);
assert(1 <= b and b <= n);

merge(a, b);

int large = (*(S.rbegin())).second;
int small = (*(S.begin())).second;

printf("%dn", large - small);
}
return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes