HackerEarth Gears in a machine problem solution

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.

#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";
    }

HackerEarth Gears in a machine problem solution

HackerEarth Gears in a machine problem solution.

Second solution

Leave a Reply

Pages

Practice