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 Buggy Bot problem solution

YASH PAL, 31 July 2024
In this HackerEarth Buggy Bot problem solution, Alice finally finished her CS assignment and programmed her robot to explore a directed graph G with n nodes (numbered 1 through n) and m edges.
Alice programmed the robot with a series of k instructions. The robot will attempt to execute one instruction per second in the given order; it won’t repeat any instruction or return to an instruction it didn’t execute. Each instruction is of the form “if the robot is currently at node x, it will move to node y”. Note that if the robot is not currently at node x, it will ignore such an instruction. The robot is initially located at node 1.
Unfortunately, the robot is a bit buggy — at one moment in time, it can move from its current node to an arbitrary neighboring node (a node to which an edge leads from the current node). Note that this bug could have happened before any instructions, between any two instructions, or after all instructions; however, it couldn’t have happened multiple times. It is also possible that this bug did not happen at all.
Alice is having trouble debugging the robot, and would like your help to determine all nodes where the robot could be located at the end.
HackerEarth Buggy Bot problem solution

HackerEarth Buggy Bot problem solution.

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100010, MAXM = 1000010, MAXK = 1000010;

int n, m, k, ia[MAXK], ib[MAXK], pos[MAXK], ee[MAXN];
set<int> graph[MAXN], tmp[MAXN], ans;

int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 0, a, b; i < m; i++) {
scanf("%d%d", &a, &b);
graph[a].insert(b);
}

for (int i = 0; i < k; i++) {
scanf("%d%d", ia+i, ib+i);
}

pos[0] = 1;
int cp = 1;
for (int i = 0; i < k; i++) {
if (cp == ia[i]) cp = ib[i];
pos[i+1] = cp;
}

for (int i = 1; i <= n; i++) {
ee[i] = i;
}

ans.insert(pos[k]);
for (int i = k-1; i >= -1; i--) {
int cnode = pos[i+1];
for (int j : graph[cnode]) {
ans.insert(ee[j]);
tmp[j].insert(cnode);
}
graph[cnode].clear();

if (i >= 0) {
ee[ia[i]] = ee[ib[i]];
for (int j : tmp[ia[i]]) {
graph[j].insert(ia[i]);
}
tmp[ia[i]].clear();
}
}

printf("%dn", ans.size());
vector<int> xx(ans.begin(), ans.end());
sort(xx.begin(), xx.end());
for (int i = 0; i < ans.size(); i++) {
printf("%d%c", xx[i], " n"[i == ans.size() - 1]);
}
}
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