Answered by:
HackerRank  Roads and Libraries  Getting wrong answer in some test cases
Question

My approach:
According to the problem we have to minimize the cost to repair the lib and the roads. So what I did was if the cost of repairing the lib is <= cost of repairing the roads then I just simply return (numberOfCities * costOfRepairingLib). Otherwise I count the no of connected components and the no of roads to be repaired then I calculated the cost and return it.
And I'm unable to pass 4, 5, 6, 8, 9 and 10 test cases and the test cases are so huge that I can't even debug. Please see where I did the mistake.
The logic feels fine to me but its failing for large test cases even I change every data type to long. I'm really stuck on this.class Solution { // Complete the roadsAndLibraries function below. static long roadsAndLibraries(long n, long c_lib, long c_road, long[][] cities) { if(c_lib <= c_road  c_road == 0) return c_lib * n; long[,] adjacentMatrix = new long[n, n]; Stack<long> stack = new Stack<long>(); Dictionary<long, bool> notVisited = new Dictionary<long, bool>(); Dictionary<long, bool> visited = new Dictionary<long, bool>(); for(long i = 1; i <= n; i++){ notVisited[i] = false; } foreach(var city in cities){ adjacentMatrix[city[0]  1,city[1] 1] = 1; adjacentMatrix[city[1]  1,city[0]  1] = 1; } long noOfCycles = 0; long noOfRoads = 0; while(notVisited.Count > 0){ stack.Push(notVisited.ElementAt(0).Key); visited.Add(stack.Peek(), true); notVisited.Remove(notVisited.ElementAt(0).Key); noOfCycles++; while(stack.Count > 0){ long top = stack.Pop(); for(long i = 0; i < n; i++){ if(adjacentMatrix[top  1, i] == 1 && !visited.ContainsKey(i + 1)){ visited.Add(i + 1, true); noOfRoads++; stack.Push(i + 1); notVisited.Remove(i + 1); } } } } return (noOfCycles * c_lib) + (noOfRoads * c_road); } static void Main(string[] args) { TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true); long q = Convert.ToInt64(Console.ReadLine()); for (long qItr = 0; qItr < q; qItr++) { string[] nmC_libC_road = Console.ReadLine().Split(' '); long n = Convert.ToInt64(nmC_libC_road[0]); long m = Convert.ToInt64(nmC_libC_road[1]); long c_lib = Convert.ToInt64(nmC_libC_road[2]); long c_road = Convert.ToInt64(nmC_libC_road[3]); long[][] cities = new long[m][]; for (long i = 0; i < m; i++) { cities[i] = Array.ConvertAll(Console.ReadLine().Split(' '), citiesTemp => Convert.ToInt64(citiesTemp)); } long result = roadsAndLibraries(n, c_lib, c_road, cities); textWriter.WriteLine(result); } textWriter.Flush(); textWriter.Close(); } }
Friday, August 23, 2019 5:22 AM
Answers

So I found out what was going wrong with my code
My logic was totally correct the thing where I wasn't able to guess what was happening is that HACKERRANK handles OutOfMemoryException badly, they show wrong answer instead of showing that exception. So I changed my code to improve the time complexity.
So what I did is:#1. I removed the two dictionaries (visited and notVisited) and added a visited array instead as the array lookup will be quicker because a dictionary lookup is two operations: calculate the hash of the key to get an index and retrieve the value from an internal array at that index.
#2. Used adjacency list instead of adjacency matrix.
CODE:class Solution { // Complete the roadsAndLibraries function below. static long roadsAndLibraries(long n, long c_lib, long c_road, long[][] cities) { if(c_lib <= c_road  cities.Length == 0) return c_lib * n; long[,] adjacentMatrix = new long[n + 1, n + 1]; Stack<long> stack = new Stack<long>(); bool[] visited = new bool[n + 1]; foreach(var city in cities){ adjacentMatrix[city[0], city[1]] = 1; adjacentMatrix[city[1], city[0]] = 1; } // for(int i = 0; i < n + 1; i++){ // for(int j = 0; j < n + 1; j++){ // Console.Write(adjacentMatrix[i,j]+" "); // } // Console.WriteLine(); // } long noOfComponents = 0; long noOfEdges = 0; for(long i = 1; i <= n; i++){ if(visited[i]){ continue; } stack.Push(i); visited[i] = true; noOfComponents++; while(stack.Count > 0){ long top = stack.Pop(); for(long j = 0; j <= n; j++){ if(!visited[j] && adjacentMatrix[top,j] == 1){ stack.Push(j); visited[j] = true; noOfEdges++; } } } } // Console.WriteLine(noOfCycles+" "+noOfRoads); return noOfComponents * c_lib + noOfEdges * c_road; } static void Main(string[] args) { TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true); long q = Convert.ToInt64(Console.ReadLine()); for (long qItr = 0; qItr < q; qItr++) { string[] nmC_libC_road = Console.ReadLine().Split(' '); long n = Convert.ToInt64(nmC_libC_road[0]); long m = Convert.ToInt64(nmC_libC_road[1]); long c_lib = Convert.ToInt64(nmC_libC_road[2]); long c_road = Convert.ToInt64(nmC_libC_road[3]); long[][] cities = new long[m][]; for (long i = 0; i < m; i++) { cities[i] = Array.ConvertAll(Console.ReadLine().Split(' '), citiesTemp => Convert.ToInt64(citiesTemp)); } long result = roadsAndLibraries(n, c_lib, c_road, cities); textWriter.WriteLine(result); } textWriter.Flush(); textWriter.Close(); } }
 Marked as answer by FaxMachine Saturday, August 24, 2019 2:31 PM
 Edited by FaxMachine Saturday, August 24, 2019 2:35 PM ADDING CODE!
Saturday, August 24, 2019 2:31 PM
All replies

Link to the problem: https://www.hackerrank.com/challenges/torqueanddevelopment/problemFriday, August 23, 2019 5:23 AM

So I found out what was going wrong with my code
My logic was totally correct the thing where I wasn't able to guess what was happening is that HACKERRANK handles OutOfMemoryException badly, they show wrong answer instead of showing that exception. So I changed my code to improve the time complexity.
So what I did is:#1. I removed the two dictionaries (visited and notVisited) and added a visited array instead as the array lookup will be quicker because a dictionary lookup is two operations: calculate the hash of the key to get an index and retrieve the value from an internal array at that index.
#2. Used adjacency list instead of adjacency matrix.
CODE:class Solution { // Complete the roadsAndLibraries function below. static long roadsAndLibraries(long n, long c_lib, long c_road, long[][] cities) { if(c_lib <= c_road  cities.Length == 0) return c_lib * n; long[,] adjacentMatrix = new long[n + 1, n + 1]; Stack<long> stack = new Stack<long>(); bool[] visited = new bool[n + 1]; foreach(var city in cities){ adjacentMatrix[city[0], city[1]] = 1; adjacentMatrix[city[1], city[0]] = 1; } // for(int i = 0; i < n + 1; i++){ // for(int j = 0; j < n + 1; j++){ // Console.Write(adjacentMatrix[i,j]+" "); // } // Console.WriteLine(); // } long noOfComponents = 0; long noOfEdges = 0; for(long i = 1; i <= n; i++){ if(visited[i]){ continue; } stack.Push(i); visited[i] = true; noOfComponents++; while(stack.Count > 0){ long top = stack.Pop(); for(long j = 0; j <= n; j++){ if(!visited[j] && adjacentMatrix[top,j] == 1){ stack.Push(j); visited[j] = true; noOfEdges++; } } } } // Console.WriteLine(noOfCycles+" "+noOfRoads); return noOfComponents * c_lib + noOfEdges * c_road; } static void Main(string[] args) { TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true); long q = Convert.ToInt64(Console.ReadLine()); for (long qItr = 0; qItr < q; qItr++) { string[] nmC_libC_road = Console.ReadLine().Split(' '); long n = Convert.ToInt64(nmC_libC_road[0]); long m = Convert.ToInt64(nmC_libC_road[1]); long c_lib = Convert.ToInt64(nmC_libC_road[2]); long c_road = Convert.ToInt64(nmC_libC_road[3]); long[][] cities = new long[m][]; for (long i = 0; i < m; i++) { cities[i] = Array.ConvertAll(Console.ReadLine().Split(' '), citiesTemp => Convert.ToInt64(citiesTemp)); } long result = roadsAndLibraries(n, c_lib, c_road, cities); textWriter.WriteLine(result); } textWriter.Flush(); textWriter.Close(); } }
 Marked as answer by FaxMachine Saturday, August 24, 2019 2:31 PM
 Edited by FaxMachine Saturday, August 24, 2019 2:35 PM ADDING CODE!
Saturday, August 24, 2019 2:31 PM