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 Gears in a machine problem solution

YASH PAL, 31 July 2024
In this HackerEarth Gears in a machine problem solution Alice and Bob are working on a new contraption to make the most of their extended summer vacations. However, they ran into some trouble with the mechanics of their machine, specifically, in the gear trains. The complicated meshing of gears has confused them and they require your help to make it functional.
A gear train is a network of gears that are engaged with each other. Mechanically, two gears are said to be engaged or connected if some segment of their teeth interlocks, so that rotating gear forces the rotation of the other gear. This mechanism forces all gears that are engaged with the latter gear to rotate and this motion propagates throughout the train. This type of network can be described in terms of a graph where each vertex represents a gear and an edge denotes that two gears are engaged. 
There are two types of gears, internal and external. The types of gears depend on which region their teeth are present. Note that all gears are fixed to their position.
HackerEarth Gears in a machine problem solution

HackerEarth Gears in a machine problem solution.

#include <bits/stdc++.h>

#define vi vector<int>
#define pb push_back

using namespace std;

vi colour, gear_type, conn_comp;
vector<vi> AdjList;

bool bipartite_check (int source, int comp_no)
{
int node, i, to_ret=true;
queue <int> q;
q.push(source);
colour[source]=1;
while (!q.empty())
{
node=q.front();
conn_comp[node]=comp_no;
q.pop();
for (i=0; i<AdjList[node].size(); i++)
{
if (colour[AdjList[node][i]]==0)
{
colour[AdjList[node][i]]=-(gear_type[node]*gear_type[AdjList[node][i]])*colour[node];
q.push(AdjList[node][i]);
}
else
if (colour[AdjList[node][i]]==(gear_type[node]*gear_type[AdjList[node][i]])*colour[node])
to_ret=false;
}
}
return to_ret;
}

void mark_stuck(int node)
{
int i;
colour[node]=-2;
for (i=0; i<AdjList[node].size(); i++)
if (colour[AdjList[node][i]]!=-2)
mark_stuck(AdjList[node][i]);
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int n, m, q, i, u, v, gp, dirp, gf, dirf, comp_no=1;

cin>>n>>m>>q;

gear_type=colour=conn_comp=vi(n+1);
AdjList=vector<vi>(n+1);

for (i=1; i<=n; i++)
cin>>gear_type[i];

for (i=0; i<m; i++)
{
cin>>u>>v;
AdjList[u].pb(v);
AdjList[v].pb(u);
}

for (i=1; i<=n; i++)
if (colour[i]==0)
if (!bipartite_check(i, comp_no++))
mark_stuck(i);

while (q--)
{
cin>>gp>>gf>>dirp>>dirf;
if (colour[gp]==-2 || colour[gf]==-2)
cout<<"NOn";
else if (conn_comp[gp]!=conn_comp[gf] || (colour[gp]==colour[gf])==(dirp==dirf))
cout<<"YESn";
else
cout<<"NOn";
}
}

Second solution

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 14;

int n, m, q, col[maxn], gpc, gp[maxn], wh[maxn];
vector<int> g[maxn];
bool check(int v, int c = 1){
if(col[v])
return col[v] == c;
gp[v] = gpc;
col[v] = c;
for(auto u : g[v])
if(!check(u, wh[v] == wh[u] ? 3 - c : c))
return false;
return true;
}
void spread(int v){
if(col[v] == 3)
return ;
col[v] = 3;
for(auto u : g[v])
spread(u);
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> q;
for(int i = 0; i < n; i++)
cin >> wh[i];
for(int i = 0; i < m; i++){
int v, u;
cin >> v >> u;
v--, u--;
g[v].push_back(u);
g[u].push_back(v);
}
for(int i = 0; i < n; i++)
if(!col[i]){
if(!check(i))
spread(i);
gpc++;
}
while(q--){
int v, u, d, e;
cin >> v >> u >> d >> e;
v--, u--;
if(col[v] == 3 || col[u] == 3 || gp[v] == gp[u] && (col[v] == col[u]) != (d == e))
cout << "NOn";
else
cout << "YESn";
}

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