Editorial - HALLALLOC

Problem link: Hall Allocation - Problems - CodeChef
Auth: picramide

We are interested in forming a happy room such that the minimum cgpa of students of that room is maximum.

So first we sort the pairs of friends (u, v) in decreasing order of min(CG_u, CG_v). Now we add the edges in our graph upto when a connected component of size k is formed and then output the minimum CGPA of students in that connected component. If no component of size k is formed then no happy room can exist.

This can be achieved by using disjoint set union data structure.

C++ Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

const ll N = 200005;
ll n, m, k;
ll cg[N];
pair<ll, ll> adj[N];

int parent[N], sz[N], mn[N];

void make_set(int x){
    parent[x] = x;
    sz[x] = 1;
    mn[x] = cg[x];

int find_set(int x){
    if(x == parent[x]) return x;
    return parent[x] = find_set(parent[x]);

void union_set(int a, int b){
    a = find_set(a); b = find_set(b);
    if(a == b) return;
    if(sz[a] < sz[b]) swap(a,b);
    parent[b] = a;
    mn[a] = min(mn[a], mn[b]);
    sz[a] += sz[b];

bool cmp(const pair<ll,ll> a, const pair<ll,ll> b){
    return min(cg[a.fr], cg[a.sc]) > min(cg[b.fr], cg[b.sc]);

void solve(){
    cin >> n >> m >> k;
    for (ll i = 0; i < n; ++i){
        cin >> cg[i + 1];
        make_set(i + 1);
    for (ll i = 0; i < m; ++i){
        cin >> adj[i].fr >> adj[i].sc;
    sort(adj, adj + m, cmp);
    for (ll i = 0; i < m; ++i){
        int a = find_set(adj[i].fr); int b = find_set(adj[i].sc);
        if(max(sz[a], sz[b]) >= k){
            cout << min(mn[a], mn[b]);
    cout << -1;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tt = 1; cin >> tt;
        cout << endl;
    return 0;
1 Like

You can solve this problem by binary search also.

1 Like