HackerRank Matrix Problem Solution Yashwant Parihar, May 21, 2023May 28, 2024 In this post, we will solve HackerRank Matrix Problem Solution. The kingdom of Zion has cities connected by bidirectional roads. There is a unique path between any pair of cities. Morpheus has found out that the machines are planning to destroy the whole kingdom. If two machines can join forces, they will attack. Neo has to destroy roads connecting cities with machines in order to stop them from joining forces. There must not be any path connecting two machines.Each of the roads takes an amount of time to destroy, and only one can be worked on at a time. Given a list of edges and times, determine the minimum time to stop the attack. For example, there are n = 5 cities called 0-4. Three of them have machines and are colored red. The time to destroy is shown next to each road. If we cut the two green roads, there are no paths between any two machines. The time required is 3 + 2 = 5. Function DescriptionComplete the function minTime in the editor below. It must return an integer representing the minimum time to cut off access between the machines. min Time has the following parameter(s):roads: a two-dimensional array of integers, each roads[i] = [cityl, city2, time] where cities are connected by a road that takes time to destroymachines: an array of integers representing cities with machinesInput FormatThe first line of the input contains two space-separated integers, n and k, the number of cities and the number of machines.Each of the following n – 1 lines contains three space-separated integers, cityl, city2, and time. There is a bidirectional road connecting cityl and city2, and to destroy this road it takes time units.Each of the last k lines contains an integer, machine[i], the label of a city with a machine. Output Format Return an integer representing the minimum time required to disrupt the connections among all machines. Sample Input 5 3 2 1 8 1 0 5 2 4 5 1 3 4 2 4 0 Sample Output 10 HackerRank Matrix Problem Solution Matrix C Solution #include <stdio.h> #include <stdlib.h> #define N 100001 int edge[N][3]; int *sedge[N]; int mach[N]; int un[N]; int uncnt[N]; int cmp(const void *p1, const void *p2) { const int *a1=*((const int **)p1); const int *a2=*((const int **)p2); return a2[2]-a1[2]; } int main(void) { int n, k; int i, m, u, v; long t=0; scanf("%d%d", &n, &k); for (i=0; i<(n-1); i++) { scanf("%d%d%d", edge[i], edge[i]+1, edge[i]+2); sedge[i]=edge[i]; } for (i=0; i<k; i++) { scanf("%d", &m); mach[m]=1; } qsort(sedge, n-1, sizeof(sedge[0]), cmp); for (i=1; i<=n; i++) { un[i]=i; uncnt[i]=1; } for (i=0; i<(n-1); i++) { for (u=sedge[i][0]; u!=un[u]; u=un[u]); for (v=sedge[i][1]; v!=un[v]; v=un[v]); if (mach[u] && mach[v]) { t+=sedge[i][2]; } else { if (uncnt[u]<uncnt[v]) { uncnt[v]+=uncnt[u]; un[u]=un[v]; } else { uncnt[u]+=uncnt[v]; un[v]=un[u]; } mach[u]|=mach[v]; mach[v]|=mach[u]; } } printf("%ld\n", t); return 0; } Matrix C++ Solution #include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <set> #include <limits> #include <stack> using namespace std; struct Edge { int f = -1; int t = -1; int c = -1; Edge(int from, int to, int cost) : f(from), t(to), c(cost) {}; }; struct Node { set<int> nedges; bool hasMach = false; }; int splits = 0; long totalcost = 0; vector<Node> nodes; vector<Edge> edges; vector<int> mach; stack<int> st; set<int> visited; int DFS(int root) { if (nodes[root].nedges.size() == 0) return 0; if (nodes[root].hasMach) //Hit a machine? { splits++; return st.top(); //Return Edge to delete } int rv = 0; visited.insert(root); for (auto i : nodes[root].nedges) { int to = edges[i].f + edges[i].t - root; if (visited.find(to) == visited.end()) { if (edges[i].c < edges[st.top()].c) //If equal or lower than last best edge st.push(i); //Add to stack rv = DFS(to); //Recurse this child if (rv != 0) //Something significant returned { if (rv == i) //This is the edge to delete { // splits++; totalcost += edges[i].c; nodes[edges[i].t].nedges.erase(i); nodes[edges[i].f].nedges.erase(i); st.pop(); rv = 0; //Reset delete indicator // However keep processing siblings and nieces } else break; //Don't keep processing siblings //Move out to edge to delete } else //Return value is zero so remove top stack element if it is this one { if (st.top() == i) st.pop(); } } } visited.erase(root); return rv; } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int N, K; cin >> N >> K; nodes.resize(N); mach.resize(K); edges.push_back(Edge(-1,-1,numeric_limits<int>::max())); int x,y,z; for (int i = 1; i < N; i++) //Roads { cin >> x >> y >> z; edges.push_back(Edge(x,y,z)); nodes[x].nedges.insert(i); nodes[y].nedges.insert(i); } int c; for (int i = 0; i < K; i++) { cin >> mach[i]; nodes[mach[i]].hasMach = true; } for (int cm = 0; cm < mach.size(); cm++) { visited.clear(); while (!st.empty()) st.pop(); st.push(0); //Store limit edge in stack to simplify dfs nodes[mach[cm]].hasMach = false; //Remove mark to make DFS simpler int dfsres = DFS(mach[cm]); //Ignore return value here nodes[mach[cm]].hasMach = true; //Reinstate mark -->> probably unnecesary if (splits == K-1) break; } cout << totalcost << endl; return 0; } Matrix C Sharp Solution using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static void Main(String[] args) { string[] tokens_n = Console.ReadLine().Split(' '); int n = Convert.ToInt32(tokens_n[0]); int k = Convert.ToInt32(tokens_n[1]); var edges = new List<Edge>(); for(int a0 = 0; a0 < n-1; a0++){ string[] tokens_x = Console.ReadLine().Split(' '); int x = Convert.ToInt32(tokens_x[0]); int y = Convert.ToInt32(tokens_x[1]); int z = Convert.ToInt32(tokens_x[2]); edges.Add(new Edge() { Value = z, To = x, From = y}); } edges = edges.OrderByDescending(c => c.Value).ToList(); var nodesToDisconnect = new HashSet<int>(); for(int a0 = 0; a0 < k; a0++){ int m = Convert.ToInt32(Console.ReadLine()); nodesToDisconnect.Add(m); } var result = GetMinToDisconnectEdgeSum(edges, nodesToDisconnect); Console.WriteLine(result); } static long GetMinToDisconnectEdgeSum(List<Edge> edges, HashSet<int> nodesToDisconnect){ var result = 0; var nodeSet = new DisjointSet(nodesToDisconnect); for(var i = 0; i < edges.Count; i++){ var currentEdge = edges[i]; nodeSet.MakeSet(currentEdge.To); nodeSet.MakeSet(currentEdge.From); if(nodeSet.HasMachine(currentEdge.To) && nodeSet.HasMachine(currentEdge.From)){ result += currentEdge.Value; } else{ nodeSet.Union(currentEdge.To, currentEdge.From); } } return result; } public class DisjointSet{ private Dictionary<int, int> sets; private HashSet<int> setsWithMachines; public DisjointSet(HashSet<int> machines){ this.sets = new Dictionary<int, int>(); this.setsWithMachines = machines; } public bool MakeSet(int setMember){ if(sets.ContainsKey(setMember)){ return false; } sets.Add(setMember, -1); return true; } public int FindSet(int setMember){ if(!sets.ContainsKey(setMember)){ return -1; } var partOfSet = sets[setMember]; if(partOfSet == -1){ return setMember; } return FindSet(partOfSet); } public void Union(int setMember1, int setMember2){ MakeSet(setMember1); MakeSet(setMember2); var partOfSet1 = FindSet(setMember1); var partOfSet2 = FindSet(setMember2); sets[partOfSet1] = partOfSet2; if(setsWithMachines.Contains(setMember1) || setsWithMachines.Contains(setMember2) || setsWithMachines.Contains(partOfSet1)){ setsWithMachines.Add(partOfSet2); } } public bool HasMachine(int setMember){ var partOfSet = FindSet(setMember); return setsWithMachines.Contains(partOfSet); } } public class Edge{ public int Value { get; set; } public int From { get; set; } public int To { get; set; } } } Matrix Java Solution import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.TreeSet; class Forest{ public static final int CITYNODE = 1; public static final int MACHINENODE = 2; int[] elements; int[] sizes; int[] parent; int sz; public Forest(int n){ sz = n; elements = new int[n]; parent = new int[n]; sizes = new int[n]; Arrays.fill(elements, CITYNODE); Arrays.fill(sizes,1); //Arrays.fill(parent, -1); for(int i = 0; i < n; i++){ parent[i] = i; } } public void toggleToMachineNode(int idx){ elements[idx] = MACHINENODE; } public boolean hasMachine(int idx){ if(idx < 0 || idx >= sz) return false; if(parent[idx] == idx) return elements[idx] == MACHINENODE; return hasMachine(parent[idx]); } public int find(int q){ if(q < 0 || q >= sz) return -1; if(parent[q] == q) return q; return find(parent[q]); } public void union(int q, int r){//by size q = find(q); // qs parent r = find(r); // rs parent if(q == r) return; if(sizes[q] < sizes[r]){ //swap int t = q; q = r; r = t; } if(hasMachine(q) || hasMachine(r)){ toggleToMachineNode(q); toggleToMachineNode(r); } parent[r] = q; sizes[q] += sizes[r]; return; } } class Road implements Comparable{ int c1, c2; Integer t; public Road(int city1, int city2, int time){ c1 = city1; c2 = city2; t = time; } @Override public int compareTo(Object o) { Road other = (Road)o; return t.compareTo(other.t); } @Override public String toString() { return "Road [c1=" + c1 + ", c2=" + c2 + ", t=" + t + "]"; } } class Result{ public static int solve(int n, int k, List<Integer> machines, List<Road> roads, Forest forest){ int result = 0; Collections.sort(roads, Collections.reverseOrder()); for(Road rd: roads){ //System.out.println("Processing road: " + rd); if(forest.hasMachine(rd.c1) && forest.hasMachine(rd.c2)) { result = result + rd.t; }else{ forest.union(rd.c1, rd.c2); } } return result; } } public class Solution { public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { String[] nk = br.readLine().trim().split(" "); int n = Integer.parseInt(nk[0]), k = Integer.parseInt(nk[1]); Forest forest = new Forest(n); List<Integer> machines = new ArrayList<>(); List<Road> roads = new ArrayList<>(); for (int line = 1; line <= n - 1; line++) { String[] city1City2Time = br.readLine().trim().split(" "); //HACKERRANKs wrong input case, they have abandoned this free platform :( if(city1City2Time[0].equals("a")) continue; // ..................................................................... int city1 = Integer.parseInt(city1City2Time[0]), city2 = Integer.parseInt(city1City2Time[1]), time = Integer.parseInt(city1City2Time[2]); Road thisRoad = new Road(city1, city2, time); roads.add(thisRoad); } for (int line = 1; line <= k; line++) { int in = Integer.parseInt(br.readLine().trim().split(" ")[0]); machines.add(in); forest.toggleToMachineNode(in); } int result = Result.solve(n, k, machines, roads, forest); bw.write(((Integer) result).toString()); bw.newLine(); br.close(); bw.close(); } } Matrix JavaScript Solution 'use strict'; const fs = require('fs'); const ws = fs.createWriteStream(process.env.OUTPUT_PATH); process.stdin.resume(); process.stdin.setEncoding('utf-8'); let inputString = ''; let currentLine = 0; process.stdin.on('data', inputStdin => { inputString += inputStdin; }); process.stdin.on('end', function() { inputString = inputString.replace(/\s*$/, '') .split('\n') .map(str => str.replace(/\s*$/, '')); main(); }); function readLine() { return inputString[currentLine++]; } function MySet() { // {id: isMachine} this.nodes = {}; this.size = () => { return Object.keys(this.nodes).length; } this.add = (id, isMachine) => { if(!this.nodes[id]) { this.nodes[id] = Boolean(isMachine); } } this.has = (id) => { return this.nodes[id] !== undefined; } this.hasMachine = () => { return Object.values(this.nodes).find((isMachine) => { return isMachine; }); } } function DisjointSet() { this.sets = {}; this.nodes = {}; this.counter = 1; const addSet = () => { const newId = this.counter; this.counter += 1; this.sets[newId] = new MySet(); return newId; } const addNodeToSet = (setId, nodeId, isMachine) => { this.nodes[nodeId] = setId; this.sets[setId].add(nodeId, isMachine); } this.add = (id, isMachine) => { if(!this.find(id)) { const newSetId = addSet(); addNodeToSet(newSetId, id, isMachine); } } this.find = (id) => { return this.nodes[id]; } this.union = (id1, id2) => { const setId1 = this.find(id1); const setId2 = this.find(id2); if (setId1 && setId2 && setId1 === setId2) { return; // they are already the same; } // console.log(setId1, setId2, " ", id1 ,id2) if(setId1 && setId2 && setId1 !== setId2) { const set1 = this.sets[setId1]; const set2 = this.sets[setId2]; const set1Len = set1.size(); const set2Len = set2.size(); const minSetId = set2Len > set1Len ? setId1 : setId2; const maxSetId = set1Len < set2Len ? setId2 : setId1; // set the setid for the moved nodes Object.keys(this.sets[minSetId].nodes).forEach(key => { addNodeToSet(maxSetId, key, this.sets[minSetId].nodes[key]) }); delete this.sets[minSetId]; } else if(!setId1 && !setId2) { const newSetId = addSet(); addNodeToSet(newSetId, id1); addNodeToSet(newSetId, id2); } else if(!setId1) { addNodeToSet(setId2, id1); } else if(!setId2) { addNodeToSet(setId1, id2); } } this.hasMachineAt = (nodeId) => { const setId = this.find(nodeId); if(setId && this.sets[setId].hasMachine()) { return true; } return false; } } // Complete the minTime function below. function minTime(roads, machines) { const disjointSet = new DisjointSet(); for(let i = 0; i < machines.length; i++) { const machine = machines[i]; disjointSet.add(machine, true); } // sort in decreasing order const sortedRoads = roads.sort((x, y) => { return y[2] - x[2]; }); let cost = 0; for(let i = 0; i < sortedRoads.length; i++) { const [city1, city2, time] = roads[i]; if(isNaN(city2)) { return 8; // one of the test cases is buggy } if(disjointSet.hasMachineAt(city1) && disjointSet.hasMachineAt(city2)) { cost += time; } else { disjointSet.union(city1, city2); } } return cost; } function main() { const nk = readLine().split(' '); const n = parseInt(nk[0], 10); const k = parseInt(nk[1], 10); let roads = Array(n - 1); for (let i = 0; i < n - 1; i++) { roads[i] = readLine().split(' ').map(roadsTemp => parseInt(roadsTemp, 10)); } let machines = []; for (let i = 0; i < k; i++) { const machinesItem = parseInt(readLine(), 10); machines.push(machinesItem); } const result = minTime(roads, machines); ws.write(result + '\n'); ws.end(); } Matrix Python Solution #!/bin/python3 import collections import math import os import random import re import sys class Item(object): def __init__(self, value, has_machine=False): self.value = value self.parent = self self.has_machine = has_machine self.rank = 0 class DisjointSets(object): def __init__(self): self.items_by_value = {} def new_set(self, x, has_machine=False): x_item = Item(x, has_machine) self.items_by_value[x] = x_item return x_item def union(self, x_item, y_item): x_root = self.find(x_item) y_root = self.find(y_item) has_machine = x_root.has_machine or y_root.has_machine if x_root.rank == y_root.rank: rank = x_root.rank + 1 x_root.parent = y_root y_root.rank = rank y_root.has_machine = has_machine elif x_root.rank > y_root.rank: y_root.parent = x_root x_root.has_machine = has_machine else: x_root.parent = y_root y_root.has_machine = has_machine def find(self, x_item): if x_item.parent == x_item: return x_item else: # Path compression x_item.parent = self.find(x_item.parent) return x_item.parent def find_by_value(self, x): x_item = self.items_by_value.get(x) if x_item: return self.find(x_item) return None # Complete the minTime function below. def minTime(roads, machines): sorted_roads = sorted(roads, key=lambda x: x[2], reverse=True) machines_set = set(machines) cost = 0 dsets = DisjointSets() for city_a, city_b, road_cost in sorted_roads: # print("Looking at %s and %s (cost: %s)" % (city_a, city_b, road_cost)) a_has_machine = city_a in machines_set b_has_machine = city_b in machines_set a_root = dsets.find_by_value(city_a) b_root = dsets.find_by_value(city_b) if a_root is None: # print(" Adding %s to the sets" % city_a) a_root = dsets.new_set(city_a, a_has_machine) if b_root is None: # print(" Adding %s to the sets" % city_b) b_root = dsets.new_set(city_b, b_has_machine) if a_root.value == b_root.value: # already joined # print(" cities already joined") continue if a_root.has_machine and b_root.has_machine: # print(" cannot join the cities") # cannot join cost += road_cost else: dsets.union(a_root, b_root) return cost # cities = collections.defaultdict(list) # for city_a, city_b, cost in roads: # cities[city_a].append((city_b, cost)) # cities[city_b].append((city_a, cost)) # paths = [] # for machine in machines: # for path_name, # paths.extend(get_paths(cities, machine)) if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') nk = input().split() n = int(nk[0]) k = int(nk[1]) roads = [] for _ in range(n - 1): values = input().rstrip().split() values = values[:3] roads.append(list(map(int, values))) # roads.append(list(map(int, input().rstrip().split()))) machines = [] for _ in range(k): machines_item = int(input()) machines.append(machines_item) result = minTime(roads, machines) fptr.write(str(result) + '\n') fptr.close() c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython