Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • 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
Programming101
Programming101

Learn everything about programming

HackerEarth Handshakes in a party problem solution

YASH PAL, 31 July 2024
In this HackerEarth Handshakes in a party problem solution, You are organizing a new year’s party and you have invited a lot of guests. Now, you want each of the guests to handshake with every other guest to make the party interactive. Your task is to know what will be the minimum time by which every guest meets others. One person can handshake with only one other person at once following the handshake should be of 3 seconds sharp.
You have prepared some data for each guest which is the order in which the Guest(i) will meet others. If the data is inconsistent, then print -1. Otherwise, print the minimum time in seconds.
HackerEarth Handshakes in a party problem solution

HackerEarth Handshakes in a party problem solution.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1010;

int n;
int id[maxn][maxn];
int k = 1;

vector<int> g[maxn*maxn];
int indeg[maxn*maxn];

int tot;

int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n;
tot=n*(n-1)/2;

for (int i=0; i<n; i++) {
int prev = 0;
for (int j=1; j<n; j++) {
int x;
cin>>x;
--x;

// assign a unique id to the G(i)-G(x) handshake
if (!id[i][x]) {
id[i][x]=id[x][i] = k;
k++;
}

// create handshake sequence graph
if (prev) {
g[prev].push_back(id[i][x]);
indeg[id[i][x]]++;
}
prev = id[i][x];
}
}


// add all handshakes which doesn't need prior handshake as source nodes in queue.
queue<int> Q;
int count = 0;
for (int i=1; i<k; i++) {
if (indeg[i]==0) {
Q.push(i);
count++;
}
}

ll seconds=0;
// multi-point BFS to traverse and visit every node in directed graph
while(!Q.empty()) {
int len = Q.size();
queue<int> nQ;
while(!Q.empty()) {
int front_node = Q.front();
Q.pop();
for (int x: g[front_node]) {
if (--indeg[x] == 0) {
nQ.push(x);
count++;
}
}
}
Q = nQ;
seconds++;
}

// count denotes the number of visited nodes in the graph
// if the visited nodes are equal to total handshakes in the party, then the data is valid
if (count == tot)
cout << seconds*3 << endl;
else
cout << -1 << endl;
return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e3 + 14;
vector<int> g[N * N];
int id[N][N], in[N * N], d[N * N];

int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
int cnt = 0;
for (int i = 0; i < n; ++i) {
int p = -1;
for (int j = 0; j < n - 1; ++j) {
int o;
cin >> o;
--o;
if (!id[i][o])
id[i][o] = id[o][i] = cnt++;
if (p != -1) {
g[id[i][o]].push_back(p);
++in[p];
}
p = id[i][o];
}
}
memset(d, 63, sizeof d);
queue<int> q;
for (int i = 0; i < cnt; ++i)
if (!in[i]) {
d[i] = 0;
q.push(i);
}
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto u : g[v])
if (!--in[u]) {
d[u] = d[v] + 1;
q.push(u);
}
}
int ans = *max_element(d, d + cnt);
cout << (ans > 1e9 ? -1 : ans * 3 + 3);
}
coding problems

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

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
©2025 Programming101 | WordPress Theme by SuperbThemes